Math 154: Probability Theory
Homework 3
Lawrence Tyler Rush
<me@tylerlogic.com>
March 2, 2011
1 Feller III.10 Problem 1
Problem
Statement. (a) If a > 0 and b > 0, prove that the number of paths (s1,s2,…,sn) such that s1 > -b,…,sn-1,sn = a
is Nn,a - Nn,a+2b. (b) If b > a > 0, prove that there are Nn,a - Nn,2b-a paths satisfying the conditions
s1 < b,s2 < b,…,sn-1 < b,sn = a.
Problem Solution
A:
The
number of paths that start at 0 and end at a in exactly n steps that hit or dip below the -b line is equivalent, by the
reflection principle, to the total number of paths from -2b to a in exactly n steps. However, this is the same as the total
number of paths from 0 to a + 2b in n steps. Thus we have that the total number of paths that hit or dip below the -b line
when starting at 0 and ending on a in n steps is Nn,a+2b, indicating that the number of paths from 0 to a in n steps while
remaining above -b is equal to Nn,a - Nn,a+2b.
B:
The
number of paths from (0,0) to (n,a) that touch the b line at some point is, by the reflection principle, the total number of
paths from (0,2b) to (n,a). This is turn would be equivalent to the total number of paths from (0,0) to
(n,b + (b-a) = (n,2b-a), i.e. Nn,2b-a. Hence the total number of paths from (0,0) that remain below the b line and end
at (n,a) is Nn,a - Nn,2b-a.
2 Feller III.10 Problem 2
3 Feller III.10 Problem 3
4 Feller III.10 Problem 4
5 Feller III.10 Problem 6
6 Feller III.10 Problem 7
7 Feller III.10 Problem 12