根本概念

随机进程 $X (t)$ 是随机变量的调集。依据 $t$ 的取值和 $X$ 的取值特色，能够分为离散时刻、接连时刻、离散状况、接连状况
马尔科夫性（MP）： $Pr[X_t|X_{t-1}, X_{t-2}…] = Pr[X_t|X_{t-1}]$ ，另一种是 $Pr[X_{t+1}X_{t-1}|X_t]Pr[X_{t+1}|X_t]Pr[X_{t-1}|X_t]$ 。

注意，马尔可夫性并不蕴含曩昔和未来独立，而是说曩昔对未来的影响都现已蕴含在了现在状况的取值里了。所以其实这个假定并不强，假如对现在的调查满意细致，那么马尔可夫性是能够满意的。后边研究的都是离散时刻的，而且是有限状况或可数无量状况的Markov Chain

一步搬运矩阵： $P={P_{ij}=Pr[X_t=j|X_{t-1}=i]}$ ，由此带来的一系列表明不再赘述 $p_t=p_{t-1}P$ ， $n$ 步搬运 $P^n$
首达概率 $rijtr^t_{ij}$ ：从 $i$ 动身通过 $t$ 步，第一次抵达 $j$ 的概率。
首达期望长度： $hii=∑ttriith_{ii}=\sum_t t r^t_{ii}$

至此，咱们仅仅给出来MC的界说，没有剖析任何他的性质，但即使如此，就现已能够剖析某些算法问题了。

使用1: 2-SAT算法

问题回忆：有 $n$ 个布尔变量组成L长度的合取范式（与），每一个子句有两个变量组成析取范式（或），找到一组变量赋值使其满意。
算法：一个直观的算法是两阶段思路，先随机指使，然后随机选一个不满意的子句，随机改动其间一个变量的值。直到合法。
剖析：咱们感兴趣的问题是算法需求履行多少次，才有可能以较大的概率回来正确成果。这个问题的剖析就利用了MC。

状况表明：状况建模非常有技巧，界说 $X_t$ 表明在t步时，赋值正确变量的数量。那总共会有n+1个状况 $0, 1, \dots, n$
状况搬运剖析： $P_{01}=1$ ，关于一般状况 $Pi,i+1≥12,Pi,i−1≤12P_{i,i+1}\ge \frac{1}{2}, P_{i,i-1}\le \frac{1}{2}$ 。这是由于，每次都会挑选不合法的子句，那么这个子句里至少有一个变量的赋值是错的，所以选中并修正一个过错赋值的概率至少是 $12\frac{1}{2}$
MC的构建：由于上面的概率是个不等联系欠好剖析，可是假如概率取 $12\frac{1}{2}$ ，那剖析出来的必定比实际状况要差，相当于找到了下界，那也是很有价值的。所以树立MC，他的状况是从0～ $n$ ，概率搬运是 $P01=1,Pi,i+1=Pi,i−1=12P_{01}=1, P_{i,i+1}=P_{i,i-1}=\frac{1}{2}$ 。
步数剖析：算法成功意味着从某状况 $j$ 搬运到 $n$ ，中心走了多少步呢？利用期望剖析。 $h_0=1+h_1$ ， $h_i=1/2(1+h_{i-1}) + 1/2(1+h_{i+1})$ 。联立一堆方程，能够求出 $h_0=n^2$ 。也便是说最惨假定初始条件一个也没猜对， $n^2$ 步之后，也期望能求出来正确成果了。假如走 $2n^2$ 步，那不成功的概率就降低到 $1/2$ ，假如是 $2mn^2$ 步，那便是 $12m\frac{1}{2^m}$ （这儿不是 $12m\frac{1}{2m}$ 是由于没有看成一次测验搬运了 $2mn^2$ 步，而是测验了 $m$ 次算法，每次都走 $2n^2$ 步）

使用2: 3-SAT算法

