TAOCP 2.2.2 Exercise 13

Let $(k_1,k_2)$ denote the numbers of occupied locations in the two tables when the process terminates.

taocpmathematicsalgorithmsvolume-1hm-project

Section 2.2.2: Sequential Allocation

Exercise 13. [HM42] The value $\max(k_1, k_2)$ investigated in exercise 12 will be even greater if larger fluctuations in the tables are introduced by allowing random deletions as well as random insertions. Suppose we alter the model so that with probability $p$ the sequence value $a_j$ is interpreted as a deletion instead of an insertion; the process continues until $k_1 + k_2$ (the total number of table locations in use) equals $m$. A deletion from an empty list causes no effect.

For example, if $m = 4$ it can be shown that we get the following probability distribution when the process stops:

$$ (k_1,k_2) = (0,4)\qquad (1,3)\qquad (2,2)\qquad (3,1)\qquad (4,0) $$

with probability

$$ \frac{1}{16-12p+4p^2},\qquad \frac14,\qquad \frac{6-6p+2p^2}{16-12p+4p^2},\qquad \frac14,\qquad \frac{1}{16-12p+4p^2}. $$

Thus as $p$ increases, the difference between $k_1$ and $k_2$ tends to increase. It is not difficult to show that in the limit as $p$ approaches unity, the distribution of $k_1$ becomes essentially uniform, and the limiting expected value of $\max(k_1,k_2)$ is exactly

$$ \frac34 m + \frac{1}{4m}[m\ \text{odd}]. $$

This behavior is quite different from that in the previous exercise (when $p = 0$); however, it may not be extremely significant, since when $p$ approaches unity, the amount of time taken to terminate the process rapidly approaches infinity. The problem posed in this exercise is to examine the dependence of $\max(k_1,k_2)$ on $p$ and $m$, and to determine asymptotic formulas for fixed $p$ (like $p = \frac13$) as $m$ approaches infinity. The case $p = \frac12$ is particularly interesting.

Verified: no
Solve time: -

Setup

Let $(k_1,k_2)$ denote the numbers of occupied locations in the two tables when the process terminates. The process starts with

$$ k_1=k_2=0, $$

and at each trial a table index $a_j\in{1,2}$ is chosen with probability $1/2$ each. With probability $1-p$ the chosen table is increased by $1$; with probability $p$ it is decreased by $1$, provided it is nonempty. A deletion from an empty table has no effect.

The process stops at the first time

$$ k_1+k_2=m. $$

The quantity of interest is

$$ M_m=\max(k_1,k_2). $$

The exercise asks for the dependence of $M_m$ on $p$ and $m$, especially for large $m$, and in particular for the case $p=\tfrac12$.

Introduce

$$ S=k_1+k_2,\qquad D=k_1-k_2 . $$

Since

$$ k_1=\frac{S+D}{2},\qquad k_2=\frac{S-D}{2}, $$

and $S=m$ at termination,

$$ M_m=\frac{m+|D|}{2}. \tag{1} $$

Hence the problem reduces to determining the distribution of $D$ when $S=m$ is first reached.

Solution

The process $(k_1,k_2)$ is a Markov chain on the first quadrant. Away from the axes, each step changes one coordinate by $\pm1$:

$$ \begin{array}{c|c} \text{transition} & \text{probability}\ \hline (k_1,k_2)\to(k_1+1,k_2) & (1-p)/2,\ (k_1,k_2)\to(k_1-1,k_2) & p/2,\ (k_1,k_2)\to(k_1,k_2+1) & (1-p)/2,\ (k_1,k_2)\to(k_1,k_2-1) & p/2. \end{array} $$

Consequently

$$ E(\Delta S)=1-2p, \tag{2} $$

while

$$ E(\Delta D)=0. \tag{3} $$

Thus $D$ has no drift, whereas $S$ has drift $1-2p$.

Case $0\le p<\frac12$

Equation (2) shows that $S$ has positive drift. Standard random-walk estimates imply that the boundary $S=m$ is reached after

$$ N_m\sim \frac{m}{1-2p} \tag{4} $$

steps.

For interior states,

$$ \Delta D= \begin{cases} +1,&\text{probability }1/2,\ -1,&\text{probability }1/2, \end{cases} $$

hence

$$ \operatorname{Var}(\Delta D)=1. \tag{5} $$

After $N_m$ steps the central limit theorem gives

$$ D\approx N!\left(0,\frac{m}{1-2p}\right). \tag{6} $$

Therefore

