Ariss

A model for random walk has sample space {\Omega = [0, 1)}. The base 2 expansion of {\omega\in\Omega} is {\omega = \sum_{i>0} \omega_i/2^i} where {\omega_i\in\{0,1\}}. Let {A_{j,n} = [j/2^n, (j + 1)/2^n)} and {\mathcal{A}_n = \{A_{j,n}\mid 0\le j < 2^n\}}.

Exercise. Show \cup_{0\le j < 2^n} A_{j,n} = [0, 1).

Hint: If \omega\in [0, 1) then there exists an integer j with {j\le\omega 2^n < j + 1} and {0\le j < 2^n}. This shows \omega\in A_{j,n}. We can also write this as j = \lfloor \omega 2^n\rfloor, the greatest integer less than or equal to \omega 2^n.

Exercise. Show A_{j,n}\cap A_{k,n} = \emptyset if j\not=k.

Hint: Consider j < k.

This shows \mathcal{A}_n is a partition of \Omega = [0, 1). A partition is used to represent partial information. Full information is knowing \omega\in\Omega. Partial information is knowing only which atom \omega belongs to.

Define X_n\colon\Omega\to\{0,1\} by X_n(\omega) = \omega_n, to be the n-th digit in the base 2 representation of \omega.

Exercise. Show X_1(\omega) = 1_{[1/2,1)}.

Exercise. Show X_n is constant on each atom A_{j,n}, 0\le j < n.

This implies X_n is measurable with respect to the smallest algebra of sets generated by the atoms of \mathcal{A}_n, but we prefer this simple definition. Since X_n is constant on atoms it is a function X_n\colon\mathcal{A}_n\to\bm{R}. This is useful for computer implementation.

Let Y_n = 2X_n - 1 so Y_n = 1 when X_n = 1 and Y_n = -1 when X_n = 0. Random walk is the stochastic process W_n = Y_1 + \cdots + Y_n.

Exercise. Show E[W_n] = 0 and \operatorname{Var}(W_n) = n.

Let B_{t,n} = W_{\lfloor tn\rfloor}/\sqrt{n}.

Exercise. Show \operatorname{Var}(B_{t,n}) \to t as n\to\infty.

Hint: \operatorname{Var}(B_{t,n}) = \lfloor tn\rfloor.

Brownian motion B_t is the limit as n\to\infty of B_{t,n}.