第13周概率课小结

1. Markov Chain

Idea: Future only depends on present, not the past. $$Future = f(present)$$

TODO

Discrete Time & Finite State

n states: (1), (2), … , (n)

$$P_{ij} = P((i) \rightarrow (j)) = P(X_{k+1} = j | X_k = i)$$

Time homogenous

$$P(X_{k+1} = j | X_{k} = i) = P_{ij} \quad \forall k$$

So $$P(X_{k+1} = j) = \sum_{i=1}^n P(X_{k+1} = j \cap X_k = i) = \sum_{i=1}^n P(X_{k+1} = j | X_k = i)P(X_k = i) \stackrel{\text{if time-homo}}{\rightarrow} \sum_{i=1}^nP_{ij}P(X_k = i)$$

Transition Probability Matrix P

$$P = \begin{bmatrix} P_{11} & P_{12} & P_{13} & \dots & P_{1n} \\ P_{21} & P_{22} & P_{23} & \dots & P_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ P_{n1} & P_{n2} & P_{n3} & \dots & P_{nn} \end{bmatrix}, \quad 0 \leq P_{ij} \leq 1, \sum_{j = 1}^n P_{ij} = 1, \forall i, j$$

• For any pdf $\pi_{1 \times n}: \pi(k) =\pi(0) P^k$

Irreducible / Regular

A Markov chain is irreducible if all the states communicate with each other.

• $P_{n \times n}$ is irreducible/regular if $\exists k > 0: P^k$ is a positive matrix $P_{ij}^{(k)} > 0, \forall i, j$

• $\exists i, P_{ii} = 1 \Rightarrow$ NOT irreducible (除了$P_{1 \times 1}$ = 1)

Period

State i has period d if it can only reoccur at times that are multiples of d, i.e. $P_{ii}(n) = 0$ whenever n is not a multiple of $d$, where $d$ is the largest integer with this property. State $i$ is aperiodic if it has period $d = 1$

Aperiodic

$P$ is aperiodic iff the number of steps needed to move between any two states $(i)$ and $(j)$ is an integer multiple (not forced into fixed cycle)

• P is aperiodic if $\forall$ eigenvalue $\lambda: \lambda \neq -1$

• 若挑选某一状态， gcd(回到该状态的路径和1, 回到该状态的路径和2, …, 回到该状态的路径和n) > 1 $\Rightarrow Periodic$ （详情见笔记）

Basic Limit Theorem

If the transition matrix $P_{n \times n}$ is aperiodic and irreducible, then $P$ has a stationary pdf $\pi_e$
(1) $\displaystyle \pi_eP = \pi_e$ (equilibrium pdf)
(2) $\lim_{k \rightarrow \infty} p^k = \begin{bmatrix} \pi_e \\ \pi_e \\ \vdots \\ \pi_e \end{bmatrix}$

(3) $\displaystyle \lim_{k \rightarrow \infty} u P^k = \pi_e, \forall u \in S^n$

Special case: $2 \times 2$ transition matrix $P$

$$\displaystyle P_{2 \times 2} = \begin{bmatrix}1-a & a \\\ b & 1-b\end{bmatrix} \quad a,b \in [0,1]$$ Then $$\pi_e = (\frac{b}{a+b}, \frac{a}{a+b})$$

2. Optimal Estimators

Estimate the value of an inaccessible rv $X$ in terms of the observation of an accessible rv $Y$.

• Maximum A Posterior (MAP) 最大后验概率估计
Given observation $Y = y$, find the most probable value $x$ for $X$

$$\hat X = \max_{x}P(X = x| Y = y) = \max_x \frac{P(Y = y | X = x) P(X = x)}{P(Y = y)}$$

其中 $P(X = x)$为a priori probability, $P(Y = y| X = x)$ 为likelihood. 因此MAP需要知道a priori probability

若$X$和$Y$都是连续随机变量，则上式也可写作

$$\hat X = \max_{x} f_X(X = x| Y = y)$$

• Maximum Likelihood Estimation (MLE) 最大似然估计
适用于知道$P(Y = y| X = x)$但是不知道a priori probability, so select the estimator value $x$ as the value that maximizes the likelihood of the observed value $Y = y$

$$\hat X = \max_{x}P(Y = y | X = x)$$

若$X, Y$都连续，则亦可写作

$$\hat X = \max_{x} f_X(Y = y| X = x)$$

• Minimum Mean Square Error (MMSE) 最小均方误差

使用mean square error $e = E[(X - \hat X)^2]$ 作为误差估计

- MMSE linear estimator

$$\hat X = E[X] + \rho_{X,Y}\sigma_X \frac{Y - E[Y]}{\sigma_Y}$$

The term $\frac{Y - E[Y]}{\sigma_Y}$ is a standardized version of Y, so $\sigma_X \frac{Y - E[Y]}{\sigma_Y}$ is a rescaled version of Y that has the variance of the r.v.            that is being estimated. The term E[X] ensures the estimator has the correct mean. The correlation $\rho_{XY}$ specifies the            sign and extent of the estimate of Y relative to $\sigma_X \frac{Y - E[Y]}{\sigma_Y}$

- MMSE nonlinear estimator

$$\hat X = E[X| Y = y]$$

- 对jointly gaussian distribution，linear和nonlinear MMSE是一样的

例题

1. 小明每天喝酒，并且有无限量的红酒和白酒储备。If he drinks red wine one day then he is twice as likely to drink white wine the next day than he is to drink red wine. But if he drinks white wine one day then he is three times as likely to drink red wine the next day. 今天是周五，小明喝了白酒。小明表示 on Sunday he will be more likely to than not to drink white wine but that in the long run on any given day he is more likely to drink red wine than white wine. 小明说得对吗？

参考文献

1. 503第13周讨论课笔记
2. 503第13周课堂笔记
3. Garcia, Alberto Leon. “Probability, statistics, and random processes for electrical engineering.” (2008).
4. 盛骤. 谢式千. 潘承毅《概率论与数理统计》第四版，高等教育出版社

附

1. 解：由题意可得transition matrix

       W    R
P = W[1/4  3/4] = [1 - a  a ]
|        |   |         |
R[2/3  1/3]   [b     1-b]


W      R

$\displaystyle \pi_e = [\frac{b}{a+b} \quad \frac{a}{a+b}] = [\frac{\frac{2}{3}}{a+b} \quad \frac{\frac{3}{4}}{a+b}]$