页面排序 PageRank

模型

网页间的链接构成一副图

如果有高名次的页面指向一个页面，则该页面有较高的名次，即

π(i) = \sum_{j ∈ X} π(j) P(j, i), i ∈ X

注意其中 $P(j, i)$ 为指向 $i$ 的链接，单位化后的结果

写成矩阵：

π = π P

还有一重单位化的约束：

\sum_{i ∈ X} π(i) = 1

马尔科夫链

可以用公式定义马尔科夫链：

P[X(n+1) = j | X(n) = i, X(m), m < n] = P(i, j), ∀ i, j ∈ X, n ≥ 0

其中 $X(n)$ 表示时间 $n$ 时的状态， $X(0)$ 也称初始状态

该公式揭示了马尔科夫链的几个性质：

描述状态转移
不关心到达 $i$ 的路径

矩阵形式

π_n = π_0 P^n

分析

定义：

如果可以从任何状态到任何其他状态，则该马尔科夫链是不可约的 irreducible
如果马尔科夫链是不可约的，且定义 $d(i) = \gcd \{n ≥ 1 | P^n(i, i) > 0\}$ ， $d(i)$ 对于所有的 $i$ 有相同的 $d$ 。若 $d=1$ ，则是非周期性的 aperiodic；否则是周期性 $d$

有限马尔科夫链的大定理：

如果马尔科夫链是有限且不可约的，则有独特的不变分布 $π$ 且 $π(i)$ 是长期来看 $X(n) = i$ 的“时间比例”
如果也是非周期的，则 $X_n$ 的分布 $π_n$ 收敛于 $π$

对于长期来看 $X(n) = i$ 的“时间比例”有如下数学定义

\lim_{N → ∞} \frac{1}{N} \sum_{n=0}^{N-1} 1\{X(n) = i\}

注： $1\{X(n) = i\}$ 表示当 $X(n) = i$ 时取 1，否则为 0

为什么这个数会收敛，原因和抛硬币很多次，正面的比例为 50% 一样，是大数定律

强大数法则 Strong Law of Large Numbers

$\{X(n), n ≥ 1\}$ 是独立的随机变量，平均值为 $μ$ ，则当 $n → ∞$ 时

\frac{X(1) + ⋯ + X(n)}{n} → μ

概率为 1

命中时间

到达页面 $E$ 的时间为击中时间 hitting time，表示为 $T_E$

*定义：*平均击中时间

β(i) = E[T_E | X_0 = i]

可以得到一些方程，如 $β(A) = 1 + \frac{1}{2}β(B) + \frac{1}{2} β(D)$ 等，这些方程组称为第一步方程 first step equations

*定义：*在命中一个状态之前命中另一个状态的概率，如从 $i$ 开始访问 $C$ 再访问 $E$

α(i) = P[T_C < T_E | X_0 = i]

同样的，也有一些方程，如 $α(A) = \frac{1}{2} α(B) + \frac{1}{2} α(D)$

给出一般化的数学定义和关系：

一、平均命中时间：

β(i) = E[T_A | X_0 = i], i ∈ X

β(i) = \begin{cases} 1 + \sum_j P(i, j) β(j), i ∉ A \\ 0, i ∈ A \end{cases}

二、先访问 A 再访问 B 的概率：

α(i) = P[T_A < T_B | X_0 = i], i ∈ X

α(i) = \begin{cases} \sum_j P(i, j) α(j), i ∉ A ∪ B \\ 1, i ∈ A \\ 0, i ∈ B \end{cases}

三、每次访问 i 时，收集一个值 $h(i)$ ，直到进入 $A$

Y = \sum_{n=0}^{T_A} h(X(n))

γ(i) = E[Y | X_0 = i], i ∈ X

γ(i) = \begin{cases} h(i) + \sum_j P(i, j) γ(j), i ∉ A \\ h(i), i ∈ A \end{cases}

四、 $β$ 为折扣因子：

Z = \sum_{n=0}^{T_A} β^n h(X(n))

δ(i) = E[Z | X_0 = i]

δ(i) = \begin{cases} h(i) + β\sum_j P(i, j) δ(j), i ∉ A \\ h(i), i ∈ A \end{cases}

