1
$\begingroup$

Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure:

W := an array of length m full of 0s
for i in 0, 1, ..., n - 1; do
    (x, y) := (rand(), rand())
    W[y] := max(W[x], W[y]) + 1
x := 0
for i in 0, 1, ..., m - 1; do
    if W[i] > x; do
         x := W[i]
return x

My question is: what is the most-probable value of $x$? I'm not even sure where to begin with the analysis here, due to the probabilities involved.

$\endgroup$
  • $\begingroup$ Yes, this seems like a difficult question. The first step would be to notice that the second loop just returns the maximal value in W. $\endgroup$ – Yuval Filmus Apr 2 '17 at 7:08
  • $\begingroup$ @YuvalFilmus I'm aware - that's kinda the point. I wanted to spell it out, instead of writing 'max(W)' or something. $\endgroup$ – Koz Ross Apr 2 '17 at 7:42
3
$\begingroup$

The question sounds a bit difficult. I was able to calculate the expectation of $x$ when $m = 2$. The most probable value of $x$ should be very close to its expectation. Perhaps this will give you some ideas.

The idea is to construct an infinite Markov chain whose states are $|W[0]-W[1]|$, and whose transitions are labeled by whether $\max(W(0),W(1))$ increases or not. Here are the transitions (explained below):

  1. At state 0, we transition to state 1 w.p. 1, increasing the maximum.
  2. At state $n > 0$, we transition to state $n-1$ w.p. 1/4; to state $n+1$ w.p. 1/2, increasing the maximum; and to state 1 w.p. 1/4, increasing the maximum.

The first case is trivial. For the second case, consider the array $a+n,a$. There are four options, each occurring w.p. 1/4:

  • When $x=y=0$, the new array is $a+n+1,a$ (the maximum increases).
  • When $x=y=1$, the new array is $a+n,a+1$ (the maximum doesn't increase).
  • When $x=0,y=1$, the new array is $a+n,a+n+1$ (the maximum increases).
  • When $x=1,y=0$, the new array is $a+n+1,a$ (the maximum increases).

The next step is to calculate the stationary probability (it is easy to check that the chain is ergodic). Denoting it by $p_n$, we have

  • $p_0 = \frac{p_1}{4}$.
  • $p_1 = p_0 + \frac{p_1 + \cdots}{4} + \frac{p_2}{4} = p_0 + \frac{1-p_0}{4} + \frac{p_2}{4}$.
  • $p_n = \frac{p_{n-1}}{2} + \frac{p_{n+1}}{4}$ for $n \geq 2$.

The sequence $p_1,p_2,\ldots$ satisfies the recurrence $$ p_n = 4p_{n-1} - 2p_{n-2}. $$ The roots of $x^2 - 4x + 2$ are $2 \pm \sqrt{2}$, and since the series $\sum_{n \geq 1} p_n$ converges, we must have $p_n = C (2-\sqrt{2})^n$. In particular, $p_2 = (2-\sqrt{2})p_1$. Substituting this in the formulas for $p_0,p_1$, we can calculate $$ p_0 = \frac{4\sqrt{2}-5}{7}, \qquad p_1 = \frac{16\sqrt{2}-20}{7}. $$ Notice now that when at state $n>0$, the maximum increases with probability 3/4, and when at state 0, it always increases. Hence the probability that it increases at the stationarity is $$ \frac{3}{4} + \frac{p_0}{4} = \frac{4+\sqrt{2}}{7}. $$ Denoting by $X_n$ the expected value of $x$ when $m=2$ and $n$ is given, we deduce that $$ \lim_{n\to\infty} \frac{\mathbb{E}[X_n]}{n} = \frac{4+\sqrt{2}}{7} \approx 0.773459. $$ This is corroborated by experiment. When $n=1000$, the empirical average of $10^6$ trials is $0.773733$ (the expected error is of order $10^{-3}$).

The expected gap between $\max(W)$ and $\min(W)$ is $$ \sum_{n=1}^\infty np_n = p_1 \sum_{n=1}^\infty n(2-\sqrt{2})^{n-1} = \frac{p_1}{(\sqrt{2}-1)^2} = \frac{4+8\sqrt{2}}{7} \approx 2.18767. $$ In particular, the limits of $\mathbb{E}[\max(W)]/n$ and $\mathbb{E}[\min(W)]/n$ (after $n$ steps) are the same.

In a similar way, it should be possible to compute $\lim_{n\to\infty} \mathbb{E}[\max(W)]/n$ for any fixed $m$, though I don't know if there is a nice formula for this limit in general.

Other limits could also be interesting. For example, one could ask what happens if $n$ is fixed and $m\to\infty$ (this should be easy to answer), or when $n=m \to \infty$ (seems more difficult).

Calculating the exact expectation for given $n,m$ is possible using the same ideas, but there isn't probably any nice formula.

$\endgroup$
  • $\begingroup$ Thank you so much for all this work - I must admit it's somewhat over my head. You say that a 'nice formula' given $n,m$ probably doesn't exist; what about a nice asymptotic bound (i.e. Big-Oh something-using-$n,m$)? $\endgroup$ – Koz Ross Apr 3 '17 at 0:24
  • $\begingroup$ Multivariate asymptotics are very confusing. It's much better if you can point out a single sequence of pairs $n,m$ whose behavior you want to analyze. $\endgroup$ – Yuval Filmus Apr 3 '17 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.