计算方法04 图的随机游走
Published:
\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}
为了偷懒只讨论有限的情形
前置
离散概率分布可以表示为 ${\mathbb R}^n$ 上的向量 $x$，满足 $\sum_{i=1}^n x_i=1$ 且 $\forall i,x_i\in[0,1]$
对于用向量表示的概率分布，可以定义两个分布的“距离”：
\begin{aligned}
d_{TV}(p,q)=\frac{1}{2}\norm{p-q}1=\frac{1}{2}\sum{i=1}^n\abs{p_i-q_i}
\end{aligned}
这里 $d_{TV}(,)$ 表示 total variation distance。这样就可以定义一列分布的收敛性和极限了。系数的选择是任意的，但是这里可以思考为啥是 $\frac{1}{2}$
Markov Chain
对于一系列数量有限的状态，给出每个状态转移到下一个状态的概率 $Pr[s_i=y\mid s_{i-1}=x]$，这就构成了一个状态机。把状态看成点，转移概率看成边权，就得到了一个有向带权图，并且这个图满足一些特殊的性质。
考虑怎么算出现在状态 $i$ 的概率，这本质上是一个一阶递推，写出来就是
\begin{aligned}
p_{k+1}=Tp_k
\end{aligned}
这里 $p_k$ 表示走了恰好 $k$ 步后，处在每个状态上的概率分布
定义
周期
对于状态 $i$，其周期定义为 $gcd{t\mid {P^t}_{i,i}>0}$，记为 $period(i)$。称 Markov Chain 非周期当且仅当所有状态的周期都是 $1$
直观理解：从 $i$ 出发后走恰好 $t$ 步回到 $i$，所有这样的圈的长度的 gcd 即为周期。
这么定义的用处可以在后面看到。
不可约
有限图不可约当且仅当其为强连通图。此处强连通的定义为：任取 $x,y\in V(G)$，存在两条有向路径 $P_1,P_2$ 使得 $P_1=x\rightsquigarrow y,P_2=y\rightsquigarrow x$。不要求 $P_1,P_2$ 点不相交
性质
若 Markov Chain 不可约、非周期，则存在常数 $T$ 使得当 $t>T$ 时，${P^t}_{i,j}>0$ 对任意 $i,j$ 成立
直观理解：走了足够多步后不存在走不到的状态。
只需要证明存在常数 $L$，使得任意长度至少为 $U$ 的路径，都能在任意两点间找到。
不可约，则 $i,j$ 存在有向路径 $i\rightsquigarrow j$。
非周期，则存在最大的无法由两个圈线性组合出的正整数 $a\times b-a-b$ （NOIP2017，哈哈），记为 $mn(i)$，则此后的任意长度都可以由两个互质的圈线性组合出来。
只需要取 $T=n+\max{mn(i)}$，则此后可以在任意节点对之间游走。
稳态分布
考虑给定初始分布 $p_0$，则极限 $\lim\limits_{k\to\infty} P^k p_0$ 称为 Markov Chain 的极限分布。
若分布 $\pi$ 满足 $P\pi=\pi$，则称 $\pi$ 为平衡分布。可以证明极限分布若存在则必然为平衡分布。
设极限分布存在 $\lim\limits_{k\to\infty}P^k\pi_0=\pi’$，那么有
\begin{aligned}
P\pi’=P\lim\limits_{k\to\infty} P^k\pi_0=\lim\limits_{k\to\infty} P^{k+1}\pi_0=\pi’
\end{aligned}
这说明 $P\pi’=\pi’$ 是一个平衡分布。
Markov Chain 基本定理
若 Markov Chain 不可约、非周期，那么
存在稳态分布 $\pi$
对于任意的 $p_0$ 都有 $\lim\limits_{k\to\infty} P^k p_0=\pi$
$\pi$ 是唯一的
$\pi_i=\dfrac{1}{E[H_i]}$，其中 $H_i$ 为随机变量，表示从 $i$ 出发后第一次回到 $i$ 的行走步数。$E[H_i]$ 称为期望回归时间。
出现这个结论的原因在于，足够久之后任意点出发都将能走到任何点，因此两个不同的出发状态在足够久之后将“无法区分”
具体的证明看不懂，咕咕咕
Page Rank
Google 提出的给网页打分的算法。它假设
每个用户在页面 $x$ 浏览完后，将等概率点击一个 $x$ 中的超链接（即等概率走向一个邻居）
每个用户在页面 $x$ 浏览完后，有一定概率直接跳转到任意一个页面 $y$
可以发现 2 本质上就是新建超级点 $S$，然后每个点连向 $S$，再从 $S$ 连回所有点。
注意到 1 实际上就是在有向图上随机游走，转移矩阵恰好为度数导出的一个概率矩阵。2 保证了即使原图不是非周期、强连通时，用户这样的操作仍然可以使得随机游走存在一个稳态分布/极限分布（新图是强连通/非周期的，why？）。直觉也是符合的，每个人可能会突然停止浏览，然后从另一个完全不相关的页面重新开始冲浪。
并且这样的分数（概率分布）只与图的结构有关，与初始迭代向量没有关系。