Stochastic Processes and Reinforcement Learning
看我能坚持多久。。。
Markov Chains
划了重点的教材捏（prof 划的，虽然我感觉他把整本书划了一遍。。。）
Gambling Problems
有 \(S\) 块钱，\(A\) 有 \(K\) 块钱，\(B\) 有 \(S-K\) 块。每次有 \(p\) 的概率 \(A\) 从 \(B\) 拿走一块，\(q=1-p\) 的概率 \(B\) 从 \(A\) 拿走一块。谁拿到 \(S\) 块钱就算赢。
\[X_{n+1}=\begin{cases} X_n+1 & p \\ X_n-1 & q \end{cases}\]\(f_S(k)\) 表示 \(A\) 赢的概率。很显然我们有：
\[f_S(k)=pf_{S}(k+1)+qf_{S}(k-1)\]不难解出
\[f_S(k)=\frac{(p/q)^{S-k}-1}{(p/q)^S-1}\]\(T_{0, S}\) 表示一个游戏啥时候结束，\(h_S(k)=\mathbb{E}\left[T_{0, S}\mid X_0=K\right]\)。
很显然
\[h_S(k)=1+ph_S(k+1)+qh_S(k-1)\]这个方程的特解比较难搞，注意到 \(p+q=1\)，我们可以改写成差分方程：
\[-1=p\left(h_S(k+1)-h_S(k)\right)+q\left(h_S(k)-h_S(k-1)\right)\]观察出方程在 \(p\neq q\) 的时候一个特解为 \(\frac{k}{q-p}\)。
不难解出齐次方程 \(h_S(k)=ph_S(k+1)+qh_S(k-1)\) 的解，最终可以得到在 \(p\neq q\) 时
\[h_s(k)=\frac{1}{q-p}\left(k-S\cdot\frac{1-(q/p)^k}{1-(q/p)^S}\right)\]当 \(p=q=\frac{1}{2}\) 时，我们有特解 \(-k^2\)。所以说 \(p=q\) 时
\[h_S(k)=k(S-k)\]Random Walks
Bernoulli Random Walks: \(X_n\) 相互独立，其中
\[\begin{cases} \mathbb{P}(X_k=+1)=p \\ \mathbb{P}(X_k=-1)=q \end{cases}\]\(p+q=1\)，然后我们定义
\[S_n=\sum_{i=1}^nX_i\]很显然 \(\mathbb{P}(S_{2n}=2k+1)=\mathbb{P}(S_{2n+1}=2k)=0\)，然后
\[\begin{cases} \mathbb{P}(S_{2n}=2k)=\binom{2n}{n+k}p^{n+k}q^{n-k} \\ \mathbb{P}(S_{2n+1}=2k+1)=\binom{2n+1}{n+k+1}p^{n+k+1}q^{n-k} \end{cases}\]难度在我们怎么计算他啥时候回到 \(0\)。我们令
\[T_0^r=\inf\{n\geq 1: S_n=0\}\]表示第一次回到 \(0\) 的时间。
然后我们设
\[g(n)=\mathbb{P}\left(T_0^r=n\mid S_0=0\right)\]也就是在第 \(n\) 步第一次回到 \(0\) 的概率。那很显然 \(g(2k+1)=0\)。
接下来是一个比较神奇的套路，就是我们假设 \(h(n)\) 为第 \(n\) 步回到 \(0\) 的概率，那我们可以得到一个卷积式子：
\[h(n)=\sum_{k=0}^{n-2}g(n-k)h(k)\]也就是先走 \(n-k\) 步第一次回到 \(0\)，然后继续走 \(k\) 步回到 \(0\)。所以我们现在只要解决 \(h\) 就可以了。
我们考虑 \(h(n)\) 的生成函数
\[H(s)=\mathbb{E}\left[s^{T_0^r}\cdot\mathbb{1}_{T_0^r<\infty}\right]=\sum_{n=0}^\infty h(n)s^n\]大概推推：
\[\begin{aligned} H(s)&=\sum_{n=0}^\infty h(n)s^n\\ &=\sum_{n=0}^\infty\binom{2n}{n}p^nq^ns^{2n}\\ &=\sum_{n=0}^\infty\frac{(2n)!}{(n!)^2}\left(pqs^2\right)^n\\ &=\sum_{n=0}^\infty\frac{\left(\prod_{i=1}^n2i\right)\left(\prod_{i=1}^n(2i-1)\right)}{(n!)^2}\left(pqs^2\right)^n\\ &=\sum_{n=0}^\infty\frac{\prod_{i=1}^n(2i-1)}{n!}\left(2pqs^2\right)^n\\ &=\sum_{n=0}^\infty\frac{(-2)^n\prod_{i=1}^n\left(-\frac{1}{2}-(i-1)\right)}{n!}\left(2pqs^2\right)^n\\ &=\sum_{n=0}^\infty\frac{\left(-\frac{1}{2}\right)^{\underline{i}}}{n!}\left(-4pqs^2\right)^n\\ &=\left(1-4pqs^2\right)^{-\frac{1}{2}} \end{aligned}\]又考虑到：
\[\begin{aligned} G(s)H(s)&=\left(\sum_{i=1}^\infty s^ig(i)\right)\left(\sum_{j=0}^\infty s^jh(j)\right)\\ &=\sum_{i=2}^\infty\sum_{j=0}^\infty s^{i+j}g(i)h(j)\\ &=\sum_{k=2}^\infty s^k\sum_{i=2}^\infty g(i)h(k-i)\\ &=\sum_{k=2}^\infty s^k h(k)\\ &=-1 + \sum_{k=0}^\infty s^kh(k)\\ &=-1 + H(s) \end{aligned}\]于是乎
\[G(s)=1-\frac{1}{H(s)}=1-\sqrt{1-4pqs^2}\]所以
\[\begin{aligned} \mathbb{P}\left(T_0^r=\infty\mid S_0=0\right)&=1-\mathbb{P}\left(T_0^r<\infty\mid S_0=0\right)\\ &=1-G(1)=\sqrt{1-4pq}\\ &=\sqrt{4p^2-4p+1}\\ &=\lvert 2p-1\rvert\\ &=\lvert p-q\rvert \end{aligned}\]而根据前面的 Gambling Problems，其实我们已经解出当 \(k\neq 0\) 时：
\[\mathbb{P}\left(T_0^r=\infty\mid S_0=k\right)=1-\lim_{S\to\infty}f_S(k)=\max\left\{0, 1-\left(\frac{q}{p}\right)^k\right\}\]然后我们来计算 \(\mathbb{E}\left[T_0^r\mid S_0=0\right]\) 的时候会发现如果 \(\mathbb{P}\left(T_0^r\mid S_0=0\right)>0\) 的时候这个期望肯定是 \(\infty\)。而 \(\mathbb{P}\left(T_0^r\mid S_0=0\right)\) 只有在 \(p=q=\frac{1}{2}\) 的时候才会为 \(0\)。然鹅当 \(p=q=\frac{1}{2}\) 时：
\[\mathbb{E}\left[T_0^r\mid S_0=0\right]=\mathbb{E}\left[T_0^r \cdot\mathbb{1}_{\left\{T_0^r<\infty\right\}}\mid S_0=0\right]=\left.\frac{\partial G}{\partial s}\right|_{s=1}=\infty\]所以我们不管 \(p, q\) 都有：
\[\mathbb{E}\left[T_0^r\mid S_0=0\right]=\infty\]关于 first time 的 distribution 的话，我们不难算出
\[\mathbb{P}\left(T_0^r=2k\mid S_0=0\right)=\frac{1}{(2k)!}\left.\frac{\partial^{2k}G}{\partial s^{2k}}\right|_{s=0}=\frac{1}{2k-1}\binom{2k}{k}(pq)^k\]Discrete-Time Markov Chains
Markov property 指的是下一步的 distribution 只跟当前有关：
\[\mathbb{P}\left(Z_{n+1}=j\mid Z_n=i_n, \cdots, Z_0=i_0\right)=\mathbb{P}\left(Z_{n+1}=j\mid Z_n=i_n\right)\]\(\pi_n\) 是行向量，转移方程
\[\pi_{n+1}=\pi_n P\]首先研究 hitting probabilities。假设状态空间为 \(\mathbb{S}\)，现在有一个点集 \(A\subset\mathbb{S}\) 是吸收点。也就是说 \(\forall s\in\mathbb{S}, P_{s, s}=1\)。我们康康从 \(k\) 开始被 \(A\) 中哪个点吸收的分布：
\[g_l(k)=\mathbb{P}\left(Z_{T_A}=l\mid Z_0=k\right)\]其中 \(T_A\) 表示第一次撞到 \(A\) 的概率。
显然
\[g_l(k) = P_{k, l} + \sum_{m\in\mathbb{S}\setminus A}P_{k, m} g_l(m)\]然后我们研究从一个点开始期望多久被吸收，我们定义：
\[h_A(k) = \mathbb{E}\left[T_A\mid Z_0=k\right]\]显然
\[h_A(k) = 1 + \sum_{m\in\mathbb{S}\setminus A}P_{k, m} h_A(m)\]当然很多事会我们会钦定最后 \(d\) 个为吸收点，也就是：
\[P = \begin{bmatrix} Q & R \\ 0 & I_d \\ \end{bmatrix}\]酱一来我们就可以简单地写成
\[h_A = \mathbb{1}_{n-d} + Qh_A\]当然很多时候我们每个点都是有个 utility 的，也就是说：
\[h_A(k) = \mathbb{E}\left[\sum_{n=0}^{T_A}r(Z_n)\mid Z_0=k\right]\]那酱的话就把 \(\mathbb{1}\) 换成 \(r\) 就可以了。
接下来是 return times。我们定义 \(T_j^r\) 为第一次到 \(j\) 的时间（但不是 \(Z_0\)）：
\[T_j^r = \inf\{n\ge 1: Z_n=j\}\]然后 \(\mu_j(i)\) 表示从 \(i\) 开始第一次回到 \(j\) 的期望时间：
\[\mu_j(i) = \mathbb{E}\left[T_j^r\mid Z_0=i\right]\]酱紫 \(\mu_i(i)\) 就成功定义了“return times”。
显然：
\[\mu_j(i) = 1 + \sum_{m\in\mathbb{S}}P_{i, m}\mu_j(m)\]我们接下来定义 \(p_{i, j}\) 为从 \(i\) 能走到 \(j\) 的概率，当然一开始不算：
\[p_{i, j} = \mathbb{P}\left(T_j^r<\infty\mid Z_0=i\right)\]我们定义 \(f_{i, j}^{(n)}\) 为从 \(i\) 开始走 \(n\) 步恰好第一次走到 \(j\) 的概率：
\[f_{i, j}^{(n)} = \mathbb{P}\left(T_j^r=n\mid Z_0=i\right)\]显然
\[p_{i, j} = \sum_{n=1}^\infty f_{i, j}^{(n)}\]Number of returns 被定义为：
\[R_j = \sum_{n=1}^\infty\mathbb{1}_{\{Z_n=j\}}\]那么 \(R_j\) 的分布其实是：
\[\mathbb{P}(R_j = m \mid Z_0 = i) = \begin{cases} 1 - p_{i, j} & m = 0 \\ p_{i, j}\cdot p_{j, j}^{m - 1}\cdot (1 - p_{j, j}) & m \ge 1 \end{cases}\]那期望也好算：
\[\mathbb{E}[R_j \mid Z_0 = i] = \sum_{m = 1}^\infty m\cdot p_{i, j}\cdot p_{j, j}^{m - 1}\cdot (1 - p_{j, j}) = \frac{1}{1 - p_{j, j}}\]所以说我们得到一个性质就是，如果要
\[\mathbb{E}[R_i\mid Z_0=i] = \frac{1}{1 - p_{i, i}}\]这个东西有穷，当且仅当 \(p_{i, i} < 1\)。
而还有一个意义比较明确而且封闭的式子是：
\[\mathbb{E}[R_j\mid Z_0=i] = \mathbb{E}\left[\mathbb{1}_{\{X_n=j\}}\mid X_0=i\right] = \sum_{n=1}^\infty\left[P^n\right]_{i, j} = -\mathbb{1}_{\{i=j\}} + \left[(I - P)^{-1}\right]_{i, j}\]Branching Processes
一开始我有一个东西，然后没过一段时间这个东西随机分裂成 \(Y\) 个一样的东西，然后一直这样分裂下去。
\[X_0 = 1, X_{n+1} = \sum_{k=1}^{X_n} Y_k\]其中
\[\mathbb{P}(Y < \infty) = \sum_{n\ge 0}\mathbb{P}(Y = n) = 1\]考虑转移矩阵 \(P\)，\(P_{i,j}\) 表示 \(i\) 个东西分裂成 \(j\) 个的概率。显然 \(P_{0,0}=1\)，没有东西就无法分裂。\(P_{1, j}=\mathbb{P}(Y=j)\)，指的是从一个东西分裂开来。
酱紫的话是个树状结构，所以叫 Branching Process。
考虑生成函数 \(G_n(s) = \mathbb{E}\left[s^{X_n}\mid X_0 = 1\right]\) 表示第 \(n\) 代的概率生成函数，我们有：
\[G_{n+1}(s) = G_n(G_1(s)) = G_1(G_n(s))\]证明的话：
\[\begin{aligned} G_{n+1}(s) &= \mathbb{E}\left[s^{X_{n+1}}\mid X_0 = 1\right]\\ &=\mathbb{E}\left[s^{\sum_{l=1}^{X_n}Y_l}\mid X_0=1\right]\\ &=\sum_{k=1}^\infty\mathbb{E}\left[\prod_{l=1}^{k}s^{Y_l}\mid X_n=k\right]\mathbb{P}(X_n=k\mid X_1 = 1)\\ &=\sum_{k=1}^\infty\mathbb{E}\left[s^{Y}\right]^k\mathbb{P}(X_n=k\mid X_1 = 1)\\ &=\sum_{k=1}^\infty G_1(s)^k\mathbb{P}(X_n=k\mid X_1 = 1)\\ &=G_n(G_1(s)) \end{aligned}\]于是乎对于 \(n\) 轮后的期望值我们有：
\[\begin{aligned} \mu_n &= \mathbb{E}\left[X_n\mid X_0 = 1\right]\\ &=\left.\frac{\partial G_n(s)}{\partial s}\right|_{s=1}\\ &=\left.\frac{\partial G_{n-1}(G_1(s))}{\partial G_1(s)}\cdot\frac{\partial G_1(s)}{\partial s}\right|_{s=1}\\ &=\left.\frac{\partial G_{n-1}(G_1(s))}{\partial G_1(s)}\right|_{s=1}\cdot\left.\lim_{s\to 1^-}\frac{\partial G_1(s)}{\partial s}\right|_{s=1}\\ &=\left.\frac{\partial G_{n-1}(s)}{\partial s}\right|_{s=1}\cdot\left.\frac{\partial G_1(s)}{\partial s}\right|_{s=1}\\ &=\mu_{n-1}\mu_1\\ &=\mu_1^n \end{aligned}\]对于一个 branching process \((X_n)_{n\in\mathbb{N}}\)：
- Supercritical: \(\mu_1 > 1\)，\(\mu_n\to\infty\)
- Critical: \(\mu_1 = 1\)，\(\mu_n\to\infty\)
- Subcritical: \(\mu_1 < 1\)，\(\mu_n\to 0\)
同样的，我们考虑方差
\[\begin{aligned} \sigma_n^2 &= \mathrm{Var}\left[X_n\mid X_0 = 1\right]\\ &= \left.\frac{1}{2}\frac{\partial^2G_{n}(s)}{\partial s^2}\right|_{s=1}\\ &= \left.\frac{1}{2}\frac{\partial}{\partial s}\left(\frac{\partial}{\partial s} G_{n-1}(s)\cdot\frac{\partial}{\partial s}G_1(s)\right)\right|_{s=1}\\ &= \left.\frac{\partial^2}{\partial s^2}G_{n-1}(s)\cdot\frac{\partial}{\partial s}G_1(s)\right|_{s=1} + \left.\frac{\partial}{\partial s}G_{n-1}(s)\cdot\frac{\partial^2}{\partial s^2}G_1(s)\right|_{s=1}\\ &= \sigma_{n-1}^2\mu_1 + \mu_{n-1}\sigma_1^2\\ &= \sigma_{n-1}^2\mu_1 + \mu_{1}^{n-1}\sigma_1^2\\ &=\begin{cases} n\sigma_1^2 & \mu = 1\\ \sigma_1^2\mu_1^{n-1}\frac{1-\mu_1^n}{1-\mu_1} & \mu\neq 1 \end{cases} \end{aligned}\]接下来我们要研究的是，\(X_n\) 能延续多久，也就是“time to extinction”。我们定义
\[T_0 = \inf\{n\ge 0: X_n = 0\}\]以及最终的 extinction probability
\[\alpha_k = \mathbb{P}(T_0 < \infty\mid X_0 = k)\]首先显然我们有：
\[\begin{aligned} \mathbb{P}(T_0 = n\mid X_0 = 1) &= \mathbb{P}(X_n = 0\mid X_0 = 1) - \mathbb{P}(X_{n-1} = 0\mid X_0 = 1) \\ &= G_n(0) - G_{n-1}(0)\\ &= G_1(G_{n-1}(0)) - G_{n-1}(0) \end{aligned}\]而我们来考虑 \(\alpha_k\)，首先显然这 \(k\) 个是独立的：
\[\alpha_k = \alpha_1^k\]而我们考虑了 \(\alpha_1\)：
\[\begin{aligned} \alpha_1 &= \lim_{n\to\infty}\mathbb{P}(T_0 < n\mid X_0 = 1)\\ &= \lim_{n\to\infty}\mathbb{P}(X_n=0\mid X_0 = 1)\\ &= \lim_{n\to\infty}G_n(0) \end{aligned}\]另一个神奇的性知识 \(\alpha_1\) 一定是方程 \(G_1(\alpha) = \alpha\) 的解：
\[\begin{aligned} \alpha_1 &= \sum_{k=0}^\infty\alpha_k\mathbb{P}(X_1 = k\mid X_0 = 1)\\ &= \sum_{k=0}^\infty\alpha_1^k\mathbb{P}(X_1 = k\mid X_0 = 1)\\ &= G_1(\alpha_1) \end{aligned}\]当然考虑到
\[\alpha = G_1(\alpha) = G_1(G_1(\alpha)) = \cdots\]所以
\[\forall k\in\mathbb{N}, \alpha = G_k(\alpha)\]我们可以进一步证明 \(\alpha_1\) 一定是方程 \(G_1(\alpha) = \alpha\) 最小的正解。
首先因为 \(\frac{\partial}{\partial s}G_1(s) > 0\)，这个函数肯定是递增的，所以说对于任意 \(k\)，\(G_k\) 肯定是递增的。
而考虑到上面已经论证过只要满足 \(\alpha = G_1(\alpha)\)，肯定对于任意 \(k\)，能满足 \(\alpha = G_k(\alpha)\)，于是乎：
\[\alpha_1 = \lim_{n\to\infty}G_n(0)\le \lim_{n\to\infty}G_n(\alpha) = \alpha\]也就是说对于任意符合条件的 \(\alpha\)，他肯定是大于等于 \(\alpha_1\) 的。于是乎 \(\alpha_1\) 一定是最小的正解。
Continuous-Time Markov Chains
首先是 Poisson Process。就是隔一段时间往上 \(+1\)。\(N_t\) 表示 \(t\) 时刻是多少，其中 \(N_0=0\)。我们定义 \(T_k\) 为第一次到达 \(k\) 的时间。
\[N_t = \sum_{k\ge 1} k\cdot\mathbb{1}_{t\in \left[T_{k-1}, T_k\right)} = \sum_{k\ge 1}\mathbb{1}_{t\in \left[T_{k-1}, \infty\right)}\]我们需要这种过程满足两个性质：
- Independence of increments: 对于任意的 \(0\le t_1 < t_2 < \cdots < t_n\)，\(N_{t_1}-N_{t_0}, N_{t_2}-N_{t_1}, \cdots, N_{t_n}-N_{t_{n-1}}\) 是相互独立的。
- Stationarity of increments: \(N_{t+s}-N_s\sim N_t\)。
那其实很显然这就是一个 poison distribution 嘛：
\[\mathbb{P}(N_t - N_s = k) = e^{-\lambda(t-s)}\frac{(\lambda(t-s))^k}{k!}\]其中
\[\lambda = \lim_{h\to 0^+} \frac{1}{h}\mathbb{P}(N_h = 1)\]然后还有就是 \(T_1\) 个 exp distribution 有关，\(T_n\) 跟 gamma distribution 有关。
\[T_n \sim \Gamma(n, \lambda): f_{T_n}(t) = \lambda^n e^{-\lambda t}\frac{(\lambda t)^{n-1}}{\Gamma(n)}\]然后我们把他一般化一下，得到 continuous-time Markov chain。其实核心也就是 “Memoryless”。
只不过这次的转移矩阵是一个关于时间的函数了：
\[P_{i, j}(t) = \mathbb{P}(Z_{s + t} = j\mid Z_s = i)\]而显然 \(P(0)=I\)。
很显然的性质是：
\[P(s + t) = P(s)P(t) = P(t)P(s)\]学习 Poisson process，我们来研究类似 \(\lambda\) 的一个跟“平均”有关的东西，我们考虑：
\[Q = \lim_{t\to 0^+}\frac{1}{t}\left(P(t) - P(0)\right) = \left.\frac{\partial}{\partial t}P(t)\right|_{t=0}\]而其实我们有（这个叫“backward Kolmogorov equation”）：
\[\begin{aligned} \frac{\partial}{\partial t}P(t) &= \lim_{h\to 0^+}\frac{1}{h}\left(P(t+h) - P(t)\right)\\ &= \lim_{h\to 0^+}\frac{1}{h}\left(P(h)P(t) - P(t)\right)\\ &= \lim_{h\to 0^+}\frac{1}{h}\left(P(h) - I\right)P(t)\\ &= QP(t) \end{aligned}\]当然同理我们还可以得到（这个叫“forward Kolmogorov equation”）：
\[\frac{\partial}{\partial t}P(t) = P(t)Q\]解这个微分方程我们有：
\[P(t) = e^{Qt} = \sum_{n=0}^\infty\frac{t^n}{n!}Q^n = I + \sum_{n=1}^\infty\frac{t^n}{n!}Q^n\]我们记 \(\lambda_{i,j} = Q_{i,j}\)，其实这个 \(\lambda_{i,j}\) 就和 Poisson process 那个一样了：
\[P(h) = I + hQ + \mathcal{O}(h^2)\]也就是：
\[\mathbb{P}(X_{x + h} = j\mid X_t = i) = P_{i, j}(h) = \begin{cases} \lambda_{i,j}h + \mathcal{O}(h^2) & i\neq j \\ 1 + \lambda_{i,i}h + \mathcal{O}(h^2) & i = j \end{cases}\]根据这个，我们对于 \(i\neq j\)，如果我们已经知道它下一步会到 \(j\)。我们定义停留在 \(i\) 的时间为 \(\tau_{i, j}\)，我们可以有：
\[\mathbb{P}(\tau_{i, j}>t\mid i\to j) = e^{-\lambda_{i, j}t}\]以及
\[\mathbb{E}[\tau_{i, j}\mid i\to j] = \int_{0}^\infty t\lambda_{i, j}e^{-\lambda_{i, j}t}\mathrm{d}t = \frac{1}{\lambda_{i, j}}\]当然另外还有一个性质是：
\[\sum_{j\in\mathbb{S}}\lambda_{i,j} = 0\]就是每个点要么出去要么留在原地嘛。
然后我们考虑 \(\tau_i\)，也就是停留在 \(i\) 的时间：
\[\tau_i = \min_{j\neq i}\tau_{i, j}\]我们可以计算概率：
\[\begin{aligned} \mathbb{P}(\tau_i > t) &= \mathbb{P}\left(\min_{j\neq i}\tau_{i, j}\right)\\ &= \prod_{j\neq i}\mathbb{P}(\tau_{i, j} > t)\\ &= \exp\left(-\sum_{j\neq i}\lambda_{i, j}t\right)\\ &= e^{\lambda_{i, i}t} \end{aligned}\]于是乎
\[\mathbb{E}[\tau_i] = \frac{1}{\sum_{j\neq i}\lambda_{i, j}} = -\frac{1}{\lambda_{i, i}}\]