MA3676 2023-24: Seminar 5 1
Seminar 5: Random walks and Gambler’s Ruin problem
Reading recommendation: Lecture notes up to p.191; Jones and Smith, sections 2.1-2.3; any
introductory chapters on random walks and ”Gambler’s ruin” in a text on probability or stochastic
processes.
1) Solve the following system of linear equations:
x1 + 2x2 − 3x3 = 0
x2 + 2x3 − 3x4 = 0
x3 + 2x4 − 3x5 = 0
x4 + 2x5 − 3x6 = 0
x5 + 2x6 − 3x7 = 0
x6 + 2x7 − 3x8 = 0
x7 + 2x8 − 3x9 = 0
x8 + 2x9 − 3x10 = 0
x8 + x9 + x10 = 0
x9 + x10 + 1 = 0
2) Consider a modification of the standard “Gambler’s ruin” problem in which in each game the
probability that player A wins the £1 stake is p, the probability of player A losing the stake is
q, and there is also the possibility of a drawn outcome when each player keeps their stake, which
occurs with probability r (e. g., it is possible for the coin to land on its edge). These three outcomes
exhaust the space of possibilities for a single game, so that p + q + r = 1. Assume further that
p 6= q and r > 0. The initial capital of player A is £a, and the total capital of both players is
N . Find the probability of ruin for player A. Compare your result to the r = 0 case considered in
class.
3) Consider a ‘random walker’ on non-negative integers which moves according to the following
rules: starting from 0, it takes a step +1 with probability p and a step +2 with probability q = 1−p.
(i) Denote the position of the walker after n steps as Sn . Calculate E[Sn ] and Var[Sn ].
(ii) Determine the range of possible values of Sn and the general form of the probability mass
function P (k) ≡ P[Sn = k].
c 2023 I E Smolyarenko
MA3676 2023-24: Seminar 5 2
(iii) Let the walk (starting form 0) terminate whenever the walker either steps on position k or
oversteps it (i.e. makes a step of +2 from k − 1 to k + 1), where k is a positive integer.
1−(−q)k+1
Show that the probability that the walk terminates at k is 1+q . Hint: Construct and
solve the appropriate difference equation on gn , the probability that the walk terminates at k
starting from a generic position n < k. If k is large, find a qualitative argument that gives a
good approximation to the value of g0 without resorting to the difference equation technique.
4) Suppose a casino offers a variant of the “gambler’s ruin” game. Each game consists of a sequence
of plays. It starts with both the player and the dealer having 10 tokens, and one token is bet at
each play. The game ends when either the player or the dealer collects all 20 tokens. At each play
the probability for the dealer to win the token is 1 − p. What should be the value of p in order
for the casino to enjoy the “house advantage” of 6%? (The “house advantage” is defined as the
casino’s expected profit per game as a percentage of the player’s original bet.)
c 2023 I E Smolyarenko