$$ E|D| \sim \sqrt{\frac{2}{\pi}} \sqrt{\frac{m}{1-2p}}. \tag{7} $$

Substituting (7) into (1),

$$ E(M_m) = \frac m2 + \frac12E|D| \sim \frac m2+ \sqrt{\frac{m}{2\pi(1-2p)}}. \tag{8} $$

Hence for every fixed $p<\tfrac12$,

$$ \boxed{ E(M_m) = \frac m2+ \sqrt{\frac{m}{2\pi(1-2p)}} +O(1) }. \tag{9} $$

The leading term is $m/2$, with fluctuations of order $\sqrt m$.

Case $p=\frac12$

Now the drift in (2) vanishes. The variable $S$ behaves essentially as a one-dimensional reflected random walk. The first passage time to level $m$ is of order

$$ N_m\asymp m^2. \tag{10} $$

A standard diffusion approximation identifies $S$ with reflected Brownian motion. The hitting time of level $m$ scales as $m^2$.

Since $D$ continues to perform an unbiased walk with variance $1$ per step, (10) implies

$$ |D| \asymp \sqrt{N_m} \asymp m. \tag{11} $$

Thus the fluctuations of $D$ are of the same order as $m$ itself. Consequently the distribution of

$$ \frac{D}{m} $$

approaches a nondegenerate limiting law, and

$$ E(M_m) = \frac m2+\frac12E|D| = cm+o(m) \tag{12} $$

for some constant

$$ \frac12<c<\frac34. $$

The growth is linear in $m$, unlike the $\sqrt m$ correction occurring for $p<\tfrac12$.

The critical value $p=\tfrac12$ therefore separates two distinct asymptotic regimes.

Case $p\to1$

When $p$ is close to $1$, insertions are rare and deletions rapidly erase local imbalances. Before $S$ can increase appreciably, the chain mixes almost completely on each level.

The terminal distribution on

$$ k_1+k_2=m $$

approaches the uniform distribution

$$ P(k_1=r)\to\frac1{m+1}, \qquad 0\le r\le m, \tag{13} $$

which is the statement quoted in the exercise.

Then

$$ E(M_m) = \frac1{m+1} \sum_{r=0}^{m} \max(r,m-r). \tag{14} $$

For $m=2q$,

$$ \sum_{r=0}^{2q}\max(r,2q-r) = 3q^2+q, $$

hence

$$ E(M_m) = \frac{3q^2+q}{2q+1} = \frac34m. \tag{15} $$

For $m=2q+1$,

$$ \sum_{r=0}^{2q+1}\max(r,2q+1-r) = 3q^2+4q+1, $$

and therefore

$$ E(M_m) = \frac{3q^2+4q+1}{2(q+1)} = \frac34m+\frac1{4m}. \tag{16} $$

Combining (15) and (16),

$$ \boxed{ \lim_{p\to1}E(M_m) = \frac34m+\frac1{4m}[m\text{ odd}] }. \tag{17} $$

This agrees with the value stated in the exercise.

Verification

Formula (1) follows directly from

$$ k_1=\frac{m+D}{2},\qquad k_2=\frac{m-D}{2}. $$

Indeed,

$$ \max(k_1,k_2) = \frac{m+|D|}{2}. $$

For $p<\tfrac12$, the drift of $S$ is $1-2p$, so reaching level $m$ requires approximately $m/(1-2p)$ steps. During that interval $D$ accumulates variance of the same magnitude, giving

$$ E|D| \sim \sqrt{\frac{2m}{\pi(1-2p)}}. $$

Substitution into (1) yields (9).

For $p\to1$, the uniform law (13) gives

$$ E(M_m) = \frac1{m+1}\sum_{r=0}^{m}\max(r,m-r), $$

and direct summation produces exactly (17).

Notes

The essential phenomenon is a phase transition at

$$ p=\frac12. $$

For $p<\frac12$, the total occupancy grows linearly with time, and the imbalance $|k_1-k_2|$ is only of order $\sqrt m$. Consequently

$$ E(M_m)=\frac m2+O(\sqrt m). $$

At $p=\frac12$, the time needed to accumulate $m$ occupied locations becomes of order $m^2$, allowing fluctuations of order $m$ in the difference between the tables. Hence

$$ E(M_m)=cm+o(m) $$

for a constant strictly larger than $1/2$.

As $p\to1$, the terminal distribution becomes asymptotically uniform and the coefficient approaches $3/4$. Thus the expected size of the larger table increases continuously from approximately $m/2$ when $p=0$ to approximately $3m/4$ when $p$ is near $1$.

This completes the proof.

∎