显然，上面的思路假如直接搬迁似乎能处理3-SAT，剖析根本一致，仅有的变化是搬运概率变为 $P_{i,i+1}=1/3, P_{i,i-1}=2/3$ 。这是由于一个不满意的子句有3个变量，至少有一个不合法，所以随机改对一个的概率至少是1/3。和上面的期望核算相同，能够求出 $h_j=h_{j+1}+2^{j+2}-3$ ，那算法的期望时刻变成了 $(2n)\Theta(2^n)$ ，这和暴力枚举是相同的，并欠好。

从链的视点考虑，这个由于向0移动的概率更大，所以履行步数越多越欠好，所以把期望寄托在开局的随机挑选上。咱们把算法做出如下修正

算法：履行 $m$ 次：（随机选一个赋值组合，然后履行 $3 n$ 次修正）

先考虑初始随机指使，设随机挑选的状况有 $j$ 个和正确答案不相同，那通过 $j + 2 k$ 步能够抵达状况 $n$ 的概率为 $C_{j+2k}^k(2/3)^k(1/3)^{j+k}$ 。相当于向 $n$ 行进比向0多了 $j$ 次，就能够确保最终抵达 $n$ 。从 $j$ 移动到 $n$ 的概率下界 $qj=∑kCj+2kk(2/3)k(1/3)j+k≥C3jj(2/3)j(1/3)2jq_j = \sum_k C_{j+2k}^k(2/3)^k(1/3)^{j+k}\ge C_{3j}^j(2/3)^j(1/3)^{2j}$ （最终一步 $k$ 能取 $j$ ，这是由于算法修正的次数为 $3 n$ （算法的设计），所以 $j + 2 k$ 需求不大于 $3 n$ ，而 $j$ 不会大于 $n$ （ $j$ 的取值上限是变量数），所以能够取到)。
利用sterlin公式， $2m(me)m≤m!≤22m(me)m\sqrt{2\pi m}(\frac{m}{e})^m \le m! \le 2\sqrt{2\pi m}(\frac{m}{e})^m$ ，能够推出 $qj≥cj1/2jq_j\ge \frac{c}{\sqrt{j}}1/2^j$ 。由于初始化是随机指使，所以 $j$ 的取值是一个满意 $1/2^n$ 的均匀散布，所以最终的概率 $q≥∑jPr[j]qj≥c/n(3/4)nq\ge \sum_j Pr[j]q_j \ge c/\sqrt{n}(3/4)^n$ 。那期望次数便是 $1/ q$ ，这是咱们设置 $m$ 的参阅。能够看到，尽管还是指数，可是base从2降低到 $4/3$ 。

上面的两个使用仅仅简单利用了Markov链的建模，以及期望核算进程中的递归作用，下面更进一步发掘其间的性质，对剖析问题有更大帮助。

状况剖析

相通：两个状况彼此可达，即存在某n，使得 $Pijn>0P^n_{ij}>0$ 。
假如一切状况相通，则链是不行约的。
常返： $∑tri,it=1\sum_t r_{i,i}^t = 1$ 。
0常返： $hii=E[t]=∑ttri,it=∞h_{ii}=E[t]=\sum_t t r_{i,i}^t=\infty$
正常返： $h_{ii}$ 有限
性质：有限状况的MC，至少有一个常返且一切常返都是正常返。相通的状况要么都常返，要么都不常返。

能够这么了解，假定在链上不断搬运，那拜访的总次数是可数无量的，但状况是有限的，所以至少有一个状况被拜访无限次，那他便是常返的。此外，他被拜访的次数是可数无量，而两次拜访的间隔塞不下一个可数无量了，所以期望有限。

遍历：非周期的常返状况。

使用：赌徒问题

两个赌徒A和B，抛公平硬币，正面向上A赢1元，反面向上B赢一元，A和B的赌注分别是 $l_A, l_B$ ,谁先把对方的钱赢完谁就取胜了。剖析两者胜率。

