1

A simple random walk on the integers can be described as follows . At each time unit, a walker flips a fair coin and moves one step to the right or one step to the left depending on whether the coin comes up heads or tails. Let $S_n$ denote the position of the walker at time $n$. Suppose he starts at position 0. Then it can be shown through some involved computations that

$\lim_{n \rightarrow \infty} \mathbb{P} \{a \sqrt{2n} \leq S_{2n} \leq b \sqrt{2n} \} = \frac{1}{\sqrt{2 \pi}} \int_{a}^{b} e^{-x^2}dx$.

An alternative approach would be to use Polyas method, let $k$ be an integer

$\mathbb{P}\{S_{2n}=2k \}= \frac{1}{2 \pi}\int_{0}^{2 \pi}\cos(x)^{2n} e^{-2i xk} dx$

Then,

$\lim_{n \rightarrow \infty} \mathbb{P} \{a \sqrt{2n} \leq S_{2n} \leq b \sqrt{2n} \} = \lim_{n \rightarrow \infty} \sum_{a \sqrt{2n} \leq 2k \leq b \sqrt{2n} } \frac{1}{2 \pi}\int_{0}^{2 \pi}\cos(x)^{2n} e^{-2i xk}dx $

How could one calculate the limit of the RHS of the above equation and show it is equal $\frac{1}{\sqrt{2 \pi}} \int_{a}^{b} e^{-x^2}dx$.

user132
  • 56
  • I think you have some minor indexing error, since your second indented equation and your third don't agree with each other in the role of $k$. – Ian Oct 22 '21 at 18:38
  • In any case I think you can do stationary phase to get an asymptotic expansion of that integral for large $k$. – Ian Oct 22 '21 at 18:42
  • What does stationary phase mean? :) – user132 Oct 22 '21 at 18:43
  • More specifically I should describe it as steepest descent. Go from $0$ to $-iR$ to $2\pi-iR$ to $2\pi$ in the complex plane where $R$ is a large positive "tuning parameter", the overall integral over the whole path is the same, the integral from $-iR$ to $2\pi-iR$ is essentially zero because of the $e^{-R}$, and then you should be able to use Laplace's method on the vertical pieces. Maybe something nice comes of this? I'm not sure. Try it. – Ian Oct 22 '21 at 18:58
  • Sorry that way won't actually work, because actually $n$ is the bigger number not $k$, so you need to find a path where $|\cos(z)|$ is small a lot. – Ian Oct 22 '21 at 19:40

0 Answers0