Steven R. Dunbar
Department of Mathematics
203 Avery Hall
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.

_______________________________________________________________________________________________

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

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?

_______________________________________________________________________________________________

Key Concepts

1. The Reﬂection Principle for Paths is the one-to-one correspondence between 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).
2. The probability of a positive walk is
$ℙ2n\left[{T}_{1}>0,{T}_{2}>0,\dots ,{T}_{2n}>0\right]=\frac{1}{{2}^{2n+1}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

3. The probability of a non-negative walk is
$ℙ2n\left[{T}_{1}\ge 0,{T}_{2}\ge 0,\dots ,{T}_{2n}\ge 0\right]=\frac{1}{{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

4. The probability that one player is ahead until the last coin toss in the game, which ties the two players is
$ℙ2n\left[{T}_{1}>0,{T}_{2}>0,\dots ,{T}_{2n}=0\right]=\frac{1}{n{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-1}\right)\phantom{\rule{0.3em}{0ex}}.$

__________________________________________________________________________

Vocabulary

1. To each element $\omega \in {\Omega }_{n}$ we associate a piecewise linear curve in ${ℝ}^{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, called a path.
2. The Reﬂection Principle for Paths is the one-to-one correspondence between 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).

__________________________________________________________________________

Mathematical Ideas

Probability Interpretation: Positive Walks

Recall that ${Y}_{i}$ is a sequence of independent random variables which take values $1$ with probability $1∕2$ and $-1$ with probability $1∕2$. 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 ${ℝ}^{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 |d|\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)∕2}\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)∕2}\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↔{C}^{\prime }$is one-to-one between the two sets of paths of each of the two types. □

Figure 1: A path $C$ starting at $\left(0,0\right)$, crossing $-a$, ending at $\left(n,b-a\right)$ and its reﬂection and translation to a path ${C}^{\prime }$ starting at $\left(0,0\right)$ passing through $a$, ending at $\left(n,b+a\right)$.

Remark. The probability the random walk will end at $\left(0,0\right)$ after $2n$ steps is

