world:random-walk
Differences
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:36] 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 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}^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$. | ||
world/random-walk.1587573404.txt.gz · Last modified: 2022/03/16 01:37 (external edit)
Page Tools
