Price your future right. 60% off with code BLACKSCHOLES at USD checkout. Offer ends in --d --h --m --s-- days -- hours -- minutes -- seconds.
Price your future right. 60% off with code BLACKSCHOLES at USD checkout. Offer ends in 13d 03h 19m 04s13 days 3 hours 19 minutes 4 seconds.
Topic
Markov chain questions model a process by its states, and ask for hitting probabilities or expected time to absorption.
14 free, 17 with Premium.
A Markov chain is a random process whose next state depends only on the current one. Interview questions describe a game, a random walk or a sequence of coin flips, and ask you to define the states and compute an absorption probability, an expected hitting time or a long-run frequency.
Encode exactly what the future depends on. For "wait until HTH", the states are the longest suffix of the flips so far that matches a prefix of HTH.
Condition on the first transition and solve the linear system for hitting probabilities or expected times, with boundary values at the absorbing states.
For an irreducible, aperiodic chain, πP = π gives the long-run fraction of time in each state, and the expected return time to state i is 1/πᵢ.
A fair walk from k between 0 and N hits N first with probability k/N, and takes k(N − k) steps on average.
Problems marked with a lock are part of Premium.