有界度图序列中典型距离概率极限的证明问询

问题背景 #

设 $(G_n){n \geq 1}$ 是一个有界度图序列，即满足 $\max{v \in [n]}d_v = d_{\max} \leq K$（$K$ 为常数），且对每个 $n \geq 1$，$G_n$ 都是连通图，其中 $[n]$ 表示 $G_n$ 的顶点集。

我们需要证明：对任意 $\varepsilon > 0$，有
$$
\lim_{n \to \infty}\mathbb{P}(H_n \leq (1-\varepsilon)\log n/\log d_{\max}) = 0.
$$
这里的随机变量 $H_n$ 是典型距离：随机均匀选取两个顶点 $U_1, U_2$，定义 $H_n = \operatorname{dist}{G_n}(U_1, U_2)$，其中 $\operatorname{dist}{G_n}$ 表示 $G_n$ 中两点间的最短距离。

我的尝试 #

目前我还没找到完整思路，主要卡在如何分析这个概率事件。首先，因为 $G_n$ 是连通的，所以对所有 $n \geq 1$，$H_n < \infty$ 几乎必然成立。根据 $H_n$ 的定义，我们可以把目标概率改写为：
$$
\mathbb{P}(H_n \leq (1-\varepsilon)\log n/\log d_{\max}) = \mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) \leq (1-\varepsilon)\log n/\log d{\max}).
$$

令 $k_n := \lceil (1-\varepsilon)\log n/\log d_{\max} \rceil$，那么上式可以拆成求和形式：
$$
\mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) \leq k_n) = \sum{k = 0}^{k_n}\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k).
$$

接下来我想计算每个 $\mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) = k)$（$0 \leq k \leq k_n$），用全概率公式展开：
\begin{align*}
\mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) = k) &= \sum_{u,v \in [n]}\mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) = k|U_1 = u, U_2 = v)\mathbb{P}(U_1 = u, U_2 = v)\
&= \frac{1}{n^2}\sum{u,v \in [n]}\mathbb{I}{\operatorname{dist}_{G_n}(u, v) = k}
\end{align*}
（这里用指示函数 $\mathbb{I}{\cdot}$ 替代条件概率，因为当给定 $U_1=u, U_2=v$ 时，距离是否等于 $k$ 是确定事件）

当 $k=0$ 时，只有 $u=v$ 时指示函数取1，所以：
$$
\mathbb{P}(\operatorname{dist}{G_n}(U_1, U_2) = 0) = \frac{1}{n^2}\sum{u \in [n]}1 = \frac{n}{n^2} = \frac{1}{n}.
$$
这部分我算出来了，但对于 $k \neq 0$ 的情况，我不知道怎么继续推导下去，希望能得到思路上的提示。

备注：内容来源于stack exchange，提问作者Vicky