Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466
Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar
__________________________________________________________________________
Positive Walks
_______________________________________________________________________
Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.
_______________________________________________________________________________________________
Mathematicians Only: prolonged scenes of intense rigor.
_______________________________________________________________________________________________
How many random walks with $6$ steps are there? Among those walks, how many are positive for all $6$ steps? How many are non-negative for all $6$ steps?
_______________________________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
Recall that ${Y}_{i}$ is a sequence of independent random variables which take values $1$ with probability $1\u22152$ and $-1$ with probability $1\u22152$. This is a mathematical model of a fair coin ﬂip game where a $1$ results from “heads” on the $i$th coin toss and a $-1$ results from “tails”. Let ${H}_{n}$ and ${L}_{n}$ be the number of heads and tails respectively in $n$ ﬂips. Then ${T}_{n}={\sum}_{i=1}^{n}{Y}_{i}={H}_{n}-{L}_{n}=2{S}_{n}-n$ counts the diﬀerence between the number of heads and tails, an excess of heads if positive.
A common interpretation of this probability game is to imagine it as a random walk. That is, we imagine an individual on a number line, starting at some position ${T}_{0}$. The person takes a step to the right to ${T}_{0}+1$ with probability $p$ and takes a step to the left to ${T}_{0}-1$ with probability $q$ and continues this random process. Then instead of the total fortune at any time, we consider the geometric position on the line at any time.
Create a common graphical representation of the game. A continuous piecewise linear curve in ${\mathbb{R}}^{2}$ consisting of a ﬁnite union of segments of the form $\left[\left(i,j\right),\left(i+1,j+1\right)\right]$ or $\left[\left(i,j\right),\left(i+1,j-1\right)\right]$ where $i,j$ are integers is called a path. A path has an origin $\left(a,b\right)$ and an endpoint $\left(c,d\right)$ which are points on the curve with integer coordinates satisfying $a\le i\le c$ for all $\left(i,j\right)$ on the curve. We will say the length of the path is $c-a$. (Note that the Euclidean length of the path is $\left(c-a\right)\sqrt{2}$.) To each element $\omega \in {\Omega}_{n}$ (see Binomial Distribution.), we associate a path ${\bigcup}_{k=0}^{n-1}\left[\left(i,{T}_{i}\left(\omega \right)\right),\left(i+1,{T}_{i+1}\left(\omega \right)\right)\right]$ with origin $\left(0,0\right)$ and endpoint $\left(n,{T}_{n}\left(\omega \right)\right)$.
If $c$ and $d$ are two integers such that $0\le \left|d\right|\le c$ then the number of paths with origin $\left(0,0\right)$ and endpoint $\left(c,d\right)$ is zero if $c+d$ is odd and $\left(\genfrac{}{}{0.0pt}{}{c}{\left(c+d\right)\u22152}\right)$ if $c+d$ is even. More generally, if $a$, $b$, $c$ and $d$ are integers such that $0\le |d-b|\le c-a$ and $c-a+d-b$ is even, then the number of paths with origin $\left(a,b\right)$ and endpoint $\left(c,d\right)$ is $\left(\genfrac{}{}{0.0pt}{}{c-a}{\left(c-a+b-d\right)\u22152}\right)$.
Proposition 1 (Reﬂection Principle for Paths). Let $a,b\ge 0$ and $n>0$ be integers. Then
Proof. The case $a=0$ is trivial, so suppose $a>0$. The proof will establish a one-to-one correspondence between paths with origin $\left(0,0\right)$ and endpoint $\left(n,b-a\right)$ that cross the horizontal line $y=-a$ with paths with origin $\left(0,0\right)$ and endpoint $\left(n,a+b\right)$. Translating each path of the ﬁrst type up by $a$ units, this is equivalent to showing that the number of paths with origin $\left(0,a\right)$ and endpoint $\left(n,b\right)$ crossing the $x$-axis (call these paths of the ﬁrst type) equals the number of paths with origin $\left(0,-a\right)$ and endpoint $\left(n,b\right)$ (call these paths of the second type). If $C$ is a path of the ﬁrst type, set $t\left(C\right)$ to be the smallest $i>0$ such that $\left(i,0\right)\in C$. The path $C$ is a union of a path ${C}_{1}$ with origin $\left(0,0\right)$ and endpoint $\left(t\left(C\right),0\right)$ and a path ${C}_{2}$ with origin $\left(t\left(C\right),0\right)$ and endpoint $\left(n,b\right)$. Then to each $C$, we associate the path ${C}^{\prime}$ that is the union of ${C}_{2}$ with the reﬂection of ${C}_{1}$ across the $x$-axis. The path ${C}^{\prime}$ is a path of the second type and the correspondence $C\leftrightarrow {C}^{\prime}$is one-to-one between the two sets of paths of each of the two types. □
Remark. The probability the random walk will end at $\left(0,0\right)$ after $2n$ steps is
This is also the probability that in a coin-tossing game, the players will be tied at the end of $n$ tosses. The next corollary shows that this is double the probability that the walk remains positive for all $2n$ steps, or equivalently that the Heads player in the coin-tossing game is always ahead.
Theorem 2 (Positive Walks Theorem).
Proof. Count the paths with origin $\left(0,0\right)$ and length $2n$ strictly contained in the upper half plane. To obtain this, sum the number of paths from $\left(1,1\right)$ to $\left(2n,2k\right)$ that do not touch the $x$-axis. There is only one path that connects the point $\left(1,1\right)$ to the point $\left(2n,2n\right)$ and this path does not return to the $x$-axis. If $1\le k<n$, the number of paths connecting $\left(1,1\right)$ to the point $\left(2n,2k\right)$ that do not return to the $x$-axis equals the number of paths connecting $\left(1,1\right)$ to the point $\left(2n,2k\right)$ minus the number of paths that do return to the $x$-axis. The number of paths connecting $\left(1,1\right)$ to the point $\left(2n,2k\right)$ is $\left(\genfrac{}{}{0.0pt}{}{2n-1}{n+k-1}\right)$. By the reﬂection principle the number of paths connecting $\left(1,1\right)$ to the point $\left(2n,2k\right)$ that return to the $x$-axis equals the number of paths connecting the point $\left(1,-1\right)$ to the point $\left(2n,2k\right)$, which is $\left(\genfrac{}{}{0.0pt}{}{2n-1}{n+k}\right)$.
Therefore, the number of paths with origin $\left(0,0\right)$ and length $2n$ that are contained in the upper half-plane is
This sum telescopes to $\left(\genfrac{}{}{0.0pt}{}{2n-1}{n}\right)$ and
□
Remark. The probability the random walk will end at $\left(0,0\right)$ after $2n$ steps is
This is also the probability that in a coin-tossing game, the players will be tied at the end of $n$ tosses. The next corollary show that this also equals the probability that the walk remains nonnegative for all $2n$ steps, or that the losing player in the coin-tossing game is never ahead. Notice the diﬀerence between the previous corollary and the next corollary, the ﬁrst is about positive walks and the second is about nonnegative walks.
Theorem 3 (Non-Negative Walks Theorem).
Proof. The proof shows that
The claim is that the number of paths with origin $\left(0,0\right)$ and length $2n$ that are contained in the upper half plane with no return to the $x$-axis equals the number of paths with origin $\left(0,0\right)$ and length $2n-1$ that are contained in the upper half-plane including the $x$-axis. The claim is true because there is a bijection between the sets of these two types of paths: We associate a path of the second type to each path of the ﬁrst type by removing the initial segment and translating the path $1$ unit left and $1$ unit down.
Note that ${T}_{2n-1}$ is never zero. Then to each path with origin $\left(0,0\right)$ and length $2n-1$ that is contained in the upper half-plane including the $x$-axis, we can associate exactly two paths with length $\left(0,0\right)$ and length $2n$ that are contained in the upper half-plane. To do this, we add a segment of length $1$ and slope $1$ or $-1$ to the end of the path of length $2n-1$. Therefore, the cardinality of the event $\left\{{M}_{1}\ge 0,M2\ge 0,\dots ,{M}_{2n}\ge 0\right\}$ is twice the cardinality of the event $\left\{{M}_{1}>0,M2>0,\dots ,{M}_{2n}>0\right\}$. □
Remark. The ﬁnal corollary calculates the probability that one player is ahead until the last coin toss in the game, which ties the two players.
Proof. Count the paths with origin $\left(0,0\right)$ and endpoint $\left(2n,0\right)$ that are contained in the open upper half-plane which does not include the $x$-axis. In other words, count the paths with origin $\left(1,1\right)$ and endpoint $\left(2n-1,1\right)$ that are contained in the open upper half-plane. This number equals the number of paths with origin $\left(1,1\right)$ and endpoint $\left(2n-1,1\right)$ that touch the $x$-axis at some point. The number of paths with origin $\left(1,1\right)$ and endpoint $\left(2n-1,1\right)$ equals $\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-1}\right)$. By the reﬂection principle, the number of paths with origin $\left(1,1\right)$ and endpoint $\left(2n-1,1\right)$ that touch the $x$-axis equals the number of paths with origin $\left(1,-1\right)$ and endpoint $\left(2n-1,1\right)$. The number is $\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-2}\right)$. Finally, it is easy to check that
$$\begin{array}{llll}\hfill \left(\genfrac{}{}{0.0pt}{}{2n-2}{n-1}\right)-\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-2}\right)& =\frac{\left(2n-2\right)!}{\left(n-1\right)!\left(n-1\right)!}-\frac{\left(2n-2\right)!}{\left(n-2\right)!n!}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{n\left(2n-2\right)!-\left(n-1\right)\left(2n-2\right)!}{\left(n-1\right)!n!}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{n}\frac{\left(2n-2\right)!}{\left(n-1\right)!\left(n-1\right)!}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{n}\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-1}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$$ □Remark. The corollaries imply the following combinatorial identity.
Corollary 2. If $n$ and $k$ are integers with $0\le k\le n$, then
In particular,
Proof. Count the number of paths with origin $\left(0,0\right)$ and endpoint $\left(2n-k,k\right)$ in two diﬀerent ways. On one hand, the number of such paths is $\left(\genfrac{}{}{0.0pt}{}{2n-k}{n}\right)$. On the other hand, the number of paths equals the number of paths with origin $\left(1,1\right)$ and endpoint $\left(2n-k,k\right)$ plus the number of paths with origin $\left(1,-1\right)$ and endpoint $\left(2n-k,k\right)$. The number of paths with origin $\left(1,1\right)$ and endpoint $\left(2n-k,k\right)$ is $\left(\genfrac{}{}{0.0pt}{}{2n-k-1}{n-1}\right)$. Next, for every path with origin $\left(1,-1\right)$ and endpoint $\left(2n-k,k\right)$, there exists a minimum integer $1\le j\le n-k$ such that the path passes through $\left(2j,0\right)$. The number of paths from $1$ to $n-k$ is therefore equal to the sum for $j$ from $1$ to $n-k$ of the product of the number of paths with origin $\left(0,0\right)$ and endpoint $\left(2j,0\right)$ that are contained in the lower half-plane and the number of paths with origin $\left(2j,0\right)$ and endpoint $\left(2n-k,k\right)$. By the previous corollary, this implies the number of paths with endpoint $\left(1,-1\right)$ and endpoint $\left(2n-k,k\right)$ is
Considering all of the information above, we see that this equals
The second form follows from setting $k=0$ and using the fact that
□
Remark. Note that:
This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 10.3. [?].
_______________________________________________________________________________________________
The scripts generate $k$ trials of $n$-step random walks. Each random walk is the sequence of cumulative sums from a sequence of $n$ coin ﬂips, embedded in a $k\times n+1$ $0$ matrix walks to set the initial condition. Each random walk is examined for positive steps, creating a $k\times n+1$ Boolean matrix findposwalks. The rows of the $k\times n+1$ Boolean matrix are summed and rows with sum $n$ correspond to positive walks. Another comparison ﬁnds a Boolean vector poswalks corresponding to the positive walks. The sum of the Boolean vector poswalks gives the number of positive walks in the $k$ trials. Dividing by the number of trials gives the empirical probability of positive walks. This empirical probability is compared to the probability from the Positive Walks Theorem which is computed directly from the binomial coeﬃcient.
R script for Positive Walks Theorem..
Octave script for Positive Walks Theorem..
Perl PDL script for Positive Walks Theorem..
Scientiﬁc Python script for Positive Walks Theorem..
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________________
I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.
I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.
Information on this website is subject to change without notice.
Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1
Email to Steve Dunbar, sdunbar1 at unl dot edu
Last modiﬁed: Processed from LATEX source on September 24, 2014