# Mean time to get $k$ heads for a coin with growing bias

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?

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?

• 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" – Matt F. Jan 24 '14 at 12:39
• 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}$. – Douglas Zare Jan 24 '14 at 16:02
• @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$. – marshall Jan 24 '14 at 16:18
• Yes, but for constant $k$ you already have a proof. – Douglas Zare Jan 24 '14 at 16:23
• I think your problem is fully solved in my answer below. Is there something there that you find unclear? – 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).