# Slowest frog on a ladder amongst many, how fast does it climb and how much is it lagging below the others?

In English: Frogs are climbing up a ladder. Each frog jumps to the next level of the ladder at unit rate and independently of the other frogs and of the level it is at. All the frogs start at level 0 at time 0. How much time before every frog climbed at least some given number of levels? At that time, how many frogs are already at least some given number of levels ahead? The population of frogs is large.

In maths: consider some independent random variables $(X_k^i)_{k,i}$ with standard exponential distributions, and, for every $i\geqslant1$, $k\geqslant1$ and $n\geqslant1$, $$Y_k^i=\sum_{\ell=1}^iX_k^\ell,\qquad T_n^i=\max\{Y_\ell^i\mid 1\leqslant \ell\leqslant n\}.$$ Thus, $T_n^i$ is the first time when the slowest of $n$ independent standard Poisson processes reaches level $i$.

If $i=1$, $T_n^1=\max\{X_\ell^1\mid 1\leqslant\ell\leqslant n\}$ hence one knows that its expectation $E[T^1_n]$ is the $n$th harmonic number, in particular $E[T^1_n]\sim\log n$ when $n\to\infty$ (the distribution of $T^1_n$ is explicitely known, although it is not needed to compute the expectation).

How to compute the value of the expectation $E[T_n^{i}]$ and/or find some asymptotics when $n\to\infty$, for some $i\geqslant2$ fixed?

For every $i\geqslant1$ and $j\geqslant1$, let $N^{i,j}_n$ denote the number of $1\leqslant\ell\leqslant n$ such that $Y_\ell^{i+j}\leqslant T_n^i$.

Thus, $N_n^{i,j}$ is the number of processes that are at least $j$ steps ahead of the slowest one, at the time when the slowest one reaches level $i$.

How to compute the value of the expectation $E[N_n^{i,j}]$ and/or find some asymptotics when $n\to\infty$, for some $i\geqslant1$ and $j\geqslant1$ fixed?

-
Hi, @Did; I believe I have an asymptotic result for the first part, however they appear to be excruciatingly slow to kick in even for $k = 2$. I need to do some checking, but hopefully I can make a first cut at a post in a day or two. I don't have anything useful for the second part, at the moment. – cardinal Oct 14 '13 at 2:42
@cardinal Good news. Take your time, there is no homework to be handed-in here... :-) – Did Oct 14 '13 at 7:21
$T_n^i - f_n$ converges in distribution to a simple, closed-form, non-degenerate distribution for some $f^i_n$. Want to offer a bounty? You can afford it. :) – Will Nelson Oct 29 '13 at 22:38
I added a few results for $N_n^{i,j}$ to my answer below. At this point, I suspect that $(n - N_n^{i,j} - c (\log n)^j)/(\log n)^{\frac{j}{2}}$ converges to a non-degenerate distribution for a particular constant $c$, but I don't know what that distribution is. At some point, I may try to compute it, if someone doesn't beat me to it! – Will Nelson Nov 7 '13 at 12:02

Here are some asymptotics for the first part:

Claim For every fixed $m$, the random variable $$S_n^m = T_{n}^m - \log n - (m-1) \log\log n+\log((m-1)!)$$ converges in distribution to the "extreme value" distribution independent of $m$ given by $$F_{S_\infty}(s) = \exp\left(-\mathrm e^{-s}\right).$$

Proof For frog $j$ and $t\ge 0$, let $M_{j,t}$ be the number of jumps frog $j$ has made at or before time $t$. Note that the $M_{j,t}$ are i.i.d. Poisson with mean $t$. Observe that for any $t\ge 0$, $$\{T_n^m\le t\} = \bigcap_{j=1}^n \{M_{j,t} \ge m\}.$$ Hence, $$F_{T_n^m}(t)\equiv \mathbb{P}(T_n^m\le t) = \left( 1 - \sum_{i=0}^{m-1} \mathrm e^{-t}\frac{t^i}{i!} \right)^n.$$ This is the cdf of $T_n^m$. We wish to characterize $F_{T_n^m}(t)$ as $n\to \infty$.

