Let $L_n$ be the largest contiguous heads sequence in $n$ coin tosses with $p$ probability of having head. It is known that

$$ \forall \epsilon>0 \lim\limits_{n\to\infty}\mathbb{P} \left(\left|\frac{L_n}{\log_{1/p}n}-1\right|>\epsilon \right)=0 $$

I have the following problem. Suppose that now, for each n, the probability of having an head is $p_n$, that is it depends on the number of coin tosses. Suppose further that $p_n\rightarrow 1$ as $n\rightarrow\infty$. More precisely, $p_n=1-\frac{\gamma}{n}$ with $\gamma>0$. What can be said now about $L_n$ ? My guess is that it has an exponential or a linear growth, so that

$$ L_n = O_p\left(e^n\right) $$

or, alternatively,

$$ L_n=O_p(n) $$

instead of $L_n = O_p\left(\log n\right)$ as for the case in Schilling (1990).

  • $\begingroup$ Is it possible to assume that $p_n \nearrow 1$ as $n \to \infty$? $\endgroup$ – Hugo Oct 14 '16 at 19:27
  • $\begingroup$ Yes of course, we must assume that $p_n\rightarrow 1^{-}$ as $n\rightarrow\infty$. $\endgroup$ – AlmostSureUser Oct 15 '16 at 7:13

Surely, $L_n$ cannot grow exponentially, as it does not exceed $n$; this is just a weird mistake. But the second guess is correct: the order of $L_n$ is exactly $n$. However, $L_n/n$ converges not to a constant, but to a distribution. A quick way to see this is to remark that $L_n = n$ with probability $(1-\gamma/n)^n \to e^{-\gamma}$. But it is possible to identify the limit distribution explicitly.

Let $T^n_k$ be the moment when $k$th tail appears, and $X_n = \#\{k\le n: T_k^n\le n\}$ be the number of tails in the first $n$ flips. It has a binomial $(n,\gamma/n)$ distribution. It is well known that $X_n$ converges in distribution, as $n\to\infty$, to a random variable $X$ having Poisson distribution with parameter $\gamma$.

Further, it is easy to see that, given $X_n = k$, the set $\{T^n_1,T^n_2,\dots,T^n_k\}$ is uniformly distributed among $k$-subsets of $1,\dots,n$. Therefore, as $n\to\infty$, the distribution of $(T^n_1/n,T^n_2/n,\dots,T^n_k/n)$ given $X_n=k$ converges to the uniform distribution on $$\mathbb{S}_k = \{(x_1,\dots,x_k): 0\le x_1\le \dots\le x_k\le 1\}.$$ The lengths of head runs in first $n$ flips are just $T^n_i-T^n_{i-1}-1$, $i\ge 1$, and $n-T^n_{X_n}$. Therefore, given $X_n=k$, these lengths, divided by $n$, converge in distribution to $(S_1,\dots,S_{k+1}) = (\tau_1, \tau_2 - \tau_1,\tau_3-\tau_2,\dots,\tau_k - \tau_{k-1},1-\tau_k)$, where the vector $(\tau_1,\dots,\tau_k)$ is uniformly distributed over $\mathbb S_k$. As a result, $L_n/n$ given $X_n=k$ converges in distribution, as $n\to\infty$, to $$ M_k = \max\{S_1,\dots,S_{k+1}\}, $$ where the vector $(S_1,\dots,S_{k+1})$ is uniformly distributed over the simplex $\mathbb T_{k+1} = \{(x_1,\dots,x_{k+1}) : x_i\ge 0, x_1+\dots + x_{k+1} = 1\}$.

Hence we can find the distribution of $L$. It has atom in $1$ (corresponding to the case $X = 0$) of size $e^{-\gamma}$ and density on $[0,1]$ of the form $$ f(x) = \sum_{k=1}^\infty \mathsf{P}(X = k) f_k (x) = \sum_{k=1}^\infty\frac{\gamma^k e^{-\gamma}}{k!} f_k(x), $$ where $f_k(x)$ is the density of $M_k$. It is a matter of the inclusion-exclusion argument to show that $$ f_k(x) = (k+1)k\sum_{i=0}^{\lfloor 1/x\rfloor-1} (-1)^{i}{k\choose i}(1-ix)^{k-1}. $$ (Note that $f_k(x) = 0$ for $x<1/(k+1)$.) Finally we get $$ f(x) = \sum_{k=1}^\infty\frac{\gamma^k e^{-\gamma}(k+1)}{(k-1)!}\sum_{i=0}^{\lfloor 1/x\rfloor-1} (-1)^{i}{k\choose i}(1-ix)^{k-1}. $$

It is possible to rearrange the sum and to write it somewhat shorter. I'll write the ultimate expression for the cdf $F(x) = \mathsf{P}(L<x)$ rather than that for the density, as it looks nicer and includes both continuous part and the jump part: $$ F(x) = e^{-\gamma}\left(\sum_{i=0}^{\lfloor 1/x\rfloor} \frac{\big(\gamma(ix-1)\big)^i}{i!}e^{\gamma(1-ix)} - \sum_{i=0}^{\lfloor 1/x\rfloor - 1} \frac{\big(\gamma((i+1)x-1)\big)^i}{i!}e^{\gamma(1-(i+1)x)}\right),\quad x\ge 0. $$ Here $\sum_{i=0}^{-1} = 0$ and $0^0 = 1$.

  • $\begingroup$ I guess $Z^n(t)$ is $Z^n(t) = X^n_{\lfloor t\,n\rfloor}$ instad of $Z^n(t) = X^n_{\lfloor rn\rfloor}$, right? Secondly, I do not understand the meaning of $\Pi_{\gamma}\left(1\right)$ in $L = \max\left\{\max_{1\le i\le\Pi_\gamma(1)} E_i, 1 - \tau_i\right\}.$ $\endgroup$ – AlmostSureUser Oct 20 '16 at 9:04
  • $\begingroup$ Third, I do not get what you mean with "the joint distribution of $E_1,\dots, E_{k}$ and $\tau_k$ is uniform over the simplex $\mathbb{T}_{k+1}$". $\endgroup$ – AlmostSureUser Oct 20 '16 at 9:10
  • $\begingroup$ @AlmostSureUser, I have rewritten this part. Please check if it is clearer now. $\endgroup$ – zhoraster Oct 20 '16 at 11:24

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.