IME625A

Download as pdf or txt
Download as pdf or txt
You are on page 1of 6

C8.

HW
Monday, January 31, 2022 10:34 PM

Consider an absorbing Markov Chain with the following transition


probability matrix. It’s obvious that the chain will end up in state 2. Find
the probability that when the chain moves into state 2, it does so from state
1. Take .

0 1 2 Hint: Let . Obviously,


0 0.7 0.2 0.1 . For , you need to use the first-
step analysis. We are looking for . See the
1 0.3 0.5 0.2
notes to know about more uses of first-step
2 0 0 1 analysis.

C8 Page 1
C8.P1
Monday, January 24, 2022 8:19 PM

Gambler’s ruin problem

By the first-step analysis, for ,

Game against infinitely wealthy adversary: Let us consider a limiting case of the
gambler’s ruin problem. Let the opponent be infinitely wealthy, i.e.,
. Actually, the opponent need not have infinite wealth; it should be
able to arrange additional wealth whenever needed. Now, win is no more a
possibility for the player and the game either ends with the player’s ruin or it
continues forever. The Markov chain now have infinite states and is the only
absorbing state. Absorption is no more guaranteed, as there are infinite states.
Now, represents probability of unending game.

If , then , i.e., ruin is guaranteed, and if , then the game


may never end, which has a probability of . For , since the
game may not end, is naturally undefined, i.e., . Among the cases when
the game surely ends (with player’s ruin), for , but for
, even though the game is guaranteed to terminate, the expectation does
not exist, i.e., .

C8 Page 2
C8.P2
Tuesday, February 1, 2022 7:10 PM

Branching chain

Modelling as Markov chain: Consider a population growth model, where


each member lives for a fixed duration of time and produces random
number of offspring at the end of life. Let denote population size in the
-th generation for . Note that is the size of the initial
population. Let denote the offspring produced by the -th members
of -th population for and . These are iid random
variables for all , i.e., all members across populations behave (in terms
of offspring production) independently and identically. Furthermore, these
are independent of , i.e., population size does not have any
influence on offspring production. These assumptions may appear rather
restrictive, but the insights offered by this simplified model are very
useful.

Given the above description, for all . If


is known, then randomness of is due to . Since
these are independent of other ’s and , then
cannot influence . So, Markov property holds and
is a Markov chain, also known as the branching chain. Let us consider a
generic mass function for for all : for
where , , and . Note that
is a necessary condition for the possibility of eventual extinction of the
population. If , then the population only grows and eventually
explodes. Let us try to construct the transition probability matrix.

It’s evident that the transition probabilities contain more and more terms
as increases and there is no simple patter. If we consider specific mass
function for , only in a few simple cases the pattern can be identified.
One such case is: and rest are zero, i.e., either no offspring is
produced, or two offspring are produced. We considered this example in
the previous module. However, if we just make , the pattern in the
transition probability matrix vanishes. Verify this yourself.

Despite the difficulty in the calculation of transition probabilities, we can


observe that the branching chain is an absorbing Markov chain. is the
only absorbing state and for all . However, we are not
sure about absorption due to infinite states. The main question here is the
probability of absorption or extinction for , and the expected
time till extinction whenever . Unlike the gambler’s ruin
problem, we cannot use the first-step analysis as the transition
probabilities are not easy to calculate. So, we take a different approach and
answer the questions.

C8 Page 3
C8.P3
Tuesday, February 1, 2022 7:18 PM

Random sum of random variables: In the review of probability, we obtained:


and
. If are independent, then
and . In addition to independence, if
are identically distributed with mean and variance , then
and . Here, is a positive integer.

Consider a positive integer-valued random variable . Let denote a


sequence of iid random variables with mean and variance . Moreover,
are independent of . We are interested in , a random sum of
random variables. We encounter this quantity in the branching chain. Let us obtain
mean and variance of .

C8 Page 4
C8 Page 5
C8.P4
Tuesday, February 1, 2022 7:19 PM

Mean and variance of population size: In the branching chain,


for , where
are iid random variables denoting the offspring produced by the 1st, 2nd,
3rd, … members of the st generation. These are independent of ,
size of the st generation, as well. Let and denote mean and
variance of offspring produced by any member of the population in any
generation. Then by the formulas for the random sum of random variables,

It appears that the mean number of offspring produced by any member


determines whether and increases or decreases with . In
particular,

Implication for converges to , is random with finite mean is random with


implying guaranteed and infinite variance. Extinction infinite mean and
and extinction extinction. may still be guaranteed, but it variance. Extinction is
would take ‘long time’. no more guaranteed.

C8 Page 6

You might also like