马尔科夫链还有很多变形

页面排序 B

样本空间

以抛硬币为例，尝试定义样本空间。 $ω = (ω_0, ω_1, ⋯), ω_n ∈ \{0, 1\}$ 其中 $ω$ 是抛出的由无数个 0 和 1 组成的序列，定义 $X_n(ω) = ω_n$ ，即得到 $ω ∈ ω, X_n(ω) ∈ R$ 的函数了，这个函数将样本空间中的所有样本与数联系

可以定义样本空间中的概率了：

P(\{ω | ω_0 = a, ω_1 = b, ⋯, ω_n = z\}) = P(X_0 = 1, ⋯, X_n = z) = \frac{1}{2^{n+1}}

对于马尔科夫链，选择样本空间为无限可能的访问序列，叫规范样本空间 canonical sample space

P(X_0 = i_0, X_1 = i_1, ⋯, X_n = i_n) = π_0(i_0) P(i_0, i_1) ⋯ P(i_{n-1}, i_n)

可以发现这个定义和一开始的定义是等价的

抛硬币的大数定律

有两条路径去靠近这个接近 50% 的思想：

概率的收敛：令

Y_n = \frac{X_0 + ⋯ + X_{n-1}}{n}

有切比雪夫不等式：

P(|Y_n - E(Y_n)| ≥ ϵ) ≤ \frac{\operatorname{var}(Y_n)}{ϵ^2}

因为

\operatorname{var}(Y_n) = \frac{\operatorname{var}(X_0)}{n}

\operatorname{var}(X_0) = 0.25

故

P(|Y_n - 0.5| ≥ ϵ) ≤ \frac{1}{4n ϵ^2}

当 $n → ∞, ∀ ϵ > 0, P(|Y_n - 0.5| ≥ ϵ) → 0$

这就是弱大数定律，其含义为不收敛为 50% 的概率为 0

**几乎必然收敛：**当 $n → ∞$ 时，

Y_n(ω) → 0.5

马尔科夫链中的大数定律

$T_i$ 为走一个圈回到某个点的时间，易得该随机变量是独立的，且有一个最大值和最小值，小于无穷，故有

\frac{T_1 + ⋯ + T_k}{k} → E(T_1), k → ∞, \text{概率为 1}

易得

\lim_{k → ∞} \frac{k}{T_1 + ⋯ + T_k} = \frac{1}{E(T_1)}, \text{概率为 1}

大定理的证明

定义： $m_j$ 为回到 $j$ 的期望时间，即

m_j = E[T_j | X(0) = j], T_j = \min \{n > 0 | X(n) = j\}

有这样一个关系：

\sum_j \frac{1}{m_j} P(j, i) = \frac{1}{m_i}

所以得出分布 $π_i = \frac{1}{m_i}$

多路技术 Multiplexing

共享链接

每个用户独立使用的概率为 p，求超过 m 个活跃用户的概率最多为 5%

高斯随机变量和中心极限定理

平均值为 0，方差为 1 的高斯随机变量 $W$ 的 pdf 为

f_W(x) = \frac{1}{\sqrt{2π}} \exp \{- \frac{x^2}{2}\}

平均值为 $μ$ ，方差为 $σ^2$ 的高斯随机变量 $X$ ：

X = μ + σ W

f_X(x) = \frac{1}{\sqrt{2π σ^2}} \exp \{-\frac{(x- μ)^2}{2σ^2}\}

中心极限定理：

\frac{X(1) + ⋯ + X(n) - n μ}{σ \sqrt{n}} \implies N(0, 1)

特别的，若 $\{Y(n), n ≥ 1\}$ 是随机变量，则 $Y(n) \implies N(0, 1)$ 即

P(Y(n) ≤ x) → P(W ≤ x)

*定义：*分布的收敛，写作 $X(n) \implies X$ ，如果

P(X(n) ≤ X) → P(X ≤ x), \text{其中} P(X = x) = 0

伯努利分布与高斯分布的关系： $B(N, p) = N(Np, Np(1-p))$

置信区间：

