## 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$