MC构建：很明显把A赢的钱设为状况 $X$ ，那么初始状况为0，两个完毕状况分别是 $l_A, l_B$ 。状况搬运概率都是1/2。就像拔河相同，一会向左一会向右，一旦越过了 $l_A$ 或 $l_B$ ，就完毕了。
剖析：MC具有非周期、有限的性质。（注意并非不行约，由于停止状况只进不出）。常返状况存在且是正常返。
简单验证，常返状况便是停止状况，由于中心的状况相通所以常返性相同，考虑停止状况相邻的一个状况，这个状况显然不行能常返，由于他一旦进入周围停止状况就回不来了，因此中心的状况回来的概率不会超过1/2，不常返，又由于整个链至少有一个常返，所以停止状况是常返的。
设 $P_i^t$ 是t步之后在i的概率，那么A的赢钱期望 $E[Wt]=∑iiPitE[W^t]=\sum_i i P_i^t$ ，由于每一步竞赛公平，期望为0，那t步和也为0，所以 $E[Wt]=∑iiPit=0E[W^t]=\sum_i i P_i^t=0$ ，两侧取极限， $Pit→0(t→∞)P_i^t\rightarrow 0(t\rightarrow \infty)$ ，而 $P−lAt=(1−p),PlBt=pP^t_{-l_A}=(1-p), P^t_{l_B}=p$ 。带入得, $p=lAlA+lBp=\frac{l_A}{l_A+l_B}$

补充：完毕的期望次数为 $l_Al_B$

稳态剖析

假如一个链不行约，那么每一个状况的常返性相同，状况搬运看似永不断歇（不像前面赌徒的比方有停止状况）。但其实这儿面存在一个动态平衡，即每个状况的拜访次数的散布是稳定的。

定理：有限、不行约且遍历（非周期常返）的MC，有仅有的平稳散布 $=P\pi=\pi P$ ，而且 $i=lim⁡tPijt=lim⁡Piit=1hii\pi_i=\lim_t P^t_{ij}=\lim P^t_{ii}=\frac{1}{h_{ii}}$
推广：任何有限MC都有平稳散布，但周期状况不是求极限可解的。
性质：平稳散布中，脱离一个状况的概率=进入的概率（这说明了平衡）。这很简单想到用割来剖析，由于平衡之后，每条边的通量是稳定的，正反向求和为0。

无向图的随机游动模型

模型界说：一个连通无向图 $G = (V, E)$ ，随机选一个点开端，每次等概率搬运到它相邻的点。
平稳散布：最终会收敛，而且 $i=di2∣E∣\pi_i = \frac{d_i}{2|E|}$

证明：这个散布满意进入概率等于脱离概率

通勤时刻性质：假如 $(u,v)∈E(u,v)\in E$ ，则 $h_{uv}+h_{vu} =2|E|$
掩盖时刻性质：从一个点动身，拜访完一切点的期望时刻上界为 $2∣ E ∣ (∣ V ∣ - 1)$
掩盖时刻的上下界： $H(n-1)\min h_{uv}, H(n-1)\max h_{uv}$

马尔可夫链的耦合

定量描绘抵达平稳散布的进程

耦合技术首要用来剖析一个MC多快能够抵达平稳散布。那首先需求处理的问题是，怎么定量描绘抵达了平稳散布？这儿使用变异间隔的概念。

界说：变异间隔

可数状况空间S中的两个散布 $D_1, D_2$ 的变异间隔为 $∣∣D1−D2∣∣=12∑x∈S∣D1(x)−D2(x)∣||D_1-D_2||=\frac{1}{2}\sum_{x\in S}|D_1(x)-D_2(x)|$ 。

很简单了解，便是把每个方位散布的间隔求和了。而且乘1/2确保这个值在0～1之间。

关于上面的界说，能够发掘出一个有用的性质 $∀A⊆S,∣∣D1−D2∣∣=max⁡A⊆S∣D1(A)−D2(A)∣\forall A\subseteq S, ||D_1-D_2||=\max_{A\subseteq S}|D_1(A)-D_2(A)|$ 。这儿散布里套调集表明把调集的每一个元素的概率都加起来。

