Lecture 4 Random Walk and ruin problems
➢ A special kind of Markov chain known as random walk.
➢ A random walk is a stochastic process that consists of the sum of a sequence of changes in a random
variable. It is a process, a model or a rule to generate path sequence of random motion.
➢ A random walk is a stochastic process that describes a path that consists of a succession of random
steps on some mathematical space such as integers.
➢ Random walk is used to determine the probable location of a “walker” in a random motion, where
the location of the walker corresponds to the value of the sum of the sequence of changes.
➢ A random walk represents a quantity that changes over time (e.g., a stock price, an inventory level,
or a gambler’s fortune
Many natural phenomenon can be modelled as random walk:
• the path traced by a molecule as it travels in a liquid or a gas
• the price of a fluctuating stock
• the financial status of a gambler
• pageRank
• investment theory of stock market
Classical ruin problem
When we discuss random walks, it is an aid to speak about the state of the system as the position of a
moving “particle.”
Example . Gambler’s Ruin. Consider a Markov chain on S = {0, 1,...,m} with transition matrix
Simple Random Walk
➢ Simple random walk can be thought of as a model for repeated gambling.
➢ Specifically, suppose you start with #a, and repeatedly make #1 bets.
➢ At each bet, you have probability p of winning #1 and
➢ probability q of losing #1,
where p + q= 1.
➢ If Xn is the amount of money you have at time n (henceforth, your fortune at time n), then
X0 = a, while X1 could be a +1 or a -1
➢ depending on whether you win or lose your first bet.
➢ Then X2 could be a +2 (if you win your first two bets), or a (if you win once and lose once),
or a -2 (if you lose your first two bets). Continuing in this way, we obtain
(1)
EXAMPLE 1:
Consider simple random walk with a = 8 and p =1 /3, so you start with #8 and have probability 1/ 3 of
winning each bet. Then the probability that you have #9 after one bet is given by
as it should be. Also, the probability that you have #7 after one bet is given by
On the other hand, the probability that you have #10 after two bets is given by
EXAMPLE 2:
Consider again simple random walk with a = 8 and p =1/ 3. Then the probability that you have #7 after
three bets is given by
Now, there are three different ways we could have Z1+ Z2 +Z3 = -1, namely:
(a) Z1 =1, while Z2= Z3=-1;
(b) Z2= 1, while Z1= Z3=-1 1; or
(c) Z3=1 , while Z1= Z2 =- 1.
Each of these three options has probability (1 /3) (2/ 3) (2/ 3) .
Hence,
If the number of bets is much larger than three, then it becomes less and less convenient to compute
probabilities in the above manner. A more systematic approach is required. We turn to that next.
The Distribution of the Xn
We first compute the distribution of Xn, i.e., the probability that your fortune Xn after n bets
takes on various values
Theorem 1
This theorem tells us the entire distribution, and expected value, of the fortune Xn at time n.
Example 3
Example 4 The Gambler’s Ruin Problem
The previous subsection considered the distribution and expected value of the fortune Xn at a
fixed time n. Here, we consider the gambler’s ruin problem, which requires the consideration of
many different n at once, i.e., considers the time evolution of the process.
Let Xn be simple random walk as before, for some initial fortune a and some probability p of
winning each bet. Assume a is a positive integer. Furthermore, let c a be some other integer. The
gambler’s ruin question is: If you repeatedly bet #1, then what is the probability that you will
reach a fortune of #c before you lose all your money by reaching a fortune #0? In other words,
will the random walk hit c before hitting 0? Informally, what is the probability that the gambler
gets rich (i.e., has #c) before going broke?
Theorem 2
Consider some applications of this result.
Example 5
Example 6
Theorem
Example 7
More example from the text, Examples 1.19 – 1.25 (pages 35- 47)
