Markov Chains. Probability question.?

dear divide zero,

right can figure out way (just using conditional probability), , in fact markov chains formalized conditional probability. here primer enable answer question , others:

suppose have system 3 "states" {1, 2, 3}. ball randomly bounces around these states every time step t in {0, 1, 2, 3, 4, 5, …}. thus, every time t ball either in state 1, 2, or 3. let x(t) state of ball @ time t. given x(t) particular state, 2, value of x(t+1) chosen independently probability distribution depends on current state. 3x3 matrix p=(p_{ij}) captures these "next step" probabilities:

p_{ij} = pr[x(t+1)=j | x(t) = i]

thus, matrix p includes of probabilities required simulate ball randomly bouncing around state space. example, suppose in state 1, , want compute probability make following transitions: 1---> 1--->3--->2. independence assumptions, probability p_{11}p_{13}p_{32}. suppose want compute:

pr[x(t+2) = 3 | x(t) = 1].

can work out conditioning on possible values of x(t+1) , using law of total probability. once work out, find (1,3) entry in matrix p^2. more generally:

pr[x(t+k) = 3 | x(t) =1] = (1,3) entry of matrix p^k.

can prove above formula defining row vector v(t) = (pr[x(t)=1], pr[x(t)=2], pr[x(t)=3]) , noticing left-multiplication matrix p works out follows:

v(1) = v(0)p
v(2) = v(1)p
v(3) = v(2)p
v(4) = v(3)p

, on, v(n) = v(0)p^n. if in state 1 probability 1 @ time 0, v(0) = (1,0,0) , v(k) = (1,0,0)p^k. theory of markov chains tells when system converges "steady state probability distribution" regardless of initial distribution v(0). distribution vector v satisfies following:

lim_{n-->infinity} v(n) = v (regardless of v(0))

vector v tells overall likelihood ball in each state. such vector v must satisfy left-eigenvector equation v = vp , must have components sum 1. in fact, solving these linear equations standard way of finding steady state distribution.

***
edit: way, left eigenvector equation v = vp plays big role in how google calculates page rank. imagine virtual web user randomly bouncing around webpages of net according links exist between webpages. simple model assume user randomly , uniformly chooses 1 link list of links current webpage other pages. end result "steady state" probability of visiting particular webpage higher if has many other pages link it, particularly if other pages connected.
http://en.wikipedia.org/wiki/pagerank

p =
( 0.5 0.4 0.1
0.5 0.1 0.4
0.2 0.7 0.1)

calculate p(xt+2 = 3| xt = 1)

help. stuck on one.

Games & Recreation Card Games Next