对于为什么叫 countable-state，我一直不理解。。。。明明state是infinite的=。=不过一旦在infinite的情况下，很多东西就要改变了。
还是从state说起
在markov chain中，我们对每个state都分成了2类：recurrent和transient，并且证明了如果markov chain为ergodic，必然会收敛。这个简单的东西放在这里就不简单了。
还是以掷硬币为例，正面的1分，反面扣1分。这个过程用markov chain描绘的话如下：
我们可以直观的看到，当 $p\neq1-p$ 时，整个链条要不向左，要不向右无限扩展。但是这个markov chain的period为2，我们做个截断，让他变成1：
但是如果 $p>\dfrac{1}{2}$ 的话，整个链条仍然会无限扩展，依然没有稳定状态。而 $p=\dfrac{1}{2}$ 时，停留在每个state的概率都趋向于0。这是一个很特殊的状态，被称为 null-recurrent。
为了对countable-state markov chain的state进行定义，我们引入以前提过的first-passage-time probability的概念，其定义为 $f_{ij}(n)=Pr\left\{X_n=j,X_{n-1}\neq j,X_{n-2}\neq j...X_1\neq j | X_0 = i\right\}$ 。当然了 $i=j$ 是允许的。
在first-passage-time的基础上，引入 $F_{ij}(n) = \sum_{m=1}^n f_{ij}(m)$
我们可以定义 rv $T_{ij}$ 为从state i出发，第一次到达state j。 则 $f_{ij}$ 可以视为 $T_{ij}$ 的PMF，而 $F_{ij}$ 可以视为 $T_{ij}$ 的分布函数。
在此基础上，我们可以对state进行定义：state j is recurrent if $F_{jj}(\infty) = 1$ ；is transient if $F_{jj}(\infty) < 1$
根据 $F_{ij}(n)$ 的定义，可知
$F_{ij}(n) = P_{ij} + \sum_{k\neq j}P_{ik}F_{kj}(n-1)$
当 $n\to\infty$ 时，等式依然成立，因此我们联立多个方程就可以求解。当然，理论上来说，无论如何 $F_{ij}(n)=1$ 都是可行解。但是当state为transient时，还存在一组“非1解”(+ _ +) 。
我们令 $N_{jj}(t)$ 表示从state j出发，在t时间内到达 state j的次数。则下面四个描述是等价的：
- state j is recurrent
- $\lim_{t\to\infty} N_{jj}(t) = \infty$ WP1
- $\lim_{t\to\infty} E[N_{jj}(t)] = \infty$
- $\lim_{t\to\infty} \sum_{1\le n\le t} P_{jj}^n = \infty$
有了上面的结论，很容易证明当state i和j互相可达，state j为recurrent时，state i也是recurrent ($\sum_{n=1}^\infty P_{ii}^n \ge \sum_{n=1}^\infty P_{ii}^{m+n+k}\ge P_{ik}^mP_{kj}^k\sum_{n=1}^\infty P_{kk}^n$)。
所以对于 countable-state markov chain 来说，一个class中所有的state都是transient或者recurrent的。
对于同处于一个recurrent class的state i和j来说， $F_{ij}(\infty) = 1$ 。
证明：令 $\alpha$ 表示从 i到j的概率。则从state i 出发第一次回到state i 而不经过state j的概率必不大于 $1-\alpha$ ；第二次必不大于 $(1-\alpha)^2$ … 第n次 必不大于 $(1-\alpha)^n$ 。当 $n\to\infty$ 时，必有 $F_{ij}(\infty) = 1$
对于处于同一个recurrent class的state i和j，若 $i\neq j$ ，则 $N_{ij}(t)$ 为delay renewal process。我们令 $\bar{T}_{ij}$ 表示state i到j的first-passage time的期望。则 $\bar{T}_{ij} = 1 + \sum_{i=1}^\infty (1-F_{ij}(n))$ 。直观上看，如果 $F_{ij}(\infty)=1$ ，$\bar{T}_{ij}$ 必然为finite。但是在讨论birth-death markov chain时，我们会发现存在 $F_{ij}(\infty)=1$ 而 $\bar{T}_{ij} = \infty$ 的情况。因此recurrent state有必要进行分类。
我们将 $F_{jj}(\infty)=1, \bar{T}_{jj} < \infty$ 的state j称为 positive-recurrent；$F_{jj}(\infty)=1, \bar{T}_{jj} = \infty$ 的state j称为 null-recurrent。
我们可以看到 $T_{jj}$ 是IID rv，所以 $N_{jj}(T)$ 可以视为renewal process。根据renewal process的性质，可知：
$$\lim_{t\to\infty} \dfrac{N_{jj}(t)}{t} = \dfrac{1}{\bar{T}_{jj}}\\
\lim_{t\to\infty} E\Big[\dfrac{N_{jj}(t)}{t}\Big] = \dfrac{1}{\bar{T}_{jj}}$$
根据Blackwell’s theorem，有
$\lim_{n\to\infty} Pr\left\{X_{n\lambda} = j | X_0 = j\right\} = \dfrac{\lambda}{\bar{T}_{jj}}$
而在markov chain中， $\lambda$ 就是period。
上面的结论对于 $N_{ij}$ 同样成立
在markov chain中，同一个class中所有的state都是一样的，即都是positive-recurrent,null-recurrent或者transient。前面我能已经证明了recurrent和transient的情况，因此这里我们只需要证明positive-recurrent和null-recurrent。
首先证明positive-recurrent的情况。令 $R(t) =1$ 当t时刻在state i。根据renewal-reward process，有
$\dfrac{1}{\bar{T}_{ii}} = \lim_{t\to\infty}\dfrac{1}{t}\int^t_0R(\tau)d\tau = \dfrac{E[R_n]}{\bar {T}_{jj}}$
第一个等号成立是因为我们可以将 $\lim_{t\to\infty}\dfrac{1}{t}\int^t_0R(\tau)d\tau$ 视为停留在state i的时间占总时间的比值，而我们在前面计算出了这个比值。显而易见，当state j为positive-recurrent时，$T_{jj} < \infty$，故 $T_{ii} < \infty$ 。反之也成立。
对于停留时间的比例这种东西，敏感的人可能会将它和 $\pi_j$ 对应。对于 irreducible的markov chain来说，确实如此。irreducible markov chain就是所有的state都在同一个recurrent class里面。
证明：令 $\pi_j$ 为markov chain的初始概率分布，$\tilde{N}(t)$ 为在时间1到t之间出现在state j的次数。则
$$(1/t)E[\tilde{N}(t)] = (1/t)\sum_{1\le n\le t} Pr\left\{X_n=j\right\} = \pi_j\\
\pi_j = (1/t)E[\tilde{N}_j(t)] = \sum_i \pi_iE[N_{ij}(t)]\ge \sum_{i\le M} \pi_iE[N_{ij}(t)]\\
E[N_{ij}(t)] \le E[N_{ij}(T_{ij}+t)] = 1+E[N_{jj}]\\
\Rightarrow \pi_j \le 1/t + E[N_{jj}(t)/t]\\
\Rightarrow \lim_{t\to\infty}\pi_j = \pi_j \le \lim_{t\to\infty} (1/t + E[N_{jj}(t)/t])=1/\bar{T}_{jj}\\
\lim_{t\to\infty}\pi_j = \pi_j \ge \lim_{t\to\infty}\sum_{i\le M} \pi_iE[N_{ij}(t)] = \sum_{i\le M} \pi_i/T_{jj} \ge 1/T_{jj}\\
\Rightarrow \pi_j = 1/T_{jj}$$
Age of renewal process
我们用下图的markov chain 描绘renewal的interval
其中 $P_{n,n+1} = Pr\left\{W>n+1\right\}/Pr\left\{W>n\right\}$ ，$Pr\left\{W>n\right\}$ 表示interval大于n个时间单元， $Pr\left\{W>0\right\} =1$
故
$$\begin{aligned}
\pi_n &= \pi_{n-1}P_{n-1, n} = \pi_{n-2}P_{n-2,n-1}P_{n-1, n}= \pi_0P_{0,1}...P_{n-1, n}\\
&= \pi_0\dfrac{Pr\left\{W>1\right\}Pr\left\{W>2\right\}...Pr\left\{W>n\right\}}{Pr\left\{W>0\right\}Pr\left\{W>1\right\}...Pr\left\{W>n-1\right\}} = \pi_0Pr\left\{W>n\right\}
\end{aligned}$$
故
$$\pi_0 = \dfrac{1}{\sum_{n=0}^\infty Pr\left\{W>n\right\}} = \dfrac{1}{E[W]}\\
\pi_n = \dfrac{Pr\left\{W>n\right\}}{E[W]}$$
birth-death markov chain
birth-death markov chain如下图所示：
从state i转移到 state i+1的次数可以表示为 $\pi_ip_i$ ，其中 $\pi_i$ 为系统稳定时在state i的概率。类似的，将state i+1转移到 state i的次数表示为 $\pi_{i+1}q_i$ 。若系统存在稳定状态，则 $\pi_ip_i = \pi_{i+1}q_i$
令 $\rho_i=p_i/q_{i+1}$ ，则有 $\pi_j = \rho_i\pi_i$ 。故
$$\pi_i = \pi_0\prod_{j=0}^{i-1}\rho_i\\
\pi_0 = \dfrac{1}{1+\sum_i^{\infty}\prod_{j=0}^{i-1}\rho_i}$$
Reversible markov chain
根据markov chain的定义有：
$$Pr\left\{X_{n+1}|X_n,X_{n-1}...X_0\right\} = Pr\left\{X_{n+1}|X_n\right\}\\
Pr\left\{X_{n+k}, X_{n+k-1}, ...X_{n+1}|X_n,X_{n-1}...X_0\right\} = Pr\left\{X_{n+k}, X_{n+k-1}, ...X_{n+1}|X_n\right\}$$
令 $A^+$ 表示 state $X_{n+1}$ 到 $X_{n+k}$ 的任意事件； $A^-$ 表示 state $X_{1}$ 到 $X_{n-1}$ 的任意事件。则：
$$Pr\left\{A^+|X_n, A^-\right\} = Pr\left\{A^+|X_n\right\}\\
Pr\left\{A^+, A^-|X_n\right\} = Pr\left\{A^+|X_n\right\}Pr\left\{A^-|X_n\right\}\\
Pr\left\{A^-|X_n, A^+\right\} = Pr\left\{A^+|X_n\right\}\\
\Rightarrow Pr\left\{X_{n-1}|X_n\right\} = \dfrac{Pr\left\{X_n|X_{n-1}\right\}Pr\left\{X_{n-1}\right\}}{Pr\left\{X_n\right\}}$$
很容易发现， $Pr\left\{X_{n-1}|X_n\right\}$ 是随 $n$ 而改变的。因此backward markov chain不一定为homogeneous(即满足 $Pr\left\{X_{n+1}|X_n\right\}=Pr\left\{X_1|X_0\right\}$)。对于steady-state来说， $Pr\left\{X_{n+1}=j\right\} = Pr\left\{X_n=j\right\} = \pi_j$ 。此时，
$Pr\left\{X_{n-1} = j|X_n = i\right\} = P_{ji}\pi_j/\pi_i$
如果我们令 $P_{ij}^*$ 表示backward markov chain的转移概率，则有 $\pi_i P_{ij}^* = \pi_j P_{ji}$ 。而对于steady-state markov chain来说，必有 $\pi_i P_{ij} = \pi_j P_{ji}$ 。故我们可以推出 $P_{ij}^* = P_{ij}$
对于irreducible markov chain来说，如果对于所有的 $i,j$ 都有 $\pi_i P_{ij} = \pi_j P_{ji}$ 则 $\pi_i$ 就是其steady-state的分布；而它本身则是reversible。
假设irreducible markov chain的转移概率为 $P_{ij}$ ，$\pi_i$ 是和为1的正数集合，$P_{ij}^*$ 是转移概率，如果有
$\pi_iP_{ij} = \pi_jP_{ji}^*$
则 $\pi_i$ 是steady-state分布， $P_{ij}^* {}$ 是backward chain的转移概率。
M/M/1 queue
现用 markov chain 建模M/M/1 queue。假设 arrival rate为 $\lambda$ ，departure rate 为 $\mu$ 。还是将时间划分多个无穷小的等分，每等分的时间为 $\delta$ 。则M/M/1 queue可以表示为：
这被称为M/M/1 sample-time Markov chain
根据上节的描述，则有：
$$\rho = \lambda / \mu < 1\\
\pi_i = \pi_0 \rho ^i \\
\Rightarrow \pi_i = (1-\rho) \rho^i$$
而这个chain本身就是birth-death chain。当 $\rho <1$ 时，它是reversible。左移和右移的过程有一些相似点：
- 都可以被视为 M/M/1 chain
- 左移的arrival可以被视为右移的departure
由此我们可以总结出：
- departure也是 Bernoulli
- $n\delta$ 时刻的状态 $X_n$ 与之前的departure没有关系。
这被称为Burke’s theorem。Burke’s theorem并不需要 $\mu$ 对于所有的state保持一致，因此对于任何birth-death chain来说，只要arrival和当前的state无关(比如G/G/m queue)，就可以使用。
#Branching process
Branching process是一种特殊的markov chain，其 $X_{n+1},X_n$ 的关系为：
$$\begin{equation}
\label{eq:branch}
X_{n+1} = \sum_{k=1}^{X_n} Y_{k,n}
\end{equation}$$
其中 $Y_{k,n}$ 为rv ， $p_j = Pr\left\{Y_{k,n}= j\right\}$ ， $P_{ij} = Pr\left\{X_{n+1}= j|X_{n}= i\right\} = Pr\left\{\sum_{k=1}^iY(k,n) = j\right\}$
看上去很复杂，其实过程很简单。假设有一种生物只能活一年，每年可以自交(ˉ▽ˉ；)产生后代。我们在第一年养一只，然后每年统计种群的个数。在这个问题中，每个个体产生后代的数量就是 $Y_{k,n}$ ，$k,\ n$分别表示个体的标号以及时间。 而我们最关注的问题就是这个种群会不会灭绝，也就是 $X_n=0$
在前面我们将 $F_{ij}(n)$ 定义为 $X_0=i$ 在n时刻前访问state j的概率。因此我们的问题可以形式化为 $F_{i0}(n)$ 。每个个体时候产生后代是独立的，因此有 $F_{i0}(n) = {F_{10}(n)}^i$ 。所以显然，我们需要计算出 $F_{10}(n)$ 。
$F_{10}(n)= P_{10} + \sum_{k=1}^\infty P_{1k}[F_{10}(n-1)]^k = \sum_{k=0}^\infty P_{1k}[F_{10}(n-1)]^k$
令 $h(z) = \sum_k P_{1k}z^k$ ，则 $F_{10}(n) = h(F_{10}(n-1))$ 。通过函数，我们可以找到 $h(z)$ 的一些性质：
- $h(z) = z$ 必有解 $z = 1$
- $h'(1) = \sum_k kP_{1k} = \bar{Y}$
- $h''(z) \ge 0 \text{ for } 0\le z\le 1$
- $h(0) = P_{10} = p_0$
通过上面的结论，可以发现 $h(z)$ 为凸函数，所以我们可以画出其图像：
我们可以看到当 $\bar{Y} < 1$ 时， $F_{10}(\infty) = 1$
由 \ref{eq:branch} 可知：
$E[X_n] = \bar{Y}E[X_{n-1}] = {\bar{Y}}^nE[X_0]$
通过期望，我们可以看到上面的结论。但是需要注意的是，通过这种方式并不能真实的反映出 $E[X_n]$ 。对于 $\bar{Y} = 1, X_0=1$ 来说， $E[X_n]=1$ 但是 $h(\infty)$ 是无限趋向于1的。在这种情况下，种群内个体数量极少的可能性极大，但是通过期望，我们看不到这一点。
Round-robin and process sharing
在排队过程中，如果我们优先处理服务时间较短的客户，那么整体的delay(即renewald的 $U(t)$ )就会下降。实际场景往往不允许这种事情发生。计算机系统中也面临这种问题，而通常的处理方法是Round-robin，即处理A一会，然后处理B。。。轮流一圈之后继续处理A。而每个任务的处理时间 $\delta$ 都是一样的，即处理A $\delta$ 之后处理B。。。。
process sharing也是一样的，不过其 $\delta = 1/m$ ，$m$ 为任务数量。
下面我们证明通过Round-robin可以降低队伍的平均delay。令 $W_i$ 表示第 $i$ 个任务所需的服务时间， $f(j) = Pr\left\{W_j = j\delta\right\}, \bar{F}(j)= Pr\left\{W_j > j\delta\right\}$ ，则用户在j次服务之后还需要一次服务的概率 $g(j) = f(j+1)/\bar{F}(j)$ 。
这里还需要 state s。我们将s定义为 $s = (m, z_1, z_2...z_m)$ ，其中m为用户数， $z_i\delta$ 是第 $i$ 个用户的总服务时间。
我们在已知state $X_n$ 的情况下，可能会发现下面几种情况：
- 来了新用户(概率为 $\lambda\delta$)，被首先处理
- 队首用户接受服务，时长为 $\delta$
- 该用户可能离开
- 该用户不离开，转到队尾。
总结一下，就是4种情况：
- 没人来没人走， 概率记为 $P_{s,r(s)}$
- 有人来没人走， 概率记为 $P_{s,a(s)}$
- 没人来有人走， 概率记为 $P_{s,d(s)}$
- 有人来了就走， 概率记为 $P_{s,s}$
则有：
$$\begin{aligned}
P_{s,r(s)} &= (1-\lambda\delta)[1-g(z_1)] \quad r(s)=(m,z_2...z_m,z_1+1)\\
P_{s,d(s)} &= (1-\lambda\delta)g(z_1)\quad d(s)=(m-1, z_2...z_m,1)\\
P_{s,a(s)} &= \lambda\delta[1-f(1)]\quad a(s)=(m+1,z_1, z_2...z_m,1)\\
P_{s,s} &= \lambda\delta f(1)
\end{aligned}$$
现在我们通过backward chain找到steady-state的分布。backward的过程中，有几点需要注意：
- 原来的队尾成了队首
- $z_i\delta$ 是第 $i$ 个用户还需要的服务时间
通过这种转换，我们可以求出$P^*$
$$P_{r(s),s}^* = 1-\lambda\delta \\
P_{a(s),s}^* = 1-\lambda\delta \\
P_{d(s),s}^* = \lambda\delta f(z_1+1) \\
P_{s,s}^* = 1-\lambda\delta f(1) \\$$
通过 $\pi_iP_{ij} = \pi_j P^*_{ji}$ ，带入上式( $d(s)$ 的式子 )，可以求出：
$\pi_s = \dfrac{\lambda\delta}{1-\lambda\delta} \bar{F}(z_1)\pi_{d(s)}$
注意到我们可以通过 $\pi_{d(s)}, \pi_{d(d(s))}$ 的递推关系，得到：
$\pi_s = \Big(\dfrac{\lambda\delta}{1-\lambda\delta}\Big)^2 \bar{F}(z_1)\bar{F}(z_2)\pi_{d(d(s))} = ... =\Big(\dfrac{\lambda\delta}{1-\lambda\delta}\Big)^m \Big(\prod_{j=1}^m\bar{F}(z_j)\Big)\pi_{\emptyset}$
当然，如果你不嫌麻烦，可以带到上面剩下的3个式子里面一一验证，应该是可以通过的。
我们定义 $P_m = \sum_{z1, z_2...z_m}\pi(m, z_1, z_2,...,z_m)$ 为系统中存在m个用户的概率。则
$P_m = \Big(\dfrac{\lambda\delta}{1-\lambda\delta}\Big)^m \Big(\prod_{j=1}^m\sum_{i=1}^\infty\bar{F}(i)\Big)\pi_{\emptyset}$
又因为 $\delta \sum_{i=1}^\infty\bar{F}(i) = E[W]-\delta$ 故 $P_m = \Big(\dfrac{\lambda}{1-\lambda\delta}\Big)^m \Big(E[W]-\delta\Big)^m\pi_{\emptyset}$ 。令 $\rho = \Big(\dfrac{\lambda}{1-\lambda\delta}\Big) \Big(E[W]-\delta\Big)$ ，则 $\pi_{\emptyset} = 1-\rho, P_m = \rho^m(1-\rho)$
除了 $\rho$ 的值不一样外，这和 M/M/1 queue 是一样的，得证
对于process sharing的过程来说，过程是一样的，只是 $\delta\to\infty$ 而已。