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.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

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

Key Concepts

  1. The Reflection Principle for Paths is the one-to-one correspondence between paths with origin (0,a) and endpoint (n,b) crossing the x-axis (call these paths of the first type) equals the number of paths with origin (0,a) and endpoint (n,b) (call these paths of the second type).
  2. The probability of a positive walk is
    2n T1 > 0,T2 > 0,,T2n > 0 = 1 22n+1 2n n .

  3. The probability of a non-negative walk is
    2n T1 0,T2 0,,T2n 0 = 1 22n 2n n .

  4. The probability that one player is ahead until the last coin toss in the game, which ties the two players is
    2n T1 > 0,T2 > 0,,T2n = 0 = 1 n22n 2n 2 n 1 .

__________________________________________________________________________

Vocabulary

Vocabulary

  1. To each element ω Ωn we associate a piecewise linear curve in 2 consisting of a finite union of segments of the form [(i,j), (i + 1,j + 1)] or [(i,j), (i + 1,j 1)] where i,j are integers, called a path.
  2. The Reflection Principle for Paths is the one-to-one correspondence between paths with origin (0,a) and endpoint (n,b) crossing the x-axis (call these paths of the first type) equals the number of paths with origin (0,a) and endpoint (n,b) (call these paths of the second type).

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Probability Interpretation: Positive Walks

Recall that Y i is a sequence of independent random variables which take values 1 with probability 12 and 1 with probability 12. This is a mathematical model of a fair coin flip game where a 1 results from “heads” on the ith coin toss and a 1 results from “tails”. Let Hn and Ln be the number of heads and tails respectively in n flips. Then Tn = i=1nY i = Hn Ln = 2Sn n counts the difference 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 T0. The person takes a step to the right to T0 + 1 with probability p and takes a step to the left to T0 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 finite union of segments of the form [(i,j), (i + 1,j + 1)] or [(i,j), (i + 1,j 1)] where i,j are integers is called a path. A path has an origin (a,b) and an endpoint (c,d) which are points on the curve with integer coordinates satisfying a i c for all (i,j) on the curve. We will say the length of the path is c a. (Note that the Euclidean length of the path is (c a)2.) To each element ω Ωn (see Binomial Distribution.), we associate a path k=0n1[(i,T i(ω)), (i + 1,Ti+1(ω))] with origin (0, 0) and endpoint (n,Tn(ω)).

If c and d are two integers such that 0 |d| c then the number of paths with origin (0, 0) and endpoint (c,d) is zero if c + d is odd and c (c+d)2 if c + d is even. More generally, if a, b, c and d are integers such that 0 |d b| c a and c a + d b is even, then the number of paths with origin (a,b) and endpoint (c,d) is ca (ca+bd)2.

Proposition 1 (Reflection Principle for Paths). Let a,b 0 and n > 0 be integers. Then

n Tn = b a and Tk = a,k [0,n] = n Tn = b + a.

Proof. The case a = 0 is trivial, so suppose a > 0. The proof will establish a one-to-one correspondence between paths with origin (0, 0) and endpoint (n,b a) that cross the horizontal line y = a with paths with origin (0, 0) and endpoint (n,a + b). Translating each path of the first type up by a units, this is equivalent to showing that the number of paths with origin (0,a) and endpoint (n,b) crossing the x-axis (call these paths of the first type) equals the number of paths with origin (0,a) and endpoint (n,b) (call these paths of the second type). If C is a path of the first type, set t(C) to be the smallest i > 0 such that (i, 0) C. The path C is a union of a path C1 with origin (0, 0) and endpoint (t(C), 0) and a path C2 with origin (t(C), 0) and endpoint (n,b). Then to each C, we associate the path C that is the union of C2 with the reflection of C1 across the x-axis. The path C is a path of the second type and the correspondence C Cis one-to-one between the two sets of paths of each of the two types. □



Figure 1: A path C starting at (0, 0), crossing a, ending at (n,b a) and its reflection and translation to a path C starting at (0, 0) passing through a, ending at (n,b + a).

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

2n T2n = 0 = 1 22n 2n n .

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 T1 > 0,T2 > 0,,T2n > 0 = 1 22n+1 2n n .

Proof. Count the paths with origin (0, 0) and length 2n strictly contained in the upper half plane. To obtain this, sum the number of paths from (1, 1) to (2n, 2k) that do not touch the x-axis. There is only one path that connects the point (1, 1) to the point (2n, 2n) and this path does not return to the x-axis. If 1 k < n, the number of paths connecting (1, 1) to the point (2n, 2k) that do not return to the x-axis equals the number of paths connecting (1, 1) to the point (2n, 2k) minus the number of paths that do return to the x-axis. The number of paths connecting (1, 1) to the point (2n, 2k) is 2n1 n+k1. By the reflection principle the number of paths connecting (1, 1) to the point (2n, 2k) that return to the x-axis equals the number of paths connecting the point (1,1) to the point (2n, 2k), which is 2n1 n+k .

