联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Probability IV, Michaelmas 2022
About these notes
Lecture notes for Michaelmas 2022. Lectures will follow this content quite closely, but there may be things
said in lecturers that are not in these notes and vice versa. The exercises are an integral part of the notes
and cover examinable material. It is highly recommended that you form your own notes as part of actively
engaging with the material (mathematics, as every course introduction reminds you, is not a spectator
sport).
The sections titled ‘Going further’ concern more advanced material that will only appear on exams as
‘unseen’ material.
These lecture notes are based on previous versions by Ostap Hryniv and Andrew Wade.
Notation
This section briefly reviews some notation that is frequently used in the notes (and course).
Sets
A set S is a collection of elements. If x is an element of S, we write x ∈ S. The set of no elements is the
empty set ?. A set S is a subset of a set T, written S ? T (or T ? S), if x ∈ S implies x ∈ T.
Given two sets S and T, we can construct new sets via:
? Intersection: S ∩ T, the set of elements in both S and T.
? Union: S ∪ T, the set of elements in S or in T (or in both).
? Difference: S T, the set of elements x where x ∈ S but x /∈ T.
? Complement of S in T: S
c ≡ T S, the set of elements x where x ∈ T but x /∈ S.
? Symmetric difference: S △ T = (S T) ∪ (T S), the set of elements in exactly one of S and T.
A set is countable if it is finite or countably infinite, the latter meaning that it is in bijection to the set
N := {1, 2, 3, . . .} of natural numbers.
Given a collection of sets (Aα)α∈I , compact notation for their union or intersection is ∪α∈IAα or
∩α∈IAα. Particular examples are ∪
n
i=1Ai
, ∩
n
i=1Ai (finitely many sets) and ∪∞
i=1Ai
, ∩∞
i=1Ai (a countable
infinity of sets). If the meaning is clear from the context, we may just write ∪nAn, ∩nAn for countable
unions or intersections.
Limits
Recall that if x1, x2, x3, . . . is a sequence of real numbers, then
lim inf
n→∞
xn = limn→∞
inf
m≥n
xm = sup
n
inf
m≥n
xm ,
lim sup
n→∞
xn = limn→∞
sup
m≥n
xm = inf
n
sup
m≥n
xm ;
here ?∞ ≤ lim infn→∞ xn ≤ lim supn→∞ xn ≤ +∞.
If (and only if) lim infn→∞ xn = lim supn→∞ xn then their common value in [?∞, +∞] is limn→∞ xn.
1
If (xn) is a non-decreasing sequence of real numbers, i.e., xn+1 ≥ xn for all n, and x = limn→∞ xn
exists, we write xn ↑ x to indicate that xn converges to x monotonically (from below). Similarly, if xn
is non-increasing with limit x, we write xn ↓ x to indicate that xn converges to x monotonically (from
above). As an example of combining these notational concepts, infm≥n xm is non-decreasing in n, and so
infm≥n xm ↑ lim infn→∞ xn.
Miscellaneous
As usual, 1A denotes the indicator random variable of the event A, i.e., the function 1A(ω) taking value
1 if ω ∈ A and value 0 otherwise.
We will occasionally use the notation a ∧ b = min{a, b} and a ∨ b = max{a, b} for real numbers a and
b. Finally, we use ?x? for the floor function of a real number x, i.e., the largest integer that is at most x.
1 Introductory examples: from finite to infinite spaces
1.1 Coin tossing I
A coin is tossed n times. Let ξk be equal to 1 if the kth toss comes down ‘heads’ and equal to ?1 if the
kth toss comes down ‘tails’. We assume that the coin is fair, so P(ξk = 1) = P(ξk = ?1) = 1
2
, and that
coin tosses are independent.
The sample space of this experiment can be described by the sequence of ±1s: each sequence
(x1, . . . , xn), where xk ∈ {?1, +1}, is equally likely, because there are 2
n
such sequences and each
has probability 2
?n
. This is a finite sample space and we know all about these from earlier probability
courses.
An alternative description of the experiment is given by the sequence not of tosses themselves but of
partial sums ξ1 + · · · + ξk. That is, define S0 := 0 and, for k ∈ {1, . . . , n}, Sk =
Pk
?=1 ξ?
. Then each
realization (x1, . . . , xn) of (ξ1, . . . , ξn) corresponds to a realization (s0, s1, . . . , sn) of (S0, S1, . . . , Sn). The
random process S0, . . . , Sn is called an n-step simple random walk, and any sequence (s0, s1, . . . , sn) of its
possible values is called an n-step trajectory; it has the properties s0 = 0 and |sk+1 ?sk| = 1, there are 2
n
such trajectories. So an equivalent sample space for the experiment is the space of all n-step trajectories;
again every trajectory has probability 2
?n
.
For trajectories of n-step random walks we will ask questions such as
? What is the distribution of the fraction of the time that the walk is positive?
? What is the distribution of the position of the maximum of the walk?
? What is the probability that the walk never revisits to the origin?
These questions have interesting and sometimes surprising answers.
1.2 Coin tossing II
Suppose now that the coin is tossed an infinite number of times, giving a sequence ξ1, ξ2, . . . indexed by
the natural numbers N. This corresponds to an infinite random walk trajectory S0, S1, . . . .
What is the sample space for this process? It must have the property that if we stop at any finite n,
we recover the properties already discussed. The idea is to represent the infinite sequence of coin tosses
(x1, x2, . . .) as a point in [0, 1] via dyadic expansion:
u =
X∞
k=1
2
?k
1 + xk
2
.
For example, the sequence (1, 1, ?1, ?1, . . .) corresponds to 3
4
. Now take U uniformly distributed on [0, 1],
and define (ξ1, ξ2, . . .) as the dyadic expansion of U. Then the sequence ξk has all the right properties: for
2
example,
P(ξ1 = 1) = P(U ∈ [
1
2
, 1]) = 1
2
;
P(ξ2 = 1) = P(U ∈ [
1
4
,
1
2
] ∪ [
3
4
, 1]) = 1
2
;
and
P(ξ1 = 1, ξ2 = 1) = P(U ∈ [
3
4
, 1]) = 1
4
.
So our sample space for the infinite coin-tossing experiment can be [0, 1] with the uniform distribution.
To formalize this we need the notion of measure theory, but you should be happy that this is possible
because you have all seen the uniform distribution before! Note there’s a minor complication here in that
the dyadic expansion may not be unique; (1, ?1, ?1, . . .) and (?1, 1, 1, . . .) are both equal to 1
2
. But there
are relatively few of these (only countably many) and they do not affect the probabilities.
We are not often concerned directly with infinite random walks in this course, but we will ask questions
such as
? What is the probability that the walk eventually returns to the origin?
? What is the expected time taken for the walk to return to the origin?
1.3 Some warm-up exercises
Exercise 1.1. The following task gives you an opportunity to test your intuition. Use your imagination to
“generate” a sequence of 200 random bits (i.e., 0 or 1). Split your sequence into individual runs (a run
is a maximal subsequence of consecutive identical bits) and construct the histogram of the runs lengths.
Compare your results to those generated by computer, using, e.g., the R script available from DUO.
Exercise 1.2. Let Πn denote the set of all n-step paths started at the origin, i.e., the set of s =
(s0, s1, . . . , sn) with s0 = 0 and |sk ? sk?1| = 1 for all 1 ≤ k ≤ n. For s = (s0, s1, . . . , sn) ∈ Πn,
denote
u(s) = Xn
k=1
1{sk?sk?1=+1} and d(s) = Xn
k=1
1{sk?sk?1=?1}
,
the number of ‘up’ and ‘down’ steps in s, respectively.
(i) Let p ∈ [0, 1]. Assume that S = (S0, S1, . . . , Sn) is a random element of Πn with distribution given
for s = (s0, s1, . . . , sn) ∈ Πn by
P(S = s) = P(S0 = s0, S1 = s1, . . . , Sn = sn) = p
u(s)
(1 ? p)
d(s)
.
Define for k ∈ {1, . . . , n}, ξk := Sk ? Sk?1. Show that ξ1, . . . , ξn are independent random variables
with
P(ξi = +1) = p and P(ξi = ?1) = 1 ? p .
(ii) Let p ∈ [0, 1]. Let ξ1, . . . , ξn be independent random variables with
P(ξi = +1) = p and P(ξi = ?1) = 1 ? p .
Define S0 := 0, and, for 1 ≤ k ≤ n,
Sk = ξ1 + · · · + ξk .
Show that for any s = (s0, s1, . . . , sn) ∈ Πn we have
P(S0 = s0, S1 = s1, . . . , Sn = sn) = p
u(s)
(1 ? p)
d(s)
.
Exercise 1.3. Using Definition 2.3, show that the simple random walk is temporally and spatially homogeneous, i.e., show that for any n, x and y,
P(Sn = x | S0 = 0) = P(Sn = x + y | S0 = y)
and for any n, m, x and y,
P(Sn = y | S0 = x) = P(Sn+m = y | Sm = x).
3
2 Trajectories of random walks
Goals of this section:
1. Use path-counting and associated arguments such as the reflection principle and time-reversal to
investigate properties of finite duration simple random walks.
2. Understand the origin of the renewal relation involving visits and first returns to the origin, and its
implications for the first return time distribution.
3. Investigate phenomena associated with long leads, first maxima, and first-passage probabilities.
Alternative presentations of the material in this section can be found in [GS01, Sections 3.9–3.10]
or [Fel68, Section III].
2.1 The Ballot problem
We start by considering the following ballot problem:
Example 2.1. In a ballot consisting of two candidates, votes are counted one by one. It is found that
candidate A scored a votes and candidate B scored b votes, a > b. Suppose that every possible order in
which the a + b votes are counted are equally likely. What is the probability that throughout the counting
process there are more votes for A than for B?
It will be shown below (see Theorem 2.8) that the answer to the ballot problem equals (a ? b)/(a + b).
We will work towards a proof of this result, which is essentially combinatorial—it boils down to counting.
Let n = a + b denote the total number of votes in the ballot. The counting process can be described
by a sequence (ξ0, ξ1, . . . , ξn) where
ξk =
(
+1 if the kth vote is for A ,
?1 if the kth vote is for B .
Then if we define S0 := 0 and, for 1 ≤ k ≤ n,
Sk := X
k
i=1
ξi
,
the sequence (S0, S1, . . . , Sn) describes the evolution of the counting process, with
Sk = the lead of A over B after k ballots have been counted .
It is very instructive to plot Sk against k. Notice that every possible trajectory arising from the counting
process connects the origin (0, S0) = (0, 0) and the final point (n, Sn) = (a + b, a ? b). By assumption,
every such trajectory is equally likely.
Definition 2.2. A sequence of integers (s0, s1, s2, . . . , sn) is an n-step path from x to y if s0 = x, sn = y,
and |sk ? sk?1| = 1 for all 1 ≤ k ≤ n.
In the ballot problem, the counting sequence (S0, S1, . . . , Sn) is an n-step path (n = a + b) from 0 to
a ? b > 0, chosen uniformly at random from all such paths. The event that we are interested in for the
ballot problem is that Sk > 0 for all 1 ≤ k ≤ n.
Let Nn(x, y) denote the total number of n-step paths from x to y. Call sk ? sk?1 the kth step or
jump. Since s0 = x and sn = y, and clearly
sn ? s0 =
Xn
k=1
(sk ? sk?1) = “number of +1 steps” ? “number of ?1 steps”
4
we have that every trajectory that contributes to Nn(x, y) must be such that of its n jumps, there are
exactly n+y?x
2
jumps ‘up’ and n+x?y
2
jumps ‘down’. Each trajectory is specified by choosing which n steps
are ‘up’ and which are ‘down’. Consequently,
Nn(x, y) =
n
n+y?x
2

=

n
n+x?y
2

, (1)
where we use the convention that
n
k

:= 0 unless n and k are non-negative integers with k ≤ n.
In the ballot problem, the total number of paths is
Na+b(0, a ? b) =
a + b
a

=

a + b
b

.
2.2 Simple random walk
Definition 2.3. Let p ∈ [0, 1] and x ∈ Z. Let ξ1, ξ2, . . . , ξn be independent random variables with
P(ξi = +1) = p and P(ξi = ?1) = 1 ? p =: q .
Define S0 := x and for k ∈ {1, . . . , n},
Sk = S0 +
X
k
i=1
ξi
.
Then (S0, S1, . . . , Sn) is called n-step simple random walk (SRW) started at x. If p = 1/2 the random
walk is symmetric (SSRW); otherwise it is biased (BSRW). Unless otherwise stated, we will take x = 0 as
the starting point for SRW.
The word ‘simple’ refers to the fact that the step size is always 1. Later we will also consider SRW with
an unlimited number of steps. To draw a connection with what you have seen previously in Probability
II, notice that SRW is a particular Markov chain.
To start to acquaint ourselves with SRW, we first ask a simple question: what is the distribution of the
final position Sn of an n-step SRW?
Lemma 2.4. Consider SRW started at 0. For n ∈ Z+ and y ∈ Z we have
P(Sn = y) =
n
n+y
2

p
(n+y)/2
(1 ? p)
(n?y)/2
,
provided |y| ≤ n and n + y is even; otherwise, P(Sn = y) = 0.
Proof. Clearly it is impossible to have Sn = y if |y| > n or if n and y have different parity. So suppose
|y| ≤ n and n + y is even. Let
Yn =
Xn
k=1
1{ξk=1}
,
the number of ‘up’ steps. Then Yn is binomial (n, p). Moreover, Sn = Yn ? (n ? Yn) = 2Yn ? n. Hence
P(Sn = y) = P

Yn =
n + y
2

,
which gives the result.
Let Πn denote the set of all n-step paths started at the origin, i.e., the set of s = (s0, s1, . . . , sn) with
s0 = 0 and |sk ? sk?1| = 1 for all 1 ≤ k ≤ n. (It is convenient to take Π0 to consist of a single path,
namely the empty path.) For s = (s0, s1, . . . , sn) ∈ Πn, denote
u(s) = Xn
k=1
1{sk?sk?1=+1} and d(s) = Xn
k=1
1{sk?sk?1=?1}
,

the number of ‘up’ and ‘down’ steps in s, respectively. It is easy to see from Definition 2.3 that for each
s = (s0, s1, . . . , sn) ∈ Πn,
P(S0 = s0, S1 = s1, . . . , Sn = sn) = p
u(s)
(1 ? p)
d(s)
. (2)
In particular, if p = 1/2 we see that SSRW gives a uniform random element of Πn since (1/2)u(s)+d(s) =
2
?n
. We will see shortly how the ballot theorem translates to this context.
Remark 2.5. We may use (2) as an alternative definition of SRW as a random elements of Πn: see
Exercise 1.2. In this context, one may see Lemma 2.4 as a translation of the formula (1).
One interpretation of SSRW is as a fair coin-tossing game played between two players. Suppose that
a fair coin is flipped n times. Player A wins ￡1 if the coin comes down ‘heads’, and Player B wins ￡1 if
the coin comes down ‘tails’. Let Sk denote the cumulative amount of money by which Player A is ahead
after k tosses. Then (S0, S1, . . . , Sn) is an n-step SSRW.
There are many interesting phenomena associated with SSRW and the coin-tossing game, and we will
see several of these in this term’s lectures. We mention a couple of facts here.
Consider the events
E
+
n =

Player A leads in all n trials
(3)
E
=
n =

Player A leads in exactly n/2 trials
. (4)
One might expect E=
n
(when n is even) to be much more likely than E+
n
; after all, the game is ‘fair’ !
However, one can show (see Remark 2.18 below) that for n = 20000, one has P(E+
n
)/P(E=
n
) ≈ 88. In
fact, the most probable number of changes of lead is zero! Many stochastic processes in applications have
a similar property.
Let Tn denote the number of times the coin-tossing game is tied, or, equivalently, the number of times
SSRW visits the origin in n steps:
Tn := Xn
k=1
1{Sk=0}
.
How does Tn behave as n grows? Common sense might suggest that for n large enough, T2n ≈ 2Tn, i.e.,
Tn grows linearly with n. This conjecture is actually wrong; in fact, one can show that for n large enough,
Tn ≈
√
n. Similarly, the typical distance between consecutive returns to the origin for SSRW scales also
as √
n. A R script illustrating these properties is available from DUO.
We will also sometimes consider random walks with infinite trajectories, or coin tossing games of
unbounded duration.
Definition 2.6. Let p ∈ [0, 1] and x ∈ Z. Let ξ1, ξ2, . . . be an infinite sequence of independent random
variables with
P(ξi = +1) = p and P(ξi = ?1) = 1 ? p =: q .
Define S0 := x and for n ≥ 1,
Sn = S0 +
Xn
i=1
ξi
.
Then (S0, S1, . . .) is called infinite simple random walk started at x.
Note that if we terminate the infinite random walk after n steps we obtain (S0, S1, . . . , Sn) an n-step
random walk satisfying Definition 2.3.
2.3 Reflection principle
Recall that Nn(x, y) denotes the number of n-step paths from x to y. Also, let N0
n
(x, y) be the number
of such paths that contain 0 at some time, i.e., the number of (s0, s1, . . . , sn) with jumps of size 1 from
x to y such that s0s1 · · · sn = 0.
The next lemma, called the reflection principle, is relatively easy to prove, but nonetheless extremely
important.
6
Lemma 2.7. If x, y > 0 then N0
n
(x, y) = Nn(?x, y).
Proof. Each path from ?x to y must hit 0 at some earliest time k ∈ {1, . . . , n ? 1}. Reflect the segment
of the path indexed over [0, k] in the time axis to obtain a path from x to y in n steps which hits 0. This
gives a one-to-one correspondence between the two sets of paths.
Using the reflection principle, we can easily derive the ballot theorem:
Theorem 2.8. If h is a positive integer then the number of n-step paths from 0 to h which do not revisit
0 is h
n Nn(0, h).
Proof. The first step of all the paths in question must be ‘up’. So the number of such paths is
Nn?1(1, h) ? N
0
n?1
(1, h) = Nn?1(1, h) ? Nn?1(?1, h),
by the reflection principle. Then we use the formula (1) to compute
Nn?1(1, h) ? Nn?1(?1, h) =
n ? 1
(n + h)/2 ? 1

?

n ? 1
(n + h)/2

=
n + h
2n
?
n ? h
2n

n
(n + h)/2

=
h
n

n
(n + h)/2

,
which gives the result.
Example 2.9. In particular, if h = a ? b > 0 and n = a + b then the fraction of paths from 0 to a ? b
that do not revisit 0 is (a ? b)/(a + b), as claimed in our solution to the Ballot problem.
The Catalan numbers are defined by
C2n :=
1
n + 1
2n
n

=
(2n)!
(n + 1)!n!
. (5)
Here are two random walk results where the Catalan numbers appear.
Corollary 2.10. For a fixed integer n > 0, consider 2n-step paths from 0 to 0. Then:
(a) there are exactly C2(n?1) such paths satisfying min1≤k≤2n?1 sk > 0;
(b) there are exactly C2n such paths satisfying min0≤k≤2n sk ≥ 0.
Proof. Notice that every path contributing to (a) starts with a segment of 2n ? 1 steps from 0 to 1 never
returning to 0, and then the final step is ‘down’. So by Theorem 2.8 the number of such paths is
1
2n ? 1

2n ? 1
n

=
(2n ? 2)!
n!(n ? 1)! = C2(n?1) .
For part (b), observe that there is a one-to-one relation between strictly positive paths of length 2n+ 2 and
non-negative paths of length 2n (just remove the first and the last jump of the positive trajectory!).
Exercise 2.1. Consider SRW with parameter p ∈ [0, 1] started at 0. For x ?= 0, use the ballot theorem to
show that
P(S1 ?= 0, S2 ?= 0, . . . , Sn?1 ?= 0, Sn = x) = |x|
n
P(Sn = x).
Deduce that the probability that SRW never revisits 0 over n steps is equal to 1
n
E|Sn|.
7
Exercise 2.2. Consider n-step SRW with parameter p ∈ [0, 1] started at 0, and let τx = min{k ≥ 1 :
Sk = x}, the first time the walk reaches level x (set min ? := ∞). Consider the time-reversed random
walk (R0, R1, . . . , Rn) given by R0 = 0, R1 = ξn, R2 = ξn +ξn?1, . . . , Rn = ξn +· · ·+ξ1, i.e., the jumps
are taken in reverse order. Relate the event {S1 ?= 0, S2 ?= 0, . . . , Sn?1 ?= 0, Sn = x} for the original walk
to the event {τx = n} for the time-reversed walk, and hence use Exercise 2.1 to show that for x ?= 0,
P(τx = n) = |x|
n
P(Sn = x).
Exercise 2.3. Let S0, S1, . . . , Sn be SSRW starting at 0, and let τx = min{k ≥ 1 : Sk = x} denote the
first hitting time of level x. Use the reflection principle to show that for x ?= 0,
P(τx ≤ n) = 2P(Sn > |x|) + P(Sn = x).
Why does the argument not work when the random walk is not symmetric?
Hint: Consider the number of n-step paths that start at 0, pass through x and finish at Sn = y for y ∈ Z.
Consider separately the cases y < x, y = x and y > x.
2.4 Renewal structure
Consider SSRW (so p = 1/2) S0, S1, . . . , S2n. We are going to study the connection between the probabilities
u2n := P(S2n = 0), and f2n := P(S1 ?= 0, S2 ?= 0, . . . , S2n?1 ?= 0, S2n = 0),
i.e., the probabilities of the events
V2n =

SSRW visits the origin at time 2n

and R2n =

first return of SSRW to the origin is at time 2n

.
It is easy to see that u0 = 1. By definition, a return to the origin can happen only after a positive even
number of steps, so f0 := P(R0) = 0.
Lemma 2.11. We have
u2n =

2n
n

2
?2n ～
1
√
πn
, as n → ∞. (6)
Proof. The equality is a special case of Lemma 2.4, while the asymptotic form follows from Stirling’s
formula n! ～
√
2πn(n/e)
n
(see Exercise 2.4).
At the same time, for any n ≥ 1 the event V2n = {S2n = 0} can be partitioned into the disjoint union
∪
n
k=1(V2n ∩ R2k), so that the formula of total probability implies
P(V2n) = Xn
k=1
P(R2k)P(V2n | R2k).
Now notice that P(V2n | R2k) = P(V2n?2k) because given R2k we know that the random walk is at the
origin at time 2k, and the path S2k, S2k+1, . . . , S2n is distributed as a uniform random (2n?2k)-step path
started at the origin. In the above notation, we thus have:
Lemma 2.12. The following renewal relation is valid.
u2n =
Xn
k=1
f2ku2n?2k , for all n ≥ 1 . (7)
A useful interpretation of (7) is that after a return to the origin (in particular, after the first return to
the origin), the SSRW starts afresh, hence the term ‘renewal’; this property is also known as the strong
Markov property in Markov chain theory.
Let τ0 := min{n ≥ 1 : Sn = 0} denote the first return time to the origin; as usual we use the
convention min ? := ∞.
8
Theorem 2.13. For SSRW, we have, for n ≥ 1,
P(τ0 = 2n) = f2n =
1
2n ? 1

2n
n

2
?2n
.
Proof. Recall the definition of the Catalan numbers from (5). Corollary 2.10(a) shows that the probability
that SSRW makes a first return at time 2n having been positive over times [1, 2n ? 1] is 2
?2nC2(n?1);
by symmetry, with the same probability the excursion is negative. Hence we can compute the first return
probability f2n:
f2n = 21?2nC2n?2 =
1
n

2n ? 2
n ? 1

2
1?2n =
1
2n
u2n?2 . (8)
The form given in the theorem is follows after performing some algebraic rearrangements.
One can also show that
f2k = u2k?2 ? u2k , (9)
for instance, by checking that the RHS of equation (8) is equal to that of equation (9). A consequence of
this is the following result.
Theorem 2.14. For SSRW, P(S1 ?= 0, S2 ?= 0, . . . , S2n ?= 0) = P(S2n = 0).
Proof. Recall that τ0 = min{n ≥ 1 : Sn = 0}. Then
P(S1 ?= 0, S2 ?= 0, . . . , S2n ?= 0) = P(τ0 > 2n) = 1 ? P(τ0 ≤ 2n),
and summing over the possible values of τ0 (which must be even) gives that the probability that the walk
does not return to the origin in 2n steps is
P(S1 ?= 0, S2 ?= 0, . . . , S2n ?= 0) = 1 ?
Xn
k=1
f2k = 1 ?
Xn
k=1
(u2k?2 ? u2k) = u2n , (10)
using equation (9).
In other words, we have:
Corollary 2.15. For the SSRW, we have
P(τ0 > 2n) =
2n
n

2
?2n
, for n ≥ 0 .
In particular, for infinite SSRW we have from the asymptotic formula (6) that P(τ0 > 2n) → 0 as
n → ∞, which means that P(τ0 < ∞) = 1. In the language of Markov chains, this says that SSRW is recurrent; in Exercises 2.7 and 2.11 it is shown that Eτ0 = ∞, so SSRW is null recurrent. Remarkably, the following event has the same probability: Lemma 2.16. For SSRW, P(S1 ≥ 0, S2 ≥ 0, . . . , S2n ≥ 0) = P(S2n = 0). Proof. This is Exercise 2.12. Exercise 2.4. The aim of this exercise is to obtain by simple calculus a version of Stirling’s formula, namely that there is a positive constant a0 such that, as n → ∞, n! ～ a0e ?nn n+ 1 2 , where ～ indicates that the ratio of the two sides tends to 1. (It can be shown that the constant a0 is equal to √ 2π, but that is a harder exercise!) The idea of the proof is to consider log n! = log 1 + log 2 + · · · + log(n ? 1) + log n and try to quantify the difference between the sum and the integral R n+1 1 log x dx. 9 (i) Draw a picture of the function log x for x ≥ 1. Consider the segment of the picture for x in the range [n, n + 1]. Let rn denote the area of the largest rectangle under the curve with base on the segment of the x-axis in the range [n, n + 1]. Let tn denote the area of the largest triangle that sits between the rectangle and the curve. Let δn denote the area under the curve not accounted for by rn or tn. Show that Z n+1 1 log x dx = log n! + 1 2 log(n + 1) +Xn k=1 δk . (ii) Considering the area under the curve over interval [n, n+1], deduce that δn = n + 1 2 log 1 + 1 n ?1, Then use Taylor’s theorem for log(1 + y) to show that δn = 1 12n2 + O(n ?3 ). (iii) By computing the integral in part (i) and simplifying, show that n! = e?nn n+ 1 2 e ?c+o(1) 1 + 1 n n+ 1 2 for some constant c > 0, and so finally deduce Stirling’s formula as stated, where a0 is a function of
c.
Exercise 2.5. Consider SRW with parameter p ∈ [0, 1] started at 0. Show that the generating function of
the sequence P(Sn = 0) is given by
ψ(t) := X∞
n=0
t
nP(Sn = 0) = 1
p
1 ? 4p(1 ? p)t
2
,
provided |t| < 1/ p 4p(1 ? p). To do this, first use Taylor’s theorem to verify that X∞ m=0 2m m x m = 1 √ 1 ? 4x for all |x| < 1/4 . (11) Exercise 2.6. Consider SRW with parameter p ∈ [0, 1] started at 0, and its first return time to the origin τ0 := min{n ≥ 1 : Sn = 0}. Consider the generating functions ψ(t) := X∞ n=0 t nP(Sn = 0) and ?(s) := X∞ n=0 s nP(τ0 = n). Use the renewal relation (7) to establish the relation ψ(t) = 1 + ψ(t)?(t). Hence deduce from Exercise 2.5 that ?(s) = 1 ? p 1 ? 4p(1 ? p)s 2 . Exercise 2.7. Consider an infinite SRW with parameter p ∈ (0, 1) started at 0 and let τ0 := min{n ≥ 1 : Sn = 0}. Using the result of Exercise 2.6, show that (i) P(τ0 < ∞) = 1 ? |2p ? 1|. (ii) Eτ0 = +∞. Note that in the language of Markov chains, this result says that for p = 1/2 SRW is null recurrent and when p ?= 1/2 SRW is transient. Exercise 2.8. For infinite SSRW, let τx := min{n ≥ 1 : Sn = x} denote the first hitting time of x ∈ Z. This exercise gives a direct argument that Eτ0 = ∞ using the Markov property, spatial homogeneity, and symmetry of the random walk. (i) By considering the first step of the walk started at S0 = 0, argue that Eτ0 = 1 + Eτ1. (ii) By considering the first step of the walk started at S0 = 0, argue that Eτ1 = 1 + Eτ1. (iii) Hence deduce that Eτ0 = ∞. Exercise 2.9. Use Theorem 2.13 to directly deduce Corollary 2.15. Exercise 2.10. Use Theorem 2.14 and Exercise 2.1 to show that for SSRW we have E|S2n| = n 2n n 2 1?2n . Hence use Stirling’s formula to show that E|S2n| ～ 2 p n/π as n → ∞. Interpret this result in words. Exercise 2.11. Consider infinite SSRW and the time τ0 = min{n ≥ 1 : Sn = 0} of first returning to 0. (a) Show that for n ≥ 1 P(τ0 = 2n) = 1 2 P(S1S2 · · · S2n?1 ?= 0, S2n?1 = +1) + 1 2 P(S1S2 · · · S2n?1 ?= 0, S2n?1 = ?1). (b) Hence use Exercise 2.1 to show that, for n ≥ 1, we have P(τ0 = 2n) = 1 2n ? 1 2n n 2 ?2n . (c) Use Stirling’s formula to show that E[τ β 0 ] < ∞ if and only if β < 1/2. Exercise 2.12. Use path-counting to show that f2k is also the probability of first visiting state ?1 at time 2k ? 1: P(S1 ≥ 0, S2 ≥ 0, . . . , S2k?2 ≥ 0, S2k?1 < 0) = f2k . Use the telescopic property (9) to deduce that the probability P(S1 ≥ 0, S2 ≥ 0, . . . , S2n ≥ 0) = P no visit to ?1 up to time 2n coincides with u2n. Exercise 2.13. Consider a SRW with parameter p ∈ (0, 1), started at S0 = 1. Let τ0 = min{n ≥ 1 : Sn = 0} denote the first hitting time of the origin. (a) By counting paths in a similar way to Exercise 2.12, use Corollary 2.10 to show that the Catalan number C2n counts the total number of (2n + 1)-step non-negative trajectories with τ0 = 2n + 1. Deduce the value of the first-passage probability an = P(τ0 = 2n + 1). (b) Show that an+1 < an for all n, and show that if p ?= 1/2 then an ≤ e ?δn for some constant δ > 0.
2.5 Long lead probability
Consider SSRW S0, S1, . . . , S2n. For 1 ≤ k ≤ 2n, we say that a time interval (k ? 1, k) is positive for
the random walk if the event {Sk?1 ≥ 0, Sk ≥ 0} occurs. Similarly, we say interval (k ? 1, k) is negative
if {Sk?1 ≤ 0, Sk ≤ 0} occurs. Note that any interval (k ? 1, k) must be either positive or negative, and
cannot be both.
Note that after 2n steps, the number of positive/negative intervals must be even. Let A2k,2n be the
event that the walk S0, S1, . . . , S2n has exactly 2k positive intervals (and hence 2n?2k negative intervals);
i.e.,
A2k,2n =
nX
2n
i=1
1{Si?1≥0,Si≥0} = 2k
o
.
To compute the probability p2k,2n := P(A2k,2n) explicitly, notice the symmetry p2k,2n = p2n?2k,2n.
Theorem 2.17. Let the probability p2k,2n be as described above. Then
p2k,2n = P(A2k,2n) = u2ku2n?2k, for any k ∈ {0, 1, . . . , n} . (12)
1
Proof. We proceed by induction. The case n = 1 is trivial: the two time intervals are either both positive
if S1 > 0, or both negative if S1 < 0, so one immediately gets p0,2 = p2,2 = 1 2 = u2u0. Thus we assume that (12) holds for all n < m, and consider the case n = m. By Lemma 2.16 and symmetry, we have p0,2m = p2m,2m = u2m = u0u2m. Otherwise 0 < k < m. By conditioning on the first return to the origin, we get p2k,2m = 1 2 X k ?=1 f2?p2k?2?,2m?2? + 1 2 mX?k ?=1 f2?p2k,2m?2? . Here, the first sum counts the trajectories whose first jump is up, who return to the origin at time 2? (and thus contributing 2? positive intervals), and then who contribute a remaining 2k ? 2? positive intervals; similarly, the second sum counts the trajectories whose first jump is down. Using the inductive hypothesis (12) and the renewal relation (7), we obtain p2k,2m = 1 2 u2m?2k X k ?=1 f2?u2k?2? + 1 2 u2k mX?k ?=1 f2?u2m?2k?2? = u2ku2m?2k . This completes the induction. Remark 2.18. It is instructive to investigate the result of the theorem numerically, e.g., by using the R script available from DUO. In particular, if a fair coin is tossed once per second during 365 days (or n = 31536000 times in total), with probability 0.05 the losing player shall lead in no more than 48606 tosses (or 13.50167 hours); similarly, with probability 0.1 the losing player shall lead in no more than 194130 tosses (or 2.246875 days). One can also verify that for a SSRW with n = 20000 steps the ratio P(E+ n )/P(E= n ) of probabilities from (3) and (4) is about 88.62602. Remark 2.19. By using the asymptotics (6), one can see that p2k,2n ≈ 1 π √ k(n?k) , as long as both k and n ? k are large enough. The following result is an integral version of Theorem 2.17. The next theorem is called the Arcsine law. Theorem 2.20. For fixed α ∈ (0, 1), let pn(α) be the probability that the fraction of time spent by a 2n-step SSRW on the positive side is smaller than α, pn(α) = X 0≤k<αn p2k,2n . Then, as n → ∞, pn(α) → 1 π Z α 0 dx p x(1 ? x) ≡ 2 π arcsin √ α . Proof. The evaluation of the integral is standard; we may simply note that d dx arcsin √ x = 1 2 p x(1 ? x) . It remains to prove the convergence stated in the theorem. First suppose that α ∈ [1/2, 1) and decompose pn(α) = X 0≤k