1、An Introduction to Markov Chains Homer and Marge repeatedly play a gambling game. Each time they play,the probability that Homer wins is 0.4, and the probability that Homer loses is 0.6A “Drunkards Walk”P(Homer wins) = .4 P(Homer loses) = .6Homer and Marge both start with $20 1 2 3 401234A Markov Ch

2、ain is a mathematical model for a process which moves step by step through various states. In a Markov chain, the probability that the process moves from any given state to any other particular state is always the same, regardless of the history of the process.A Markov chain consists of states and t

3、ransition probabilities. Each transition probability is the probability of moving from one state to another in one step. The transition probabilities are independent of the past, and depend only on the two states involved. The matrix of transition probabilities is called the transition matrix.P(Home

4、r wins) = .4 P(Homer loses) = .6Homer and Marge both start with $20 1 2 3 4If P is the transition matrix for a Markov Chain, then the nth power of P gives the probabilities of going from state to state in exactly n steps.If the vector v represents the initial state, then the probabilities of winding

5、 up in the various states in exactly n steps are exactly v times the nth power of P .When they both start with $2, the probability that Homer is ruined is 9/13.If Homer starts with $ x and Marge starts with $ N-x, and P(Homer wins) = p, P(Homer loses) = q, then the probability Homer is ruined is Sup

6、pose you be on red in roulette. P(win) = 18/38 = 9/19; P(lose) = 10/19.Suppose you and the house each have $10Now suppose you have $ 10 and the house has $20Now suppose you and the house each have $100. Andrei Markov (1856-1922) Paul Eherenfest: Diffusion model, early 1900sStatistical interpretation

7、 of the second law of thermodynamics: The entropy of a closed system can only increase.Proposed the “Urn Model” to explain diffusion.Albert Einstein, 1905Realized Brownian motion would provide a magnifying glass into the world of the atom. Brownian motion has been extensively modeled by Markov Chain

8、sOsmosisParticles are separated by a semi-permeable membrane, which they can pass through in either direction.There are N+1 states, given by the number of white molecules inside.Suppose that there are N black particles inside the membrane, and N white particles outside the membrane. Each second, one

9、 random molecule goes from outside the membrane to inside, and vice versa.5 molecules0 1 2 3 4 5N moleculesN moleculesIf this process runs for a while, an interesting question is: How much time, on average, is the process in each state?A Markov chain with transition matrix P is said to be regular if

10、 some power of P has all positive entries for some n. In a regular Markov chain, it is possible to get from any state to any other state in n steps.The Markov chain for our osmosis process is regular. Even starting with all black particles inside, if a white particle entered at every step, then the

11、process would pass from zero white inside through all possible states. For a regular Markov chain, the amount of time the process spends in each state is given by the fixed probability vector, which is the vector a such that Pa = a. Moreover, for any probability vector w, No matter what the starting

12、 state, if the process runs for a long time, the probability of being in a given state is given by a.In the long run, the fraction of time the process spends in each state is given by the fixed probability vector. For N particles, the fixed vector is: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1Fixed vectorsN = 4 (1/70, 16/70, 36/70, 16/70, 1/70)Now suppose 500 moleculesThe percent of the time that there are between 225 and 275 black molecules inside is 0.999.The percent of the time that there are either fewer than 100 black or more than 400 black mole