90%： $[μ_n - 1.65 \frac{σ_n}{\sqrt{n}}, μ_n + 1.65 \frac{σ_n}{\sqrt{n}}]$
95%： $[μ_n - 2 \frac{σ_n}{\sqrt{n}}, μ_n + 2 \frac{σ_n}{\sqrt{n}}]$

其中 $σ_n^2 = \frac{\sum_{m=1}^n (X(m) - μ_n)^2}{n-1}$ ，注意 $n-1$ 是为了无偏

缓冲

$λ$ 为每个时间到达的概率， $μ$ 为完成发送的概率，对于这张图，有

$p_2 = λ(1 - μ)$
$p_0 = μ(1 - λ)$
$p_1 = 1 - p_0 - p_2$

平衡方程为：

π(n) = p_2 π(n-1) + p_1 π(n) + p_0 π(n+1)

可得解为：

π(i) = π(0) ρ^i

其中 $ρ = \frac{p_2}{p_0}$

由概率相加为 1 可得

π(0) = \frac{1-p}{1-p^{N+1}}

故得到期望：

E(X) = \frac{λ(1 - μ)}{μ - λ}

平均延时：

W = \sum_{k ≥ 0} \frac{k+1}{μ} ϕ(k)

$ϕ(k)$ 为当一个包裹到达时已经有 k 个包裹的概率

从而得到

W = \frac{1 - μ}{λ - μ}

利特尔法则 Little's Law：

L = λ W

其中 L 是系统中的平均客户， $λ$ 是客户的平均到达速率，W 是客户的平均时间

多重访问

N 个设备，每个设备的传送概率 p，根据伯努利，有

P(X(n) = 1) = Np(1-p)^{N-1}

最大的成功速率是当 $p = 1 / N$ 时， $λ^* = \frac{1}{e} = 0.36$

故可以达到 36% 的传递速率，但是需要知道多少设备活跃着

多路技术 B

特征函数

随机变量 X 的特征函数 characteristic function 是

ϕ_X(u) = E(e^{iuX})

注意到

ϕ_X(u) = \int_{-∞}^{∞} e^{iux} f_X(x) \mathrm{d}x

即 $ϕ_X(u)$ 是 $f_X(x)$ 的傅里叶变换

若 $X = N(0, 1)$ ，则

ϕ_X(u) = e^{-\frac{u^2}{2}}

中心极限定理的证明

ϕ_{Y(n)}(u) = [1 - u^2 / (2n) + o(1 / n)^n] → e^{- u^2 / 2}

N(0, 1) 的矩

由 $ϕ_X(u)$ 的两种表示形式：

ϕ_X(u) = E(e^{iuX}) = \sum_{n=1}^{∞} \frac{1}{n!}(iu)^n E(X^n)

ϕ_X(u) = e^{-u^2/2} = \sum_{m=0}^{∞} \frac{1}{m!} (- \frac{u^2}{2})^m

所以得到

E(X^{2m}) = \frac{(2m)!}{m! 2^m}

注意到 $E(X^{2m+1}) = 0$

两个独立 N(0, 1) 的平方的和

f_{X, Y}(x, y) \mathrm{d}x\mathrm{d}y = \frac{\mathrm{d}\theta}{2 π} e^{- r^2/2} r \mathrm{d}r = f_{\theta}(\theta) \mathrm{d}\theta ⋅ f_R(r)\mathrm{d}r

可以发现 $\theta$ 和 r 无关

特征函数的两个应用

泊松是二项分布的极限：泊松的平均值为 $λ$ 的随机变量可以看做 $B(n, λ/n)$

对于二项分布，有

E(\exp(iuX_n)) = [1 + \frac{λ}{n}(e^{iu} - 1)]^n

对于泊松，有

E(\exp(iuX)) = \exp(λ(e^{iu} - 1))

取前者的极限，可得结果

指数是几何的极限：

因为有

\frac{1}{n} X_n → X

分别计算两边：

E(e^{iuX}) = \frac{λ}{λ - iu}

E(\exp(iu \frac{1}{n} X_n)) = \frac{λ}{λ - iu + o(1/n)}

误差函数

在计算置信区间时，使用到了 $Q(x) = P(X > x)$

该函数的上界和下界为：

