%%% Title of object: Random Walk
%%% Canonical Name: RandomWalk
%%% Type: Topic
%%% Created on: 2010-09-03 23:52:57
%%% Modified on: 2010-11-03 23:02:21
%%% Creator: rabi
%%% Modifier: rabi
%%% Author: rabi
%%% Author: jkimmel
%%% Author: tliggett
%%%
%%% Classification: msc:60G50
%%% Keywords: Sums of independent increments, CLT, Brownian motion
%%% Preamble:
\documentclass[10pt]{article}
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
%%% Content:
\begin{document}
\begin{center}
\textbf{Random Walk}\\
\end{center}
\begin{center}
Rabi Bhattacharya, The University of Arizona, USA
\end{center}
\par The simple random walk $\{S_n: n=0,1,...\}$, starting at an integer $x$, is a stochastic process on the integers, given by $S_0=x$, $S_n = x +X_1+...+X_n (n\geq1)$, where $X_n, n\geq1$, is an independent Bernoulli sequence: $P(X_n=1) =p$, $P(X_n=-1) =1-p =q$, $0c$, with probability one. By symmetry, it will reach every state with probability one. Iterating this argument one sees that, with probability one, the symmetric random walk visits
every state infinitely often. That is, the walk is \emph{recurrent}. For the asymmetric walk, the solution to $(1)$ is $\pi(x) = (1-(p/q)^{d-x})/ (1-(p/q)^{d-c})$. If $p<1/2$, then the limit of this is $1$ as $d\rightarrow \infty$ and, with probability one, the random walk will visit $c$, starting from $x>c$. On the other hand, if $p>1/2$, then $\pi(x)\rightarrow(q/p)^{x-c} <1$, as $d\rightarrow \infty$. The probability of ever reaching $d$, starting from $x1/2$ and $(p/q)^{d-x}$ if $p<1/2$. The asymmetric simple random walk is thus \emph{transient}. Indeed, it follows from the strong law of large numbers (\emph{SLLN}) that if $p>1/2$, then $S_n\rightarrow \infty$ with probability one as $n\rightarrow \infty$; and $S_n \rightarrow - \infty$, with probability one, if $p<1/2$. For these and other properties of the random walk, such as those described below, see Feller (1968), Chapter 3, Bhattacharya and Waymire (2009), Chapter 1, or Durrett (1995), Chapter 3. For additional information, refer to Billingsley (1968), and Spitzer (1964).\\
\par For computation of various probabilities associated with a simple random walk, the following
result proved by D. Andre in 1887 is very useful: Consider the polygonal path of the random walk joining successive points $(j,S_j)$, $(j+1,S_{j+1})$ $(j=0,1,...,n-1)$ by line segments. Let $y>0$. Then (a) the set of paths from $(0,0)$ to $(n,y-1)$ ($n$ and $y-1$ of the same parity) which touch or cross the level $y$, is in one-one correspondence with (b) the set of all paths from $(0,0)$ to $(n,y+1)$ (\emph{Reflection principle}). To prove this, let $\tau$ be the first time a path of the type (a) touches the level $y$ prior to time $n$. Then replace the segment of the path from $(\tau,y)$ to $(n,y-1)$ by its mirror reflection about the level $y$. This gives a path of the type (b). Conversely, given any path of the type (b), reflect about y the segment of the path from $(\tau,y)$ to $(n,y+1)$. This gives a path of the type (a). Here is an application of this principle.\\
\par \textbf{Example 1 } (First passage time distribution of a simple
random walk). Let $y$ be a positive integer, and $F_{n,y}$ the event
that the random walk, starting at zero, reaches $y$ for the first time
at time $n$, i.e., $F_{n,y}= \{ S_j\neq y, \text{for}\; 0\leq j0$, was obtained by Le'vy (1925): $ n^{-1/2}(X_1+...+X_n)$ converges in distribution to the normal distribution $N(0, \sigma^2)$ with mean zero and variance $\sigma^2$, as $n\rightarrow \infty$. In physical terms, this result says the following: if time and length are rescaled so that in one unit of rescaled time there are a large number n of i.i.d. displacements of small rescaled lengths of order $1/\sqrt{n}$, then the random walk displacements over a period of time t will appear as Gaussian with mean zero and variance $t\sigma^2$, the increments over disjoint intervals being independent. That such a Gaussian process exists with continuous sample paths was proved rigorously by N.Wiener in 1923. This process is called the \emph{Brownian motion}, following its implicit use by A. Einstein in 1905-6 to describe the kinetic motion of colloidal molecules in a liquid, experimentally observed earlier by the botanist R. Brown. Interestingly, even before Einstein, Bachelier (1900) described the random movements of stocks by this Gaussian process. The statement that the rescaled random walk $S_n (n=0,1,2,...)$ converges in distribution to Brownian motion was proved rigorously by M. Donsker in 1951, and this result is known as the functional central limit theorem (\emph{FCLT}). Both the\emph{CLT} and the \emph{FCLT} extend to arbitrary dimensions d.\\
\par As consequences of the \emph{FCLT}, one can derive many asymptotic results for the simple symmetric random walk given by the corresponding result for the limiting Brownian motion. Conversely, by
evaluating combinatorially some probability associated with the random walk, one may derive the corresponding probability for the Brownian motion. A Brownian motion with variance parameter $\sigma^2 =1$ is called a standard Brownian motion, and denoted $\{B_t:t\geq0\}$ below.\\
\par \textbf{Example 2} (Boundary hitting probability of Brownian motion). Let $c\leq x\leq d$ be arbitrary reals. Then, using the corresponding result for the scaled random walk, one obtains
\begin{equation}
P(\{B_t:t\geq 0\}\text{ reaches c before $ d \mid B_0=x) = (d-x)/(d-c$}).
\end{equation}
\textbf{ Example 3} (Arcsine law). Let $U$ denote the amount of time in $[0,1]$ the Brownian motion spends above zero, i.e., $ U=$ Lebesgue measure of the set $\{t: 0\leq t\leq 1: B_t>0\}$, given $B_0 =0$. Consider the polygonal path of the simple symmetric random walk $S_j (j=0,1,...n)$, starting at zero. By combinatorial arguments, such as the reflection principle, one can calculate exactly the proportion of times the polygonal path lies above zero and, by the \emph{FCLT}, this yields
\begin{equation}
P(U \leq x ) = (2/\pi) sin^{-1}\sqrt{x} \text{ ($0\leq x\leq 1$)}.
\end{equation}
\textbf{REFERENCES}\\
Bachelier, L. (1900). The'orie de la speculation. \emph{Ann. Sci. Ecole Norm. Sup.} \textbf{17}, 21-86.\\
Bhattacharya, R.N. and Waymire, E.C. (2009).\emph{Stochastic Processes with Applications.} SIAM
Classics in Applied Mathematics, vol. 61. SIAM, Philadelphia.\\
Billingsley, P. (1968).\emph{ Convergence of Probability Measures}. Wiley, New York.\\
De Moivre, A. (1756). \emph{Doctrine of Chance}. London.\\
Durrett, R. (1995). \emph{Probability: Theory and Examples}. 2nd edition. Duxbury, Belmont.\\
Feller, W. (1968).\emph{ An Introduction to Probability Theory and Its Applications}. Vol.1. 3rd edition. Wiley, New York.\\
Laplace, P.S. (1812). \emph{The The'orie Analitique des Probabilite's}. Paris.\\
Le'vy, P. (1925). \emph{Calcul des Probabilite's}. Gauthier-Villars. Paris.\\
Spitzer, F. (1964). \emph{Principles of Random Walk}. Van Nostrand. Princeton, NJ.\\
\footnotetext[1]{Reprinted with permission from Lovric, Miodrag (2011), International Encyclopedia of Statistical Science. Heidelberg: Springer Science+Business Media, LLC}
\end{document}