Therefore, the number of paths with origin (0, 0) and length 2n that are contained in the upper half-plane is

1 + k=1n1 2n 1 n + k 1 2n 1 n + k .

This sum telescopes to 2n1 n and

2n 1 n = (2n 1)! n!(n 1)! = 1 2 (2n)(2n 1)! n! n (n 1)! = 1 n 2n n .

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

2n T2n = 0 = 1 22n 2n n .

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 difference between the previous corollary and the next corollary, the first is about positive walks and the second is about nonnegative walks.

Theorem 3 (Non-Negative Walks Theorem).

2n T1 0,T2 0,,T2n 0 = 1 22n 2n n .

Proof. The proof shows that

2n T1 0,T2 0,,T2n 0 = 22n T1 > 0,T2 > 0,,T2n > 0 .

The claim is that the number of paths with origin (0, 0) 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 (0, 0) 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 first type by removing the initial segment and translating the path 1 unit left and 1 unit down.

Note that T2n1 is never zero. Then to each path with origin (0, 0) and length 2n 1 that is contained in the upper half-plane including the x-axis, we can associate exactly two paths with length (0, 0) 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 {M1 0,M2 0,,M2n 0} is twice the cardinality of the event {M1 > 0,M2 > 0,,M2n > 0}. □

Remark. The final 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 T1 > 0,T2 > 0,,T2n = 0 = 1 n22n 2n 2 n 1 .

Proof. Count the paths with origin (0, 0) and endpoint (2n, 0) that are contained in the open upper half-plane which does not include the x-axis. In other words, count the paths with origin (1, 1) and endpoint (2n 1, 1) that are contained in the open upper half-plane. This number equals the number of paths with origin (1, 1) and endpoint (2n 1, 1) that touch the x-axis at some point. The number of paths with origin (1, 1) and endpoint (2n 1, 1) equals 2n2 n1 . By the reflection principle, the number of paths with origin (1, 1) and endpoint (2n 1, 1) that touch the x-axis equals the number of paths with origin (1,1) and endpoint (2n 1, 1). The number is 2n2 n2 . Finally, it is easy to check that

2n 2 n 1 2n 2 n 2 = (2n 2)! (n 1)!(n 1)! (2n 2)! (n 2)!n! = n(2n 2)! (n 1)(2n 2)! (n 1)!n! = 1 n (2n 2)! (n 1)!(n 1)! = 1 n 2n 2 n 1

Remark. The corollaries imply the following combinatorial identity.

Corollary 2. If n and k are integers with 0 k n, then

j=1nk1 j 2j 2 j 1 2(n j) k n j = 2n k 1 n .

In particular,

2 j=1n1 j 2j 2 j 1 2(n j) n j = 2n n .

Proof. Count the number of paths with origin (0, 0) and endpoint (2n k,k) in two different ways. On one hand, the number of such paths is 2nk n . On the other hand, the number of paths equals the number of paths with origin (1, 1) and endpoint (2n k,k) plus the number of paths with origin (1,1) and endpoint (2n k,k). The number of paths with origin (1, 1) and endpoint (2n k,k) is 2nk1 n1 . Next, for every path with origin (1,1) and endpoint (2n k,k), there exists a minimum integer 1 j n k such that the path passes through (2j, 0). 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 (0, 0) and endpoint (2j, 0) that are contained in the lower half-plane and the number of paths with origin (2j, 0) and endpoint (2n k,k). By the previous corollary, this implies the number of paths with endpoint (1,1) and endpoint (2n k,k) is

j=1nk1 j 2j 2 j 1 2(n j) k n j .

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

2n k n 2n k 1 n 1 = 2n k 1 n .

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

2n n = 22n 1 n .

Remark. Note that:

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

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 flips, 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 finds 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 coefficient.

Scripts

Scripts

R

R script for Positive Walks Theorem..

< 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

Octave script for Positive Walks Theorem..

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

Perl PDL script for Positive Walks Theorem..

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

Scientific Python script for Positive Walks Theorem..

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

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 coefficient to find the asymptotic growth rate of the probability of positive walks, as the length n of the walks goes to infinity.

__________________________________________________________________________

Books

Reading Suggestion:

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

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 effort 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 reflects the thoughts, interests and opinions of its author. They do not explicitly represent official 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 modified: Processed from LATEX source on September 24, 2014