April 25, 2024
Flip a coin and move one step right if heads or one step left if tails. Or up and down instead of right and left. Or swap the directives of heads and tails.
The possible outcomes of repeatedly flipping a coin are described by the sample space \Omega = \{H,T\}^\bm{N}, where \bm{N}= \{0, 1, 2, \ldots\} is the set of natural numbers, consisting of all functions \omega\colon\bm{N}\to\Omega. The outcome of the n-th flip is \omega(n)\in\{H,T\} for n\in\bm{N}.
Given n initial flips \omega_n\in\{H,T\}^n let A_{\omega_n} be the elements \omega\in\Omega starting with \omega_n, \omega(k) = \omega_n(k) for k < n. The probability of A_{\omega_n} occuring is 1/2^n for each \omega_n. Let \mathcal{A}_n = \{A_{\omega_n}:\omega_n\in\{H,T\}^n\}.
Exercise. Show \mathcal{A}_n is a partition of \Omega.
Hint: A partition of a set is …
We are assuming the coin is fair so the probabitly of either heads or tails is 1/2. If the probability of heads is p (so the probability of tails is 1 - p) then the probability of A_{\omega_n} = p^h(1 - p)^t where h is the number of heads in \omega_n and t = n - h is the number of tails.
To turn coin flips into a stochastic process define a function V\colon\{H,T\}\to\bm{R}. This determines a random walk W\colon \bm{N}\times\Omega\to\bm{R} by W(n,\omega) = \sum_{0\le k < n} V(\omega(k)). We also write W_n(\omega) = W(n, \omega). Note W_n(\omega) only depends only on the first n values of \omega. Such processes are called adapted.
Typical choices for V are V(H) = 1 and V(T) = 0 or V(H) = 1 and V(T) = -1. We could also choose V(H) = 0 and V(T) = 1 or V(H) = -1 and V(T) = 1 to get processes with the same law if the coin is fair. Let’s call the first case standard random walk, or just random walk, and the second symmetric random walk.
Exercise. Show E[W_n] = 0 and \operatorname{Var}(W_n) = n if W is a symmetric (fair) random walk.
Hint: E[V] = 0 and \operatorname{Var}(V) = 1.
Exercise. If W is a (standard) random walk then P(W_n = k) = \binom{n}{k}/2^n.
Hint: W_n(\omega) = k if the first n elements of \omega has k 1’s and n - k 0’s. Recall \binom{n}{k} = n!/(n - k)!k! is the number of ways to choose k (or n-k) elements from a set of n elements.
If x\colon\bm{N}\to\bm{R} define \Delta x\colon\bm{N}\to\bm{R} by \Delta x(n) = x(n + 1) - x(n). The difference equation \Delta x = \mu where \mu\colon\bm{N}\to\bm{R} has a unique solution given x(0) = x_0\in\bm{R}.
Exercise. Show x(n) = x_0 + \sum_{0\le k < n} \mu(n).
If W_n is a random walk and X_n\colon\Omega\to\bm{R} define \Delta X_n = \mu + \sigma\Delta W_n by
The stochastic difference equation \Delta X_n(\omega) = \mu(n, \omega) + \sigma(n, \omega) \Delta W_n(\omega), where W_n is a random walk, has a unique solution given X(0, \omega_9) = x_0\in\bm{R}.