Stationary Process

• stationary: $P(X_1=x_1,X_2=x_2,\cdots,X_n=x_n)=P(X_{1+l}=x_1,X_2=x_{2+l},\cdots,X_{n+l}=x_n)$
  • Gaussian process
  • Stationary Markov Chain
• Stationary Distribution of MC
  • $p(X_{n+1})=p(X_n)$
  • $p(x_{n+1})=\sum_{x_n}p(x_n)P_{x_nx_{n+1}}$
  • net probability flow across any cut set is zero

Entropy Rate

• entropy rate of a stochastic process: $H(\mathcal{X})=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_1,X_2,\cdots,X_n)$
  • $H(X_n,\cdots,X_1)=\sum_{i=1}^nH(X_i|X_{i-1},\cdots,X_1)$
• (a) For a stationary stochastic process, $H(X_n|X_{n-1},\cdots,X_1)$ is nonincreasing and has a limit
  • $H’(X)=\lim_{n\rightarrow\infty}H(X_n|X_{n-1},\cdots,X_1)$ exists
• (b) Cesaro Mean: $a_n\rightarrow a,b_n=\frac{1}{n}\sum_{i=1}^na_i,b_n\rightarrow a$
• For a stationary stochastic process, $H(\mathcal{X})=H’(\mathcal{X})$ (a,b)
  • Markov Chain: $H(\mathcal{X})=H(X_2|X_1)=-\sum_{ij}\mu_iP_{ij}\log P_{ij}$
• Some results
  • Second Law of Thermodynamics: model the isolated system as a Morkov chain with transitions obeying the physical laws governing the system
  • $D(\mu_n|\mu_n’)$ decreases with $n$
  • $H(X_n|X_1)$ increases
  • Shuffles increase entropy: $H(TX)\geq H(X)$

Functions of Markov Chain

• $X_1,\cdots,X_n,\cdots$ be a stationary Markov chain, $Y_i=\phi(X_i)$
• $H(Y_n|Y_{n-1},\cdots,Y_1,X_1)\leq H(\mathcal{Y})\leq H(Y_n|Y_{n-1},\cdots,Y_1)$
• $\lim H(Y_n|Y_{n-1},\cdots,Y_1,X_1)= H(\mathcal{Y})= \lim H(Y_n|Y_{n-1},\cdots,Y_1)$