For integers $n,k\geq 1$ we repeatedly toss a coin and count the number of heads that occur. The probabilty of getting a head is $min(t/n,1)$ where $t$ is the current discrete time step. I am trying to work out the asymptotics of the mean time to get $k$ heads. My claim is the following.

Claim: Let $X$ be a random variable which represents the number of coin tosses at the $k$th head. If $k$ is $o(n)$ and $n \rightarrow \infty$, we have: $$\mathbb{E}(X) \sim \sqrt{2n}\frac{\Gamma(k+\frac{1}{2})}{(k-1)!}$$

My "proof" uses a limit approximation of a nonhomogeneous Bernoulli process by a nonhomogeneous Poisson process. We then compute the expected number of tosses by transforming the nonhomogeneous Poission process to a homogeneous process by an application of the inverse transform method.

Let $T_k$ be the time taken to see $k$ events in a Poisson process with increasing rate $t/n$, $t >0$. Define $$\Lambda(t) \overset{\text{def}}{=}\;\; \int_0^t \frac{x}{n} dx = \frac{t^2}{2n}$$ with inverse $$\Lambda^{-1}(y) = \sqrt{2 y n}.$$

The key observation is that $T_k$ has the same distribution as $\Lambda^{-1}(S_k)$, where $S_k$ is the time taken to see $k$ events in a Poisson process with rate $1$.
We want \begin{align*} \mathbb{E}(T_k) &= \mathbb{E}(\sqrt{2n S_k}) \\ &= \sqrt{2n} \int_0^\infty \frac{x^{1/2} x^{k-1} e^{-x}}{(k-1)!} \mathrm{d}x\\ &= \frac{\Gamma(k+\frac{1}{2})}{(k-1)!}. \end{align*}

The problem is that when $k$ grows with $n$, as is permitted in the claim, I don't see how to give a formal justification for this line of reasoning. In particular, how can you justify the limit approximation?

Any help gratefully received.

As Douglas Zare points out, when $k$ grows with $n$ (and is also $o(n)$), the claim is equivalent to $$\mathbb{E}(X) \sim \sqrt{2nk}.$$

If my particular approach can't be justified, is there another way to get the same result which has a surer footing?

  • $\begingroup$ The word "coin" suggests constant probability -- it might be clearer to title this as "Mean time to get k heads for a coin with growing bias" $\endgroup$ – Matt F. Jan 24 '14 at 12:39
  • $\begingroup$ It looks like you meant $\Gamma(k+ \frac{1}{2})$ in your claim as well. If $k$ grows with $n$ you can simplify $\Gamma(k+ \frac{1}{2})/(k-1)!$ to $\sqrt{k}$. $\endgroup$ – Douglas Zare Jan 24 '14 at 16:02
  • $\begingroup$ @DouglasZare Thank you for the typo fix and the simplification. I think the function I give is also correct for constant $k$ and $n\to \infty$. $\endgroup$ – marshall Jan 24 '14 at 16:18
  • $\begingroup$ Yes, but for constant $k$ you already have a proof. $\endgroup$ – Douglas Zare Jan 24 '14 at 16:23
  • $\begingroup$ I think your problem is fully solved in my answer below. Is there something there that you find unclear? $\endgroup$ – Lucia Jan 31 '14 at 16:57

Let me just consider the case when $k$ is growing, but still $o(n)$ (in fact, we can even let $k$ go up to $(1/2-\epsilon)n$). I will show that the expected number of coin tosses is about $\sqrt{2nk}$ as conjectured. In fact the argument shows more, getting bounds for the probability of getting $k$ heads after exactly $y$ tosses.

Let $P(k,y)$ denote the probability that we get $k$ heads exactly after $y$ tosses (so the $y$-th toss is heads, and there are $k-1$ heads up till then). If $y\le n$, then note that $P(k,y)$ equals $y/n$ times the coefficient of $x^{k-1}$ in $\prod_{i\le y-1} (x(i/n)+(1-i/n)) =Q_y(x)$ say. Now $Q_y(x)$ is a polynomial with non-negative coefficients, and therefore the coefficient of $x^{k-1}$ is bounded by $Q_y(r)r^{-(k-1)}$ for any positive real number $r$. Thus we have that $$ P(k,y) \le \frac{y}{n} \min_{r>0} Q_y(r) r^{-(k-1)}. $$

Now note that $$ Q_y(r) = \prod_{i\le y-1} (1+ (r-1)i/n) \le \exp\Big(\sum_{i=1}^{y-1} \frac{(r-1)i}{n} \Big) = \exp\Big( \frac{(r-1)y(y-1)}{2n} \Big). $$ A little calculus shows that $(r-1) y(y-1)/(2n) - (k-1)\log r$ attains its minimum when $r=2n(k-1)/(y(y-1))$. Taking this value for $r$, we obtain with $t=y(y-1)/(2n(k-1))$ $$ P(k,y) \le \frac{y}{n} \exp\Big( -(k-1)(t-1-\log t) \Big). $$

Now note that $t-1-\log t$ is approximately $(t-1)^2/2$ if $t$ is close to $1$; and that if $|t-1|>\delta$ then $(t-1-\log t)$ is at least $C\delta |t-1|$ for an absolute positive constant $C$. Thus if $|y(y-1)/(2n(k-1))-1| > \delta$ then from the above estimates it follows that $$ P(k,y) = O\Big(\frac{y}{n} \exp\Big(-C\delta (k-1)\Big|\frac{y(y-1)}{2n(k-1)}-1\Big|\Big) \Big). $$ In other words, the probability is tiny (exponentially small in $k$) unless $y(y-1)$ is very close to $2n(k-1)$; that is, unless $y$ is about $\sqrt{2nk}$. From this it is easy to see that the expected value is $\sim \sqrt{2nk}$ as conjectured.

If one argues carefully using the saddle point method, one could obtain asymptotics for $P(k,y)$; as the argument above indicates, the likely values of $y$ are sharply concentrated around $\sqrt{2nk}$.

Added: In the range where $y=o(n^{2/3})$ and $k=o(\sqrt{y})$, directly from the definition one can compute that $$ P(k,y) \sim \frac{y}{n} e^{-y^2/(2n)} \frac{(y^2/(2n))^{k-1}}{(k-1)!}. $$ So in the range $k=o(n^{1/3})$ one can compute the distribution directly (getting Gaussian fluctuations) -- this will also give the right result for bounded $k$. For larger $k$ one can use the previous argument of bounding the probability away from the peak (or work harder and get asymptotics using the saddle point method).


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.