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?



Mean time to get $k$ heads for a coin with growing bias
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). 


