# Most probable value of randomized procedure output

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.

• 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. – Yuval Filmus Apr 2 '17 at 7:08
• @YuvalFilmus I'm aware - that's kinda the point. I wanted to spell it out, instead of writing 'max(W)' or something. – Koz Ross Apr 2 '17 at 7:42

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-W|$, 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.

• 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$)? – Koz Ross Apr 3 '17 at 0:24
• 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. – Yuval Filmus Apr 3 '17 at 5:33