Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    Exercise 05

    Uploaded by

    Trần Minh

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Exercise 05

    Uploaded by

    Trần Minh
    3 views2 pages

    Original Title

    Exercise05

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    3 views2 pages

    Exercise 05

    Uploaded by

    Trần Minh

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    MS-C2111 Stochastic processes J Kohonen

    Department of Mathematics and Systems Analysis Fall 2024


    Aalto University Exercise 5

    5 Various types of Markov chains


    In this exercise set you will practice your skills learned so far by analyzing various dierent types of
    Markov chains. You will also get introduced to the notions of reversibility and recurrence.

    Classroom exercises
    5.1 Card shuing. Consider a deck (korttipakka) of n = 3 playing cards labeled using a, b, c.
    The possible congurations of the deck are denoted as S = {abc, acb, bac, bca, cab, cba},
    where in each conguration the cards of the deck are listed from top to bottom. The
    deck is shued as follows: In each step the topmost card is lifted and then pushed to a
    uniformly random location in the deck, so that the topmost card is placed to the top,
    middle, or bottom of the deck, each choice with probability 13 , and independently of
    earlier steps. Denote by Xt the conguration of the deck after t shuing steps.
    (a) Explain why (Xt ) is a Markov chain, write down its transition matrix, and draw the
    corresponding transition diagram so that no arrows cross each other.
    (b) Find out the invariant distribution π of the chain.
    Hint: Compute the column sums, what do you observe?

    (c) Is the Markov chain (Xt ) reversible with respect to the distribution π ?
    Now consider a deck of 52 cards, labeled as {1, 2, . . . , 52}. Let S be the set of all cong-
    urations of the deck.

    (d) Determine the size of the set S .


    (e) Describe a Markov chain (Xt ) which represents the same shuing method, at each
    round lifting the topmost card and placing it to a uniformly random location. How
    many entries does the corresponding transition matrix have?
    (f) Find out the unique invariant distribution of the Markov chain (Xt ) corresponding
    to the 52-card deck.

    A general shuing method can be described as follows. A permutation is a one-to-one


    map σ : {1, 2, . . . , 52} → {1, 2, . . . , 52}. Given a deck conguration x = (x1 , x2 , . . . , x52 ),
    a permutation σ transforms it so that σ(x) = (xσ(1) , xσ(2) , . . . , xσ(52) ). A shuing method
    corresponding to a random permutation σ is a Markov chain (X0 , X1 , X2 , . . . ) on S with
    transition matrix
    P (x, y) = P[y = σ(x)].

    In other words, Xt+1 is obtained by permuting Xt with an independent copy of σ .


    (g) * Check that P is a transition matrix, and nd an invariant distribution of the
    Markov chain (Xt ) corresponding to a random permutation σ .

    1/2
    MS-C2111 Stochastic processes J Kohonen
    Department of Mathematics and Systems Analysis Fall 2024
    Aalto University Exercise 5

    Homework problems
    5.2 Gambling pot. A group of people are gambling. Initially there is a pot of 1 EUR on the
    table. Then a round is played, which results in a tie or one of the players winning. If the
    result is a tie, 1 EUR is added to the pot. If one of the players wins, the winner collects
    the accumulated pot in its entirety and the next round starts 1 EUR in the pot. Suppose
    that the probability of a tie in each round is q ∈ [0, 1] and the results of the rounds are
    independent of each other.
    (a) Let Xt be the size of the pot, in euros, in the t-th round. Show that the process
    X = (Xt )t∈Z+ is a Markov chain on the innite state space S = {1, 2, . . . }, and
    calculate its transition probabilities.
    (b) For which values of the parameter q does the process X = (Xt )t∈Z+ have an invariant
    distribution (i.e. a stationary distribution)? Calculate the invariant distribution.

    5.3 Renewal chain . Let q = [q(0), q(1), q(2), . . .] be a probability distribution on the nonneg-
    ative integers N0 = {0, 1, 2, . . . }. A renewal chain corresponding to q is a Markov chain
    on the innite state space N0 with a transition matrix P such that P (k, k − 1) = 1 for
    all k ≥ 1, and P (0, k) = q(k) for all k ≥ 0.
    (a) Sketch the transition diagram of the chain.
    (b) Give an example of q for which the renewal chain is reducible.
    (c) Give an example of q for which the renewal chain is irreducible.
    (d) Prove that state 0 is recurrent.
    (e) Derive a formula for the expected return time E T0+ | X0 = 0 to state 0 in terms of
    

    the distribution q , where T0+ = min{t ≥ 1 : Xt = 0}.


    (f) Invent (or Google) an example of a probability distribution q that corresponds to a
    renewal chain for which E T0 | X0 = 0 = ∞.
    +
    

    2/2

    You might also like