Let $\left(Y_n\right)_{n \geq 1}$ a sequence of i.i.d random variables such that $\mathbb{P}\left(Y_1=1\right)=\mathbb{P}\left(Y_1=\right.$ $-1)=1 / 2$.
Define $S_0=0, \mathcal{F}_0=\{\Omega, \emptyset\}$ and for $n \geq 1, S_n=\sum_{k=1}^n Y_k$ et $\mathcal{F}_n=\sigma\left(Y_1, \cdots, Y_n\right)$.
Define for $x \in \mathbb{Z}, \tau_x=\inf \left\{n \geq 0: S_n=x\right\}$.
- Show that $\tau_x$ is a stopping time that verifies $\mathbb{P}\left(\tau_x<\infty\right)=1$. (Use the Stirling formula : $n ! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$)
Attempt :
I) The event $\left\{\tau_x=n\right\}$ is defined as the moment where the partial sum $S_n$ eaches the value $x$ for the first time exactly at the time $n$. This can be expressed in terms of the random variables $Y_1, \ldots, Y_n$ that are all mesurable with respect à $F_n$. Thus, we have: $$ \left\{\tau_x=n\right\}=\bigcap_{k=1}^{n-1}\left\{S_k \neq x\right\} \cap\left\{S_n=x\right\} $$
$\{S_n=x\}$ is $\mathcal{F}_n$-mesurable because $S_n$ is the sum of $Y_1,...,Y_n$ that are all $\mathcal{F}_n$-mesurable.
$\bigcap_{k=1}^{n-1}\left\{S_k \neq x\right\}$ is also in $\mathcal{F}_n$ as an intersections of elements of $\mathcal{F}_n$ since $k<n$, each $S_k$ is $\mathcal{F}_n$-mesurable and $\mathcal{F}_n$ is a $\sigma$-algebra.
Thus we have $\left\{\tau_x=n\right\} \in \mathcal{F}_n$ so $\tau_x$ is a stopping time.
II)
$$P(\tau_x < \infty) = P(\{S_n=x\}) = P(\sum_{k=1}^{n} Y_k = x) = \binom{n}{\frac{n+x}{2}} \frac{1}{2}^{\frac{n+x}{2}} \frac{1}{2}^{\frac{n-x}{2}}$$
Using the Stirling approximation I find :
$$P(\tau_x < \infty) \sim \frac{\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n}{\sqrt{2 \pi \frac{n+x}{2}}\left(\frac{n+x}{2e}\right)^{\frac{n+x}{2}} \sqrt{2 \pi \frac{n-x}{2}}\left(\frac{n-x}{2e}\right)^{\frac{n-x}{2}}} (\frac{1}{2})^n $$
EDIT : Simplifying :
$$P(\tau_x < \infty) \sim \frac{\sqrt{2 \pi n}}{\sqrt{2 \pi \frac{n+x}{2}}\left(\frac{n+x}{2e}\right)^{\frac{n+x}{2}} \sqrt{2 \pi \frac{n-x}{2}}\left(\frac{n-x}{2e}\right)^{\frac{n-x}{2}}} (\frac{1}{2})^n \left(\frac{n}{e}\right)^n $$
reducing $\sqrt{2 \pi}$ and 2 in the denominator:
$$P(\tau_x < \infty) \sim \frac{\sqrt{n}}{ \sqrt{\pi} \sqrt{ \frac{n+x}{2}}\left(\frac{n+x}{2e}\right)^{\frac{n+x}{2}} \sqrt{n-x}\left(\frac{n-x}{2e}\right)^{\frac{n-x}{2}}} (\frac{1}{2^n}) \left(\frac{n^n}{e^n}\right) $$
factoring $\frac{1}{2}$ and $\frac{1}{e}$ in the denominator :
$$P(\tau_x < \infty) \sim \frac{\sqrt{n}}{ \sqrt{\pi} \sqrt{n+x}\left(n+x\right)^{\frac{n+x}{2}} \sqrt{n-x}\left(n-x\right)^{\frac{n-x}{2}} \sqrt{\frac{1}{2}} (\frac{1}{2})^{\frac{n-x}{2} + \frac{n+x}{2}} (\frac{1}{e})^{\frac{n-x}{2} + \frac{n+x}{2}}} (\frac{1}{2^n}) \left(\frac{n^n}{e^n}\right) $$
Finally reducing $\frac{1}{2}$ and $\frac{1}{e}$ :
$$ P(\tau_x < \infty) \sim \frac{\sqrt{2} n^{n+\frac{1}{2}}}{ \sqrt{\pi} (n+x)^{\frac{n+x+1}{2}} (n-x)^\frac{n-x+1}{2}}$$
This doesn't look like 1 when n is large. Any help will be much appreciated. Thank you.
Consider $x=0$. Using Stirling's approximation you find
$$P(S_{2m}=0)=\binom{2m}{m}2^{-2m}\sim \frac{1}{\sqrt{\pi m}},$$
which yields
$$\sum_{m=0}^\infty P(S_{m}=0)= \infty.$$
Define
$$\tau_{0}^{(m)}:=\inf\{m>\tau_{0}^{(m-1)}: S_m=0\}$$
and use the Markov property to find $P(\tau_{0}^{(m)}<\infty)= P(\tau_0<\infty)^m$.
Then,
$$ \begin{aligned} \sum_{m=0}^\infty P(S_{m}=0) &=E\big[\sum_{m=0}^\infty 1_{\{S_{m}=0\}}\big]\\ &=E\big[\sum_{m=0}^\infty 1_{\{\tau_{0}^{(m)}<\infty\}}\big]\\ &=\sum_{m=0}^\infty P(\tau_{0}^{(m)}<\infty)\\ &=\sum_{m=0}^\infty P(\tau_0<\infty)^m\\ &= \frac{1}{1-P(\tau_0<\infty)}, \end{aligned}$$
which implies $P(\tau_0<\infty)=1$.
For $x\ne 0$ the asymptotic behaviour
$$P(S_{2m}=x)\sim \frac{1}{\sqrt{\pi m}}$$
is still true, but from my impression it should hold
$$P(\tau_{x}^{(m)}<\infty)= P(\tau_x<\infty)P(\tau_0<\infty)^{m-1}?$$
In this case, I'm not quite sure, if the proof goes through like above.