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.
 A: 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. 
