# Central limit theorem for biased random walk

Define random variables $X_n$ by $X_0 = 0$ and \begin{equation*}X_n - X_{n-1} = \begin{cases} 1 & \text{with probability } g(X_{n-1}) \\ 0 & \text{with probability } 1-g(X_{n-1}) \end{cases} \end{equation*} for some function $g:\mathbb{N}_{\geq 0} \rightarrow [0, 1]$. Assume further that $g(n)$ converges to $0$ ''fast enough'' (e.g. $g(n) = O(1/n)$). Is there any simple way to apply one of the existing Central Limit Theorems to prove that the $X_n$ (after a proper normalization) converge to a normal distribution? What about uniform convergence?

I have been able to approximate the probability function well enough in the case $g(n) = 1/n^d, d \in \mathbb{N}$, to prove the uniform convergence result directly, but I feel this should be widely known.

• Did you want $X_n-X_{n-1}=\pm 1$. Your $X_n$ looks like it will have $X_n\approx n$ and shouldn't have Gaussian behaviour. – Anthony Quas May 4 '15 at 15:29
• @Anthony Quas: I think you can get quite different behavior if you allow large biases near the unbiased mean. That looks like a different but also interesting question. – Douglas Zare May 4 '15 at 16:01
• @Anthony Quas: There is no typo. The condition $g(n) \rightarrow 0$ makes the $X_n$ have a tendency to accumulate. In the case $g(n) = 1/n^d$ one has $E(X_n) \rightarrow +\infty$, but still after normalization it seems to converge to a normal distribution. – Lazward May 4 '15 at 16:45
• If $g(n)$ decays too quickly the variance of $X_n$ fluctuates between 0 and 1/4 and there's no convergence after normalization. – Ori Gurel-Gurevich May 4 '15 at 20:25
• @Lazward: If $g(x)$ decays very rapidly, then for large $n$, there will be some nonrandom $x(n)$ so that with probability close to $1$, $|X_n - x(n)| \in \lbrace 0, 1 \rbrace$. Suppose $g(0) = 1/2, g(1) = 1/1000, g(2) = 1/10^6$. Then typical behavior is to spend a short time at $0$, then hundreds to thousands of steps at $1$, then hundreds of thousands to millions of steps at $2$. For $n \approx 10, ~p(X_n = 1) \approx 1$. For $n \approx 1000 \log 2, p(X_n=1) \approx p(x_n = 2) \approx 1/2.$ Rescaling by the standard deviation does not make a shifted Bernoulli look normal. – Douglas Zare May 8 '15 at 16:54

You can try using the Lindberg-Feller CLT by going through the hitting times of the process. That is, let $T_N = \min \{n\geq 0: X_n = N\}$ be the time it takes for the walk to move $N$ steps to the right. If $\tau_k = T_k - T_{k-1}$ is the time it takes to go from $k-1$ to $k$, then $\tau_k$ is a Geometric($g(k-1)$) random variable. Since $T_n = \sum_{k=1}^n \tau_k$ and $\{\tau_k\}_{k\geq 1}$ are independent you can try applying the Lindberg-Feller CLT.
For specificity, suppose that $g(k-1) = 1/k$. Then, $E[\tau_k] = k$ and $Var(\tau_k) = k^2-k$. From this, we get that $E[T_n] = (n^2+n)/2$ and $Var(\tau_k) = \sum_{k=1}^n (k^2-k) \sim n^3/3$. From this, one suspects that $$\lim_{n\rightarrow \infty} P\left( \frac{T_n - \frac{n^2}{2}}{ \frac{1}{\sqrt{3}} n^{3/2}} \leq t \right) = \Phi(t) = \int_{-\infty}^t \frac{1}{\sqrt{2\pi}} e^{-z^2/2} dz.$$ To verify this, one needs to check the conditions of the Lindberg-Feller CLT. In particular, in this example you need to check that $$\lim_{n\rightarrow\infty} \frac{1}{n^3} \sum_{k=1}^n E[ \tau_k^2 \mathbf{1}_{|\tau_k - k| > \epsilon n^{3/2}} ] = 0, \qquad \forall \epsilon >0.$$ It's somewhat tedious, but I was able to verify this for the case $g(k-1) = 1/k$.
If the above approach works to get Gaussian limits for the hitting times, you can then try to "invert time and space" to get Gaussian limits for the position of the walk. For instance, in the case $g(k-1) = 1/k$ you can get $$\lim_{n\rightarrow\infty} P\left( \frac{X_n - \sqrt{2n}}{\frac{2^{1/4}}{\sqrt{3}} n^{1/4} } < t \right) = \Phi(t).$$ To see this, note that $$P\left( \frac{X_n - \sqrt{2n}}{\frac{2^{1/4}}{\sqrt{3}} n^{1/4} } < t \right) = P\left(X_n < \sqrt{2n} + \frac{t 2^{1/4} n^{1/4}}{\sqrt{3}} \right) = P\left(T_{ \lceil \sqrt{2n} + \frac{t 2^{1/4} n^{1/4}}{\sqrt{3}} \rceil } > n \right),$$ then recenter and scale the probabilities on the right to apply the Gaussian limits for the hitting times.
As Ori suggested in the comments above, I think that you don't get Gaussian limits when $g(n)$ decays too quickly. For instance, if $g(n)$ decays exponentially fast, then $E[\tau_k]$ grows exponentially fast. In this case $T_n = \sum_{k=1}^n \tau_k$ is essentially determined by the last few terms in the sum. However, to get Gaussian limits from the Lindberg-Feller CLT you need that none of the terms in the sum contributes much to the distribution of the sum.
• Regarding "uniform convergence," it's known that if $P(Z_n \leq t) \rightarrow \Phi(t)$ for every fixed $t \in \mathbb{R}$, then in fact the convergence is uniform in $t$. That is, $$\lim_{n\rightarrow\infty} \sup_{t \in \mathbb{R}} \left|P(Z_n \leq t) - \Phi(t) \right| = 0.$$ This follows from the fact that the distribution function $\Phi$ for a normal distribution is continuous and that all distribution functions are non-decreasing. – Jon Peterson May 8 '15 at 15:44