证明：界说 $S^+$ 是 $D1(x)≥D2(x)D_1(x)\ge D_2(x)$ 的元素调集， $S^-$ 是 $D_1(x)<D_2(x)$ 的元素调集。
有 $max⁡A⊆S(D1(A)−D2(A))=D1(S+)−D2(S+)\max_{A\subseteq S}(D_1(A)-D_2(A))=D_1(S^+)-D_2(S^+)$ （便是说求差的最大值便是把一切D1>D2的元素都算进来，这时分差必定最大）
类似有 $max⁡A⊆S(D2(A)−D1(A))=D2(S−)−D1(S−)\max_{A\subseteq S}(D_2(A)-D_1(A))=D_2(S^-)-D_1(S^-)$
又通过 $D_1(S)=D_2(S)=1=D_1(S^+)+D_1(S^-)=D_2(S^+)+D_2(S^-)$ ，通过移项，发现刚好能够凑出前面公式的rhs，因此
$D_1(S^+)-D_2(S^-)=D_2(S^+)-D_1(S^-)$
$max⁡A⊆S(D1(A)−D2(A))=D1(S+)−D2(S−)=D2(S+)−D1(S−)\max_{A\subseteq S}(D_1(A)-D_2(A))=D_1(S^+)-D_2(S^-)=D_2(S^+)-D_1(S^-)$ ，加上绝对值
$max⁡A⊆S∣D1(A)−D2(A)∣=∣D1(S+)−D2(S−)∣=∣D2(S+)−D1(S−)∣\max_{A\subseteq S}|D_1(A)-D_2(A)|=|D_1(S^+)-D_2(S^-)|=|D_2(S^+)-D_1(S^-)|$
最终由于 $D_1(S^+)-D_2(S^-)|+|D_2(S^+)-D_1(S^-)|$ 的含义恰好是一切状况在两个散布的概率差的和所以等于 $∑x∣D1(x)−D2(x)∣=2∣∣D1−D2∣∣\sum_x |D_1(x)-D_2(x)|=2||D_1-D_2||$ 。
上面两个公式导出定论。

把变异间隔的概念套用到平稳散布上，咱们界说 $x(t)=∣∣pxt−∣∣\Delta_x(t)=||p^t_x-\bar{\pi}||$ 。即以x为初始状况动身通过t轮，得到的散布和平稳散布之间的变异间隔。而且令 $(t)=max⁡xx(t)\Delta(t)=\max_x \Delta_x(t)$

有了上面的界说和性质（能够作为核算方法），咱们有了可操作性的抵达平稳散布的断定。接下来直指最核心的问题，需求通过多久抵达平稳散布。为此，界说混合时刻的概念： $x()=min⁡{t:x(t)≤},()=max⁡ss()\tau_x(\epsilon)=\min\{t: \Delta_x(t)\le \epsilon\}, \tau(\epsilon)=\max_s \tau_s(\epsilon)$ 很直观不再赘述。

结构耦合剖析混合时刻

耦合的界说

设 $M_t$ 表明一个状况空间为 $S$ 的MC，它的耦合是一个MC: $Z_t=(X_t, Y_t)$ 满意：

Pr[X_{t+1}=x’|Z_t=(x,y)] = \Pr[X_{t+1}=x’|M_t=x]

Pr[Y_{t+1}=y’|Z_t=(x,y)] = \Pr[Y_{t+1}=y’|M_t=y]

能够这么了解：显然一个MC的两次独立采样是满意这个条件的。但通常没有用。咱们期望让两个MC的实例在搬运进程中发生一些相关，但这个相关不会改动他们单独运行的搬运概率。后边给个比方去领会。

耦合引理

现在的问题是，这个耦合是怎么帮助咱们剖析混合时刻的？答案是耦合引理。它的内容如下

