This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
world:random-walk [2020/04/22 18:35] rdouc [Other method] |
world:random-walk [2023/04/18 14:58] (current) rdouc [Statement] |
||
---|---|---|---|
Line 4: | Line 4: | ||
<WRAP center round box 80%> | <WRAP center round box 80%> | ||
- | Let $(U_i)$ be iid Rademacher random variables, i.e. $U_i=1$ or $-1$ with probability $1/2$ and set $S_i=\sum_{j=1}^iU_j$ the associated partial sum. Define $\Delta=\inf\set{t>0}{S_t=0}$. Show that $S_n$ returns to 0 with probability one. What is the law of $\Delta$? | + | Let $(U_i)$ be iid Rademacher random variables, i.e. $U_i=1$ or $-1$ with probability $1/2$ and set $S_i=\sum_{j=1}^iU_j$ the associated partial sum. Define $\Delta=\inf\set{t>0}{S_t=0}$. Show that $S_n$ returns to $0$ with probability one. What is the law of $\Delta$? |
</WRAP> | </WRAP> | ||
Line 46: | Line 46: | ||
====== Other method ====== | ====== Other method ====== | ||
- | Note that, setting $U_i$ such that $X_i=2U_i-1$, we have $\PP(S_{2n}=0)=\PP(\sum_{i=1}^{2n} U_i=n)=\frac{(2n)!}{(n!)^2} \lr{\frac14}^n \sim \frac{1}{\sqrt{n\pi}}$ where we have used the Stirling equivalence. This implies that | + | Note that, setting $U_i$ such that $X_i=2U_i-1$, we have that $(U_i)$ are iid Bernoulli random variables with success probability $1/2$. Then, $\PP(S_{2n}=0)=\PP(\sum_{i=1}^{2n} U_i=n)=\frac{(2n)!}{(n!)^2} \lr{\frac14}^{2n} \sim \frac{1}{\sqrt{n\pi}}$ where we have used the Stirling equivalence. This implies that |
\begin{equation} | \begin{equation} | ||
\label{eq:one} | \label{eq:one} | ||
Line 63: | Line 63: | ||
\end{align*} | \end{align*} | ||
and by the induction assumption, we get $\PP(T^{k+1}<\infty)=\PP(T<\infty)^{k+1}$. | and by the induction assumption, we get $\PP(T^{k+1}<\infty)=\PP(T<\infty)^{k+1}$. | ||
- | Finally, plugging \eqref{eq:induc} into \eqref{eq:one}, we finally obtain: | + | Plugging \eqref{eq:induc} into \eqref{eq:one} yields |
$$ | $$ | ||
\infty=\sum_{k=1}^\infty \PP(T<\infty)^k | \infty=\sum_{k=1}^\infty \PP(T<\infty)^k | ||
$$ | $$ | ||
Since $\PP(T<\infty) \in[0,1]$, this implies that $\PP(T<\infty)=1$. | Since $\PP(T<\infty) \in[0,1]$, this implies that $\PP(T<\infty)=1$. |