\frac{x}{1+x^2} \frac{1}{\sqrt{2 π}} \exp(-\frac{x^2}{2}) ≤ Q(x) ≤ \frac{1}{x\sqrt{2π}} \exp(-\frac{x^2}{2})

可适应多重访问

调整时间 n 时的设备传递概率 $p(n)$ ：

p(n+1) = \begin{cases} p(n), X(n) = 1 \\ ap(n), X(n) > 1 \\ \min(bp(n), 1), X(n) = 0 \end{cases}

其中 $a ∈ (0, 1), b > 1$ ，即思想是如果没有设备传递则增加，在冲突后减小

网络 Networks

传播谣言

树形结构，从上至下传递，每个节点的子节点平均值为 $μ$ ，则 $Z$ 为最终收到消息的节点数，有

如果 $μ < 1$ ，则 $P(Z < ∞) = 1, E(Z) < ∞$
如果 $μ > 1$ ，则 $P(Z = ∞) > 0$

瀑布

节点 n 独立听从节点 n-k 的建议，概率为 $p_k$ ，则最终第一个节点的影响会消失

对于 $p_k = p$ ，每个节点变红的概率为

θ = e^{- \frac{1-p}{p}}

播种市场

每个节点只听左邻居，概率为 p；每个节点收到产品的概率为 $λ$ ，该节点变红，则红色节点的比率为

\psi(λ) = 0.5 \frac{1 + λ - p + λ p}{1 - p(1-λ)}

如果一个产品的花费为 c，售价为 s，则最大化利润的 $λ$ 为

λ^* = \min(1, \frac{(1-p)^{1/2} - (1-p)}{p} \sqrt{\frac{0.5(s-c)}{c}})

制造同意

随机选择三个人，三人的认识变为较多的一方。

媒体的力量：两蓝一红有 1-p 的概率变为蓝色，有 p 的概率不变，p 就代表着媒体的力量。

p(k) = P[X_{n+1} = k+1 | X_n = k] = (1-p)^3 \frac{k(k-1)(2N-k)}{2N(2N-1)(2N-2)}

q(k) = P[X_{n+1} = k-1 | X_n = k] = 3 \frac{(2N-k)(2N-k-1)k}{2N(2N-1)(2N-2)}

故可以求出

a(k) = P[T_{2N} < T_0 | X_0 = k]

最终得到递推关系：

α(k+1) = (1 +\frac{2N-k-1}{(1-p)(k-1)})α(k) - \frac{2N-k-1}{(1-p)(k-1)} α(k-1)

极化

模型：

如果 $G(v, w) = 1$ ，则 $v, w$ 是朋友
随机选取一个人，若其朋友大多为红色，则其变红

有如下结论：系统的状态收敛，但收敛结果是随机的。

对于前者，计算朋友之间的不一致程度，发现永远不增加，故收敛
对于后者，考虑一个矩形，相对顶点颜色相同，相邻顶点颜色不同，该矩形的收敛状态随机

M/M/1 队列

第一个 M 表示两次输入的时间间隔是无记忆的
第二个 M 表示服务时间是无记忆的
1 表示只有一个服务器

显然，还有其它的变形

易得，

L = E(X_t) = \sum_{n=0}^{∞} n(1 - ρ)ρ^n = \frac{λ}{μ - λ}

W = \frac{1}{μ - λ}

队列网络

定义通过队列的速率 $λ$

λ_1 = γ_1 + λ_1 p_1

λ_2 = γ_2 + λ_2 p_2

λ_3 = λ_1+ λ_2

令 $ρ_k = λ_k / μ_k$ ，则有唯一的不变分布为：

π(x_1, x_2, x_3) = π_1(x_1) π_2(x_2) π_3(x_3)

π_1(n) = (1 - ρ_1)p_1^n

π_2(n) = (1 - ρ_2)p_2^n

π_3(a_1, …, a_n) = p(a_1) ⋯ p(a_n) (1-p_3) ρ_3^n

其中 $p(1) = λ_1 / (λ_1 + λ_2), p(2) = λ_2 / (λ_1 + λ_2)$

让我们惊讶的是，三个队列的分布居然无关，对于每个队列，其可以等效为一个 M/M/1 的队列 $λ, μ$