设 $Z_t$ 是 $M_t$ 的一个耦合，假如存在 $T$ 使得对每个 $x,y∈Sx,y\in S$ ，有 $Pr⁡[Xt≠Yt∣X0=x,Y0=y]≤\Pr[X_t\ne Y_t|X_0=x, Y_0=y]\le \epsilon$ ，则 $()≤T\tau(\epsilon) \le T$ .

也便是说，假如阅历一段时刻，两个链不论从哪个状况动身最终状况都几乎是相同的，那混合时刻不会超过这个时刻。这个思路很像数学剖析中的柯西收敛原则，在判断极限的时分不依赖外部给定的极限值，而是通过序列内部接近的间隔来决定。而在这儿，咱们判断抵达平稳散布也不依赖于外部给定的平稳散布，而是通过两个耦合链内部的趋同来确认。

证明：结构耦合，令 $Y_0$ 是从平稳散布抽取的初始状况， $X_0$ 是任取的。对恣意 $A⊆SA\subseteq S$
$Pr⁡[XT∈A]≥Pr⁡[XT=YT∩YT∈A]=1−Pr⁡[XT≠YT∪YT∉A]≥1−Pr⁡[XT≠YT]−Pr⁡[YT∉A]=Pr⁡[YT∈A]−Pr⁡[XT≠YT]≥(A)−\Pr[X_T\in A]\ge \Pr[X_T=Y_T\cap Y_T\in A] = 1 – \Pr[X_T\ne Y_T\cup Y_T\notin A] \ge 1 – \Pr[X_T\ne Y_T] – \Pr[Y_T\notin A] = \Pr[Y_T\in A]-\Pr[X_T\ne Y_T]\ge \pi(A)-\epsilon$
最终一行， $\epsilon$ 是依照界说，而 $\pi$ 是由于 $Y_0$ 是平稳散布选取的。
对 $S - A$ 类似可证 $Pr⁡[XT∈A]≤(A)+\Pr[X_T\in A]\le \pi(A)+\epsilon$ 。
所以 $max⁡∣pxT(A)−(A)∣≤\max|p_x^T(A)-\pi(A)|\le \epsilon$ ，得证。

这儿似乎有点问题，Y直接是平稳散布取的，那是不是要求咱们在利用耦合引理时结构耦合有必要有一个MC是平稳散布呢？不是的，由于咱们能够取一个充分大的T，使至少一个链抵达平稳散布。

事例：剖析洗牌进程

洗牌的目标：均匀散布从全摆放中挑选一种

洗牌的操作：随机选一张牌，放到最上面。

问题：通过多少次洗牌，能够让洗牌的成果是全摆放的均匀散布？

结构MC：状况是一个牌的摆放，相邻界说为能够通过一次洗牌抵达的状况。状况搬运界说为一次洗牌操作之后抵达的状况。由于洗牌操作牌是均匀取的，所以抵达某个状况的概率是持平的，为 $1/ n$ 。

依据前一章的剖析，平稳散布是均匀散布，所以在这个MC上搬运满意多的次数能够抵达均匀散布。这也证明了咱们这种洗牌操作的可行性。接下来便是最精彩的环节，利用耦合剖析通过多少次操作能够完成均匀采样？

结构耦合：两个链 $X$ 和 $Y$ ，初始状况恣意。 $X$ 链是随机搬运的， $Y$ 链每次搬运挑选的牌和 $X$ 链相同。简单证明这是一个耦合。由于每张牌在 $X$ 和在 $Y$ 中被选中的概率都是 $1/ n$ ，所以基于耦合 $Z$ 来搬运 $Y$ （ $Pr[Y_{t+1}|Z_t]$ ）和 $Y$ 自己去搬运( $Pr[Y_{t+1}|Y_t]$ )，搬运到每个状况的概率是相同的。这儿也许能够更好的了解前面耦合的界说。相当于 $Y$ 把自己的随机性让渡给了 $X$ ，可是这个让渡的前提是搬运概率保持不变。

