Harmonic Analysis-day3

So today’s topic as I mentioned earlier is “Markov Chains”. I shall begin with a definition and then will prove a theorem which can also be taken as a simplified definition.

Definition(Stochastic matrix) A Stochastic matrix P = (p(x,y))_{x,y \in X} is a real valued matrix parametrized by X such that

a) p(x,y) \geq 0 for all x,y

b) \sum_{y \in X} p(x,y) = 1 for all x \in X.

Another definition which would be used soon is

\mu{\xi_{k+1} = x_{k+1} | \xi_0 = x_0, \xi_1 = x_1, \ldots, \xi_k = x_k } = \frac{ \mu{\xi_0 = x_0, \xi_1 = x_1, \ldots, \xi_k = x_k, xi_{k+1} = x_{k+1}}{ \mu{\xi_0 = x_0, \xi_1 = x_1, \ldots, \xi_k = x_k}}

Definition (Markov Chains) Let X be a finite set with probability distribution \nu and stochastic matrix P. A Markov chain with sample space X, probability distribution \nu, transition matrix P is sequence of random variables \xi_0, \xi_1, \xi_2, \ldots, \xi_n: Y \rightarrow X, where (Y, \mu) is a finite measure space such that: 

a) \mu\{ \xi_0= x \} = \nu(x) .

b) \mu{\xi_{k+1} = x_{k+1} | \xi_{0} = x_{0}, \xi_1 = x_1, \ldots, \xi_k = x_k} = p(x_{k}, x_{k+1}).

Theorem~(Equivalent property of being Markov) A finite sequence of variables $\xi_0, \xi_1, \xi_2, \ldots, \xi_n: Y \rightarrow X, with probability distribution \mu on $Y$ and \nu on X is a Markov chain if (*)  \mu\{\xi_0= x_0, \xi_1 = x_1, \ldots, \xi_n=x_n \} = \nu(x_0)p(x_0, x_1)p(x_1, x_2) \cdots p(x_{n-1}, x_n).

and

\nu\{\xi_k = x\} = \sum_{x_0,x_1,x_2,\ldots,x_{k-1} \in X} \nu(x_0)p(x_0, x_1)\ldots p(x_{k-1}, x_k),

\mu\{\xi_{k+1} = x_{k+1} | \xi_{0} = x_{0}, \xi_1 = x_1, \ldots, \xi_k = x_k\} = \mu\{\xi_{k+1} = x_{k+1} | \xi_k = x_k \}

Proof: For the proof we see that if \xi_0, \xi_1, \ldots, \xi_k: Y \rightarrow X is the Markov chain then \mu\{ \xi_0= x_0 \} = \nu(x_0) and further \mu{\xi_1 = x_1, \xi_0 = x_0\} = \mu\{ \xi_0= x_0 \} \mu{\xi_1 = x_1| \xi_0 = x_0\} and therefore is equal to \nu(x_0) p(x_1, x_0). Hence the given formula can be easily proved by induction. Conversely suppose we are given (*), Then by summing over all x_{k+1}, x_{k+2}, \ldots, x_n, we get (*) for all 1 \leq k \leq n. Rest of the theorem follows just by easy calculations.

An intuitive approach: We consider time t to be discrete. Then if at time t = k our point is at x, then the probability of it being at y at time t= k+1 is equal to p(x,y). Thus if the initial stage of the particle is x_0, then the probability that it follows the path (x_0, x_1, \ldots, x_k) is \nu(x_0) p(x_0, x_1) \ldots p(x_{k-1}, x_k). Hence

\nu^k(x) = \sum_{x_0, x_1, x_2, \ldots, x_{k-1}} \nu(x_0) p(x_0, x_1) \ldots p(x_{k-1}, x)

=$latex  \sum{x_0 \in X} \nu(x_0) p^k(x_0, x)$

is the probability that at time t= k particle will be at x

 

Advertisements

About teenjamure

A learner
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Harmonic Analysis-day3

  1. Pingback: Coupling from the Past | Eventually Almost Everywhere

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s