$ℙ2n\left[{T}_{2n}=0=\frac{1}{{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\right]\phantom{\rule{0.3em}{0ex}}.$

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).

$ℙ2n\left[{T}_{1}>0,{T}_{2}>0,\dots ,{T}_{2n}>0\right]=\frac{1}{{2}^{2n+1}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

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, 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

$1+\sum _{k=1}^{n-1}\left(\left(\genfrac{}{}{0.0pt}{}{2n-1}{n+k-1}\right)-\left(\genfrac{}{}{0.0pt}{}{2n-1}{n+k}\right)\right)\phantom{\rule{0.3em}{0ex}}.$

This sum telescopes to $\left(\genfrac{}{}{0.0pt}{}{2n-1}{n}\right)$ and

$\left(\genfrac{}{}{0.0pt}{}{2n-1}{n}\right)=\frac{\left(2n-1\right)!}{n!\left(n-1\right)!}=\frac{1}{2}\frac{\left(2n\right)\left(2n-1\right)!}{n!\cdot n\cdot \left(n-1\right)!}=\frac{1}{n}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

Remark. The probability the random walk will end at $\left(0,0\right)$ after $2n$ steps is

$ℙ2n\left[{T}_{2n}=0\right]=\frac{1}{{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

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).

$ℙ2n\left[{T}_{1}\ge 0,{T}_{2}\ge 0,\dots ,{T}_{2n}\ge 0\right]=\frac{1}{{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

Proof. The proof shows that

$ℙ2n\left[{T}_{1}\ge 0,{T}_{2}\ge 0,\dots ,{T}_{2n}\ge 0\right]=2ℙ2n\left[{T}_{1}>0,{T}_{2}>0,\dots ,{T}_{2n}>0\right]\phantom{\rule{0.3em}{0ex}}.$

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.

Corollary 1.

$ℙ2n\left[{T}_{1}>0,{T}_{2}>0,\dots ,{T}_{2n}=0\right]=\frac{1}{n{2}^{2n}}\left(\genfrac{}{}{0.0pt}{}{2n-2}{n-1}\right)\phantom{\rule{0.3em}{0ex}}.$

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

$\sum _{j=1}^{n-k}\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(n-j\right)-k}{n-j}\right)=\left(\genfrac{}{}{0.0pt}{}{2n-k-1}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

In particular,

$2\sum _{j=1}n\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(n-j\right)}{n-j}\right)=\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

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

$\sum _{j=1}^{n-k}\frac{1}{j}\left(\genfrac{}{}{0.0pt}{}{2j-2}{j-1}\right)\left(\genfrac{}{}{0.0pt}{}{2\left(n-j\right)-k}{n-j}\right)\phantom{\rule{0.3em}{0ex}}.$

Considering all of the information above, we see that this equals

$\left(\genfrac{}{}{0.0pt}{}{2n-k}{n}\right)-\left(\genfrac{}{}{0.0pt}{}{2n-k-1}{n-1}\right)=\left(\genfrac{}{}{0.0pt}{}{2n-k-1}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

The second form follows from setting $k=0$ and using the fact that

$\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right)=2\left(\genfrac{}{}{0.0pt}{}{2n-1}{n}\right)\phantom{\rule{0.3em}{0ex}}.$

Remark. Note that:

• The Positive Walks Theorem is diﬀerent from the Hitting Time Theorem. The Positive Walks Theorem gives the probability that an $n$-step random walk starting at $0$ is always positive throughout the remainder of the walk, without regard to the value of the endpoint.
• The Hitting Time Theorem expresses a conditional probability.
• By time reversal and symmetry around $k$, the Hitting Time Theorem is equivalent to the statement that an $n$-step random walk taking independent and identically distributed $±1$ steps stays positive after time $0$, given that it ends at height $k>0$.

Sources

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 10.3. [?].

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithm

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×n+1$ $0$ matrix walks to set the initial condition. Each random walk is examined for positive steps, creating a $k×n+1$ Boolean matrix findposwalks. The rows of the $k×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.

Scripts

R
< 0.5
< 100
< 200

walks = array(0, c(k, n+1))
rw < tapply( 2  matrix( (runif(nk) <= p), k,n )1, 1, cumsum))
walks[ ,1:n+1] < rw

findposwalks < apply( 0+(walks[ ,1:n+1] > 0), 1, sum
poswalks = sum( 0+(findposwalks == n) )

prob < poswalks/
theoretical = 2ˆ((2n+1))choose(2n,n)

cat(sprintf(”Empirical_probability:_%fn”, prob ))
cat(sprintf(”Positive_Walks_Theorem_probability:_%fn”, theoretical))
Octave
p = 0.5;
n = 100;
k = 200;

walks = zeros(k, n+1);
walks(:,2:n+1) = cumsum((2  (rand(k,n) <= p)  1), 2);

findposwalks = sum( walks(:, 2:n+1) > 0);
poswalks = sum( findposwalks == n );

prob = poswalks/k;
theoretical = 2ˆ((2n+1))bincoeff(2n,n);

disp(”Empirical_probability:”), disp( prob )
disp(”Positive_Walks_Theorem_probability:”), disp( theoretical )
Perl
use PDL::NiceSlice;

$p = 0.5;$n = 100;
$k = 200;$walks = zeros($n + 1,$k);
$rw = cumusumover( 2 ( random($n, $k ) <=$p )  1);
$walks( 1:$n, 0: $k1 ) .=$rw;

$findposwalks = sumover($walks( 1:$n, 0:$k1) > 0 );
$poswalks = sum($findposwalks == $n);$prob = $poswalks/$k;

use PDL::GSLSF::GAMMA;
$x = 2.∗∗((2$n+1)) pdl[ gsl_sf_choose(2$n,$n)];
$theoretical =$x(0);

print ”Empirical_probability”, $prob, ”n”; print ”Positive_Walks_Theorem_probability”,$theoretical, ”n”;
SciPy
import scipy

p = 0.5
n= 100
k = 200

walks = scipy.zeros((k, n+1), dtype=int)
rw = scipy.cumsum( 2( scipy.random.random((k,n)) <= p) 1, axis=1)
walks[:,  1:n+1] = rw

findposwalks = 0+(walks[:, 1:n+1] > 0)
poswalks = scipy.sum( scipy.sum( findposwalks, axis = 1) == n)

prob = float(poswalks)/float(k)

import scipy.special
theoretical = scipy.special.exp2((2n+1))scipy.special.binom(2n,n)

print ”Empirical_probability:”, prob
print ”Positive_Walks_Theorem_probability:”, theoretical

__________________________________________________________________________

Problems to Work for Understanding

1. Modify the scripts to compare the empirical probability of nonnegative walks to the probability given in the Nonnegative Walks Theorem.
2. Use the asymptotic growth rate of the central binomial coeﬃcient to ﬁnd the asymptotic growth rate of the probability of positive walks, as the length $n$ of the walks goes to inﬁnity.

__________________________________________________________________________

__________________________________________________________________________

__________________________________________________________________________

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.