剖析 $Pr⁡[XT≠YT]\Pr[X_T\ne Y_T]$ 的概率。有了耦合，为了利用耦合引理，需求剖析通过多长时刻两个状况不等的概率就小于 $\epsilon$ 了。这需求结合洗牌进程的特色。咱们发现一旦一张牌在 $X$ 被选中放在最初，那么耦合的 $Y$ 也选中了这张牌放在最初。从这之后这张牌的方位在两个链便是相同的了。那么假如每张牌都被选中一次，两个链的状况就彻底相同了。由于每次选的牌都是等概率的，所以这便是一个赠券搜集模型。预期 $H(n)=nln⁡n+cnH(n)=n\ln n + cn$ 步之后，一张牌从未被选中的概率为 $(1−1/n)H(n)≤e−cn(1-1/n)^{H(n)} \le \frac{e^{-c}}{n}$ ，为了凑 $\epsilon$ ，取 $c=−ln⁡c=-\ln \epsilon$ 。这样， $T=nln⁡n−ln⁡nT=n\ln n -\ln \epsilon n$ 步，两个状况不持平的概率就低于 $\epsilon$ ，依照耦合引理，能够确认混合时刻比这个小。

其他可能用到的东西

同一条链的两个实例的散布变异间隔只减不增: $x(T)=∣∣pxT−pyT∣∣≥x(T+1)\delta_x(T)=||p_x^T-p_y^T||\ge \delta_x(T+1)$
几许收敛: 设 $P$ 是有限、不行约、非周期的MC搬运矩阵， $m_j$ 是第j列的最小元素， $m=∑jmim=\sum_j m_i$ ，那么 $∣∣pxt−∣∣≤(1−m)t||p_x^t-\pi||\le (1-m)^t$ 。
假如某个 $c < 1/2$ ，有 $(c)≤T\tau(c)\le T$ ，那么 $()≤⌈ln⁡/ln⁡(2c)T⌉\tau(\epsilon) \le \lceil \ln \epsilon/\ln (2c) T \rceil$

习题

7.20 不公平赌徒破产问题

假定1/3的概率赢1元，2/3概率输1元，开端有 $i$ ，游戏完毕要么全亏完，要么手上有 $n$ 元。设 $W_t$ 是t轮后的总钱数。

(a) 证明 $E[2^{W_{t+1}}]=E[2^{W_t}]$

引进条件期望， $E[2Wt+1∣Wt]=132Wt+1+232Wt−1=2WtE[2^{W_{t+1}}|W_{t}]=\frac{1}{3} 2^{W_t + 1} + \frac{2}{3} 2^{W_t – 1}=2^{W_t}$
两头取期望， $E[E[2^{W_{t+1}}|W_{t}]]=E[2^{W_{t+1}}]=E[2^{W_t}]$

(b) 利用(a)确认从i开端以0完毕和以n完毕的概率。

设 $q_i$ 表明以0完毕的概率，那么 $1-q_i$ 为n完毕的概率
由于 $E[2^{W_{t+1}}]=E[2^{W_t}]$ ，那么递推可得 $E[2Wt]=E[2W1]=132i+1+232i−1=2iE[2^{W_t}]=E[2^{W_1}]=\frac{1}{3} 2^{i+1} + \frac{2}{3} 2^{i-1}=2^i$
两侧取极限， $lim⁡t→∞E[2Wt]=qi20+(1−qi)2n=2i\lim_{t\rightarrow \infty} E[2^{W_t}] = q_i 2^0 + (1-q_i) 2^n = 2^i$
所以 $qi=2n−2i2n−1q_i = \frac{2^n – 2^i}{2^n – 1}$

从(a)的剖析能够看到，选一个合适的底数，推导进程是彻底相同的。底数需求凑出那个方式，所以取 $\frac{1+\sqrt{1+4p(1-p)}}{2p}$

7.23 网络传达模型

$n$ 台主机彼此连通，最开端有一台主机产生了音讯，再之后的时刻里，每台主机随机选取一台发送音讯。剖析这个传达进程

