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

Solution 1:

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.