For brevity, define $$f_n^m \equiv \log n + (m-1) \log \log n - \log ((m-1)!).$$ Define $S_n^m$ as $$S_n^m = T_n^m - f_n^m.$$ The cdf $F_{S_n^m}$ of $S_n^m$ is $$F_{S_n^m}(s) = F_{T_n^m}(s+f_n^m).$$ Note \begin{eqnarray} F_{S_n^m}(s) &=& \left( 1 - \sum_{i=0}^{m-1} \mathrm e^{-(s+f_n^m)}\frac{(s+f_n^m)^i}{i!} \right)^n \\ &=& \left( 1 - \frac{\mathrm e^{-s}}{n}\frac{(m-1)!}{(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{(s+f_n^m)^i}{i!} \right)^n. \end{eqnarray} For fixed $s\ge 0$ and $m$, $$\lim_{n\to\infty} \frac{(m-1)!}{(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{(s+f_n^m)^i}{i!} = 1.$$ It follows that as $n\to\infty$, for fixed $m$ and $s\ge 0$, $$F_{S_n^m}(s) \to \exp\left(-\mathrm e^{-s}\right).$$

UPDATE

Claim For $m\ge 1$ and $n>0$, let $$f^m_n = \log n + (m-1) \log\log n - \log ((m-1)!).$$ Then for all $p\ge 0$ and $m\ge 1$, $$\lim_{n\to\infty}\mathbb{E}(T_n^m - f_n^m)^p = \int_{-\infty}^{\infty} e^{-e^{-s}}e^{-s} s^p\ ds.$$

Proof

The proof will rely on a number of simple facts allowing us to invoke the dominated convergence theorem. We state these facts without (much) proof.

Lemma 1 For $x>0$ and $n\ge 2$, $$\left(1 - \frac{1}{n} x\right)^{n-1} \le \left(1 - \frac{1}{n} x\right)^{\frac{1}{2}n} \le e^{-\frac{1}{2}x}.$$

Lemma 2 For $x\in\mathbb{R}$, $$1 - x \le e^{-x}.$$

Lemma 3 For $s\in\mathbb{R}$, the function $$n\mapsto \frac{s + f_n^m}{\log n}$$ is decreasing in $n$ as long as $s + f_n^m \ge \log n + m -1$. (Differentiate to show this.)

Lemma 4 For $s\in\mathbb{R}$ and $n$ restricted to be large enough such that $s + f_n^m \ge \log n + m -1$, $$\frac{(m+1)!}{(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{t^i}{i!} \downarrow 1$$ as $n\to\infty$. (Immediate from prior lemma.)

Now to the main proof. First assume $m=1$. The density function for $T_n^m$ is easy to compute. We may write \begin{eqnarray} \mathbb{E}\left(T_n^m - f_n^m)^p\right) &=& \int_{0}^{\infty} n \left(1- e^{-t}\right)^{n-1} e^{-t} (t-f_n^m)^p\ dt \\ &=& \int_{-\log n}^{\infty} \left(1- \frac{1}{n}e^{-s}\right)^{n-1} e^{-s} s^p\ ds. \end{eqnarray} The second integral is derived from the substitution $t=s+f_n^m$ in the first. It follows from Lemma 1 that $$\left(1- \frac{1}{n}e^{-s}\right)^{n-1} e^{-s} |s|^p \le e^{-\frac{1}{2}e^{-s}} e^{-s} |s|^p.$$ The rhs is integrable. By dominated convergence, \begin{eqnarray} \lim_{n\to\infty} \int_{-\log n}^{\infty} \left(1- \frac{1}{n}e^{-s}\right)^{n-1} e^{-s} s^p\ ds &=& \int_{-\infty}^{\infty} \lim_{n\to\infty}\left(1- \frac{1}{n}e^{-s}\right)^{n-1} e^{-s} s^p\ ds \\ &=& \int_{-\infty}^{\infty} e^{-e^{-s}} e^{-s} s^p\ ds. \end{eqnarray}

Now assume $m\ge 2$. We will break the expectation into two pieces. First, observe \begin{eqnarray} \mathbb{E}\left( |T_n^m - f_n^m|^p 1_{T_n^m\le \log n + m - 1}\right) &\le& (f_n^m)^p \mathbb{P}(T_n^m\le \log n + m - 1) \\ &=& (f_n^m)^p \left(1 - e^{-(\log n + m - 1)} \sum_{i=0}^{m-1} \frac{(\log n + m - 1)^i}{i!} \right)^n \\ &\le& (f_n^m)^p \left(1 - e^{-(\log n + m - 1)} (\log n + m - 1) \right)^n \\ &\le& (f_n^m)^p \left(1 - e^{-(m-1)}\frac{1}{n} \log n \right)^n \\ &\le& (f_n^m)^p \left(\exp(- e^{-(m-1)}\frac{1}{n} \log n)\right)^n \mbox{ [Lemma 2]}\\ &=& \frac{(\log n + (m-1)\log\log n - \log((m-1)!))^p}{n^{e^{-(m-1)}}}. \end{eqnarray} The last quantity vanishes as $n\to\infty$. Hence, $$\lim_{n\to\infty} \mathbb{E}\left( |T_n^m - f_n^m|^p 1_{T_n^m\le \log n + m - 1}\right) = 0.$$

Now consider $\mathbb{E}\left( (T_n^m - f_n^m)^p 1_{T_n^m > \log n + m - 1}\right)$. Again, the density function for $T_n^m$ is easily obtained. We may write \begin{eqnarray} \mathbb{E}\left( (T_n^m - f_n^m)^p 1_{T_n^m > \log n + m - 1}\right) &=& \int_{\log n + m -1}^{\infty} n \left( 1 - \sum_{i=0}^{m-1} \mathrm e^{-t}\frac{t^i}{i!} \right)^{n-1}\ e^{-t} \frac{t^{m-1}}{(m-1)!} \ (t - f_n^m)^p \ dt \\ &=& \int_{-f_n^m + \log n + m - 1}^{\infty} I_n^m(s) \ ds \end{eqnarray} where $$I_n^m(s) \equiv \left( 1 - \frac{1}{n} e^{-s}\frac{(m-1)!}{(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{(s+f_n^m)^i}{i!} \right)^{n-1}\ e^{-s} \frac{(s+f_n^m)^{m-1}}{(\log n)^{m-1}} \ s^p.$$ The second integral is derived from the first by substituting $t = s + f_n^m$.

Fix $s$. We will show that for large enough $n$ and all $s$, $$(*)\ \ \ |I_n^m| \le e^{-\frac{1}{2}e^{-s}} e^{-s} s^p (|s| + 2)^{m-1}.$$ To see this, first note that for large enough $n$, \begin{eqnarray} \left|\frac{s+f_n^m}{\log n}\right| &=& \frac{|s+\log n + (m-1)\log\log n - \log((m-1)!)|}{\log n} \\ &\le& |s| + 2. \end{eqnarray}

Next, Lemma 4 and Lemma 2 combine to show that if $n$ is large enough that $s \ge - f_n^m + \log n + m -1$, then $$\left(1-\frac{e^{-s}}{n}\frac{(m+1)!}{(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{(s+f_n^m)^i}{i!}\right)^{n-1} \le e^{-\frac{1}{2}e^{-s}}.$$ The integrable bound in $(*)$ is proved. By dominated convergence, \begin{eqnarray} \lim_{n\to\infty} \mathbb{E}\left( (T_n^m - f_n^m)^p 1_{T_n^m > \log n + m - 1}\right) &=& \lim_{n\to\infty} \int_{-f_n^m + \log n + m - 1}^{\infty} I_n^m(s) \ ds \\ &=& \int_{-\infty}^{\infty} \lim_{n\to\infty} I_n^m(s) \ ds \\ &=& \int_{-\infty}^{\infty} e^{-e^{-s}} e^{-s} s^p \ ds. \end{eqnarray}

UPDATE 2

Claim Let $N_n^{m,h}$ be defined as in the original question, i.e., $N_n^{m,h}$ is the number of frogs among $n$ that have jumped at least $m+h$ times when the last frog to jump $m$ times does so. Then $N_n^{m,h}$ is binomially distributed with $n-1$ trials and probability of success $p_n^{m,h}$ given by $p_n^{m,0} = 1$ and $$p_n^{m,h} = \int_0^{\infty} n \left(1 - e^{-t}\sum_{i=0}^{m+h-1} \frac{t^i}{i!} \right) \left(1 - e^{-t}\sum_{i=0}^{m-1} \frac{t^i}{i!} \right)^{n-2} e^{-t} \frac{t^{m-1}}{(m-1)!} \ dt$$ for $h>0$.

Let $J_n^{m,i}$ be the number of jumps frog $i$ has already made at time $T_n^m$, i.e., at the time the slowest frog finally makes his $m^{\mbox{th}}$ jump. Observe that, conditioned on frog $1$ being the slowest frog, $\{J_n^{m,i}\}_{i=2,3,\ldots,n}$ are jointly independent and identically distributed. It follows that, conditioned on frog $1$ being the slowest frog, $N_n^{m,h}$ is binomially distributed with $n-1$ trials and probability of success $$p_n^{m,h}\equiv\mathbb{P}(J_n^{m,2}\ge m+h |\mbox{frog 1 is slowest}).$$ Now notice that exactly this same distribution obtains for $N_n^{m,h}$ conditioned on any frog $i$ being slowest. It follows that $N_n^{m,h}$ is (unconditionally) binomial with $n-1$ trials and probability $p_n^{m,h}$ given above.

We can calculate \begin{eqnarray} p_n^{m,h} &=& \mathbb{P}(J_n^{m,2}\ge m+h\ |\ \mbox{frog 1 is slowest}) \\ &=& \mathbb{P}(J_n^{m,2}\ge m+h\ |\ \mbox{frog 2 is not slowest}) \\ &=& \int_0^{\infty} \mathbb{P}(J_n^{m,2}\ge m+h\ |\ \mbox{frog 2 is not slowest,} T_n^m=t) \ dF_{T_n^m}(t) \\ &=& \int_0^{\infty} \frac{1 - e^{-t} \sum_{i=0}^{m+h-1} \frac{t^i}{i!}}{1 - e^{-t} \sum_{i=0}^{m-1} \frac{t^i}{i!}}\ dF_{T_n^m}(t). \end{eqnarray} The result follows from the expression for $F_{T_n^m}$ given above.

Claim For $h\ge 1$, $$\lim_{n\to\infty} \frac{(m+h-1)!}{(m-1)!}\frac{n}{(\log n)^h}(1- p_n^{m,h}) = 1.$$

We have $$1 = \int_0^{\infty} n \left(1 - e^{-t}\sum_{i=0}^{m-1} \frac{t^i}{i!} \right) \left(1 - e^{-t}\sum_{i=0}^{m-1} \frac{t^i}{i!} \right)^{n-2} e^{-t} \frac{t^{m-1}}{(m-1)!} \ dt,$$ so \begin{eqnarray} 1-p_n^{m,h} &=& \int_0^{\infty} n \left(e^{-t}\sum_{i=m}^{m+h-1} \frac{t^i}{i!} \right) \left(1 - e^{-t}\sum_{i=0}^{m-1} \frac{t^i}{i!} \right)^{n-2} e^{-t} \frac{t^{m-1}}{(m-1)!} \ dt \\ &=& \int_{-f_n^m}^{\infty} I_n^{m,h}(s) \ ds \end{eqnarray} where \begin{eqnarray} I_n^{m,h}(s) &=& \frac{e^{-2s}(m-1)!(s+f_n^m)^{m-1}}{n(\log n)^{2(m-1)}} \left(\sum_{i=m}^{m+h-1} \frac{(s+f_n^m)^i}{i!} \right) \\ & & \ \ \ \ \ \ \ \ \ \ \times \ \left(1 - \frac{e^{-s}(m-1)!}{n(\log n)^{m-1}}\sum_{i=0}^{m-1} \frac{(s+f_n^m)^i}{i!} \right)^{n-2}. \end{eqnarray} One can verify $$\lim_{n\to\infty} \frac{(m+h-1)!}{(m-1)!} \frac{n}{(\log n)^h} I_n^{m,h}(s) = e^{-e^{-s}} e^{-2s}.$$ Also, one can use techniques similar to the previous claim to show that dominated convergence can be invoked and \begin{eqnarray} \lim_{n\to\infty} \frac{(m+h-1)!}{(m-1)!} \frac{n}{(\log n)^h} (1-p_n^{m,h}) &=& \int_{\infty}^{\infty} \lim_{n\to\infty} \frac{(m+h-1)!}{(m-1)!} \frac{n}{(\log n)^h} I_n^{m,h}(s) \ ds \\ &= & \int_{-\infty}^{\infty} e^{-e^{-2}} e^{-2s}\ ds \\ &=& 1. \end{eqnarray}

Corollary For $h\ge 1$, $$\lim_{n\to \infty} \frac{(m+h-1)!}{(m-1)!}\frac{n - \mathbb{E}(N_n^{m,h})}{(\log n)^h} = 1,$$ and $$\frac{(m+h-1)!}{(m-1)!}\frac{n - N_n^{m,h}}{(\log n)^h} \overset{L^2}{\longrightarrow} 1.$$

This is immediate from $\mathbb{E}(N_n^{m,h}) = (n-1) p_n^{m,h}$, $\mathrm{Var}(N_n^{m,h}) = (n-1) p_n^{m,h}(1-p_n^{m,h})$, and the previous result.

-
Verrry nice. +1. – Did Oct 30 '13 at 20:45
Glad I could help. I suspect $\mathbb{E}(T_n^m) - \log n - (m-1)\log\log n + \log (m-1)!$ converges, as well, to the mean of the extreme value distribution, but I haven't proved it yet. And on $N_n^{i,j}$, I believe this is binomially distributed with "sample size" $n-1$ and probability of success $p_n^{i,j}$ theoretically computable from the cdf of $F$ above. Observe for fixed $i$, $j$, $p_n^{i,j}\to 1$ as $n\to \infty$, so the fraction of frogs $j$ jumps ahead of the slowest frog always goes to $1$. – Will Nelson Oct 30 '13 at 21:21
(+1) This is part of the result mentioned in my first comment to @Did. The expectations do, indeed, converge. See Pickands (1968) (but watch out for typos and slightly sloppy arguments) or, e.g., Section 5.3 of de Haan and Ferreira (2006). – cardinal Nov 2 '13 at 19:13
@cardinal Thanks for the references. Please feel free to add your own contribution, especially if it proves some further results. – Did Nov 3 '13 at 11:54