(a) 怎么建模成Markov Chain

$X_k$ 表明 $k$ 轮后，收到音讯的主机数

(b) 在已知 $k - 1$ 轮有 $i$ 台主机有音讯的状况下，确认 $k$ 轮后有 $j$ 台收到音讯的概率。

递推，令P(i,j, c)表明在某一轮，前c个机器挑选后，从i台主机有音讯变成j台有音讯的概率。那么能够得到如下递推式

$c)=P_{k-1}(i, j – 1, c – 1)\frac{n – 1 – (j – 1)}{n – 1} + P_{k-1}(i, j, c – 1)\frac{j – 1}{n – 1}$

便是说，假如前c-1台选完后，现已有j-1台有音讯了，那第c台有必要再选一个没有音讯的。假如第c台选的时分现已有j台有音讯了，那有必要选之前有音讯的，才干确保总共还是j台。

7.26 狼吃羊的问题

假定一个圆盘，等间隔标示了0～n-1个点，狼在0处，每次有1/2的概率向左或向右移动一个点，并在第一次抵达一个点的时分把羊吃掉。问：哪个方位的羊最终被吃掉的概率最大。

直觉上应该是间隔狼最远的方位，也便是0对面。但实际上每个点都是相同的。之所以反直觉，是由于接近狼的方位并不是最终一个被吃掉的概率降低了，而是在前几回被吃掉的概率变大了，这是两回事。比方和狼紧挨的方位，第一次被吃掉的概率高达1/2，但这不阻碍他最终被吃掉的概率和其他人相同。由于你总是要被吃掉。。。

剖析一下被吃掉的概率。首先考虑和狼紧挨的方位1，假如把环从1-2之间劈开（之所以能够劈开，咱们只关怀第一次抵达1的状况，所以抵达1之后就完毕了，不需求考虑从1到2这条路，此外也不需求关怀从2抵达1的状况，由于假如从2到1，那其他羊都被吃完了，这样1确实是最终一个，也完毕了），那这个问题就变成了赌徒破产问题，1最终被吃掉的概率和到2方位取胜概率相同，为 $1n−2+1=1n−1\frac{1}{n-2+1}=\frac{1}{n-1}$ ，由对称性，n-1方位也是这个概率。
关于其他方位， $i$ 最终被吃掉，有两种状况：
1 A: 从0走到i-1（不通过i+1），B: 再从i-1走到i+1（不穿过i）
2 C: 从0走到i+1（不通过i-1），D: 再从i+1走到i-1（不穿过i）
每种状况都是两个赌徒破产问题， $Pr[C]Pr[D]=\frac{i-1}{n-1}\frac{1}{n-1} + \frac{n-i}{n-1}\frac{1}{n-1}$

4 马尔可夫

根本概念

使用1: 2-SAT算法

使用2: 3-SAT算法

状况剖析

使用：赌徒问题

稳态剖析

无向图的随机游动模型

马尔可夫链的耦合

定量描绘抵达平稳散布的进程

结构耦合剖析混合时刻

耦合的界说

耦合引理

事例：剖析洗牌进程

其他可能用到的东西

习题

7.20 不公平赌徒破产问题

7.23 网络传达模型

7.26 狼吃羊的问题

作者信息

4 马尔可夫

根本概念

使用1: 2-SAT算法

使用2: 3-SAT算法

状况剖析

使用：赌徒问题

稳态剖析

无向图的随机游动模型

马尔可夫链的耦合

定量描绘抵达平稳散布的进程

结构耦合剖析混合时刻

耦合的界说

耦合引理

事例：剖析洗牌进程

其他可能用到的东西

习题

7.20 不公平赌徒破产问题

7.23 网络传达模型

7.26 狼吃羊的问题

相关文章

GPT-4 性能炸天：10 秒做出一个网站，考试成绩击败 90% 人类

技术管理的心态修炼

Go基础：接口

Android 内存泄漏分析思路和案例剖析

作者信息