> [!definition] > > $ > \begin{align*} > R_{j} = {-1, 1} &\quad p(-1) = p(1) = \frac{1}{2} \\ > \ev{(X)} = 0 &\quad \var{X} = 1^2 \times 0.5 + (-1)^2 \times 0.5 = 1 \\ > S(n) &= X_{1} + X_{2} + \cdots X_{n} \\ > R_{S(n)} &= \{-n, -n + 2, ..., n - 2, n\}\\ > \ev{(S(n))} = 0 &\quad \var{S(n)} = n > \end{align*} > $ > A simple random walk is a [[Random Walk|random walk]] with $p = q = 0.5$. > [!theorem] [[Probability]] of landing on a position $x$ after $n$ steps > > $ > P(S(n) = x) = {n \choose (n + x)/2}\paren{\frac{1}{2}}^n > $ > > *Proof*. > > Consider $(X_j = 1)$ as a "success" and $(X_j = -1)$ as a "failure". > $ > P(S(n) = x) = P(\mathrm{successes - failures} = x) > $ > Since successes and failures also add up to the number of steps $n$, setup the following [[Linear System|linear system]] and solve: > $ > \begin{align*} > \mathrm{successes + failures} = n \\ > \mathrm{successes - failures} = x \\ > \mathrm{successes} = \frac{n + x}{2} \\ > \mathrm{failures} = \frac{n - x}{2} > \end{align*} > $ > > Convert the problem into calculating the probability of $x$ successes in $n$ attempts and use the [[Binomial Random Variable|binomial distribution]]: > $ > \begin{align*} > P(\mathrm{successes - failures} = x) &= P\paren{\mathrm{successes} = \frac{n + x}{2}} \\ > &= P\paren{B\paren{n, \frac{1}{2}} = \frac{n + x}{2}} \\ > &= {n \choose (n + x)/2}\paren{\frac{1}{2}}^n > \end{align*} > $