Markov chain and simple random walk.

In this blog, I try to introduce the concept of Markov chain , so first, we give the definition of markov chain. And we state that every markov chain will have a fixed point.

Go back to Main page Notes for Complexity theory

Then we introduce the random walk and how to connect the  concept of Markov Chain and the random Walk. And we proof some basic facts of the expection values.

How to leave the maze without memorize anything using random walk.

附上 wiki 的 Markov Chain  inequality:

If X is a nonnegative random variable and a > 0, then the probability that X is at least a is at most the expectation of X divided by a:

 From the definition of expectation:

${\displaystyle \operatorname {E} (X)=\int _{-\infty }^{\infty }xf(x)\,dx}$

However, X is a non-negative random variable thus,

${\displaystyle \operatorname {E} (X)=\int _{-\infty }^{\infty }xf(x)\,dx=\int _{0}^{\infty }xf(x)\,dx}$

From this we can derive,

${\displaystyle \operatorname {E} (X)=\int _{0}^{a}xf(x)\,dx+\int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }af(x)\,dx=a\int _{a}^{\infty }f(x)\,dx=a\operatorname {P} (x\geq a)}$

From here it is easy to see that

${\displaystyle \Pr(X\geq a)\leq \operatorname {E} (X)/a}$

Chebyshev's inequality

這個東西也重要

for any a > 0. Here Var(X) is the variance of X, defined as:

${\displaystyle \operatorname {Var} (X)=\operatorname {E} [(X-\operatorname {E} (X))^{2}].}$

Chebyshev's inequality follows from Markov's inequality by considering the random variable

${\displaystyle (X-\operatorname {E} (X))^{2}}$

and the constant ${\displaystyle a^{2},}$ for which Markov's inequality reads

${\displaystyle \operatorname {P} ((X-\operatorname {E} (X))^{2}\geq a^{2})\leq {\frac {\operatorname {Var} (X)}{a^{2}}}.}$

This argument can be summarized (where "MI" indicates use of Markov's inequality):

${\displaystyle \operatorname {P} (|X-\operatorname {E} (X)|\geq a)=\operatorname {P} \left((X-\operatorname {E} (X))^{2}\geq a^{2}\right)\,{\overset {\underset {\mathrm {MI} }{}}{\leq }}\,{\frac {\operatorname {E} \left((X-\operatorname {E} (X))^{2}\right)}{a^{2}}}={\frac {\operatorname {Var} (X)}{a^{2}}}.}$