0
$\begingroup$

I am trying to work out the asymptotic large $t$ behavior of following function \begin{equation} f(t ) = \sum_{x = 0}^{2t} { 2t \choose t + x} p^{ t+x } (1 - p)^{ t - x} = \sum_{x = 0}^{2t} { 2t \choose t + x} [p ( 1- p)]^{ t} \left( \frac{p }{1 -p } \right)^x \end{equation} with $p > \frac{1}{2}$. Specifically, I want to find \begin{equation} \alpha = \lim_{ t\rightarrow \infty} - \frac{\ln f(t)}{t} \end{equation}

I have two ways to approximate the sum, resulting in two different answers.

1

Since $\left( \frac{p }{1 -p } \right)^x $ is an exponentially decaying function about $x$ (because $p > 1/2$), we can take the saddle point approximation in the sum. The largest term in the sum is at $x = 0$. It will dominate the sum, hence \begin{equation} f(t) = { 2t \choose t + x} [p ( 1- p)]^{ t} \sim [p ( 1- p)]^{ t} 2^{2t} \frac{1}{\sqrt{2t}} \end{equation} which implies \begin{equation} \alpha = - \ln [4p( 1- p) ] > 0 \end{equation}

This should be the correct answer, because \begin{equation} \frac{f(t)}{[p ( 1- p)]^{ t} 4^t} = {}_2 F_1 [1, -t, 1+t, \frac{p}{p - 1}] \end{equation} We can plot the hypergeometric function and find that its large $t$ values seem to converge to a constant.

2

We consider a random walk $X_t$ with the probability $p$ of going right and $1 - p$ of going left, then \begin{equation} f(t) = \text{Pr}( X_{2t} \ge 0 ) = 1 - \text{Pr}( X_{2t} < 0 ) \end{equation}

In the large $t$ limit, the central limit theorem implies that the 2nd term will converge to the CDF of a Gaussian function with \begin{equation} \mu = 2t [p - ( 1 - p )] \quad \sigma^2 = 2t ( 1 - (2p-1)^2 ) = 2t 4p ( 1- p) \end{equation} Therefore \begin{equation} f(t) \sim \int_0^{\infty} dx e^{-\frac{( x- \mu)^2}{2 \sigma^2}}\frac{1}{\sqrt{2\pi} \sigma} = \frac{1}{2}( 1 + \text{erf}( \frac{\mu}{\sqrt{2} \sigma} ) ) \end{equation} According to Wikipedia, we can approximate the error function by \begin{equation} \text{erf}(x) \sim \text{sgn}(x) \sqrt{ 1 - e^{ -x^2 } } \end{equation} when $|x| \gg 0$.

With this we have \begin{equation} f(t) \sim \frac{1}{2} ( 1 + \sqrt{ 1 - e^{ - \frac{\mu^2}{2 \sigma^2}}} ) \sim \frac{1}{4} e^{ - \frac{\mu^2}{2 \sigma^2}} \end{equation} Then \begin{equation} \alpha \stackrel{?}{=} \frac{\mu^2}{2 \sigma^2 t} = \frac{( 1 - 2p)^2}{4p ( 1- p) } \end{equation}

Questions

Why the 2nd approach does not give the correct asymptotic behavior?

My guess is that the central limit theorem only provides convergence to the scaled variable $X_t / \sqrt{t}$, not the distribution of $X_t$ itself.

Is it possible to fix the 2nd approach?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.