用户: Cybcat/123 不等式

1不等式引入

在概率论中有这样一条神奇的不等式

定理 1.1 (123 不等式). 假设 $X,Y$ 是两个独立同分布的随机变量, 那么$$\mathbb{P}[|X-Y|\le 2]<3\mathbb{P}[|X-Y|\le 1].$$

该不等式得名 $123$ 不等式显然是因为其系数中出现的 $1,2,3$. 不过本质上说 $1,2$ 可以被换成两个正实数 $r,2r$, 毕竟只需将 $X,Y$ 乘一个常数就能得到一般的版本.

另外这个常数是最好的, 实际上考虑分布为 $2,4,6,\cdots ,2n$ 的均匀分布. 那么$$\mathbb{P}[|X-Y|\le 1]=\frac{1}{n},\mathbb{P}[|X-Y|\le 2]=\frac{3}{n}-\frac{2}{n^2}.$$由此可知 $3$ 不能被改进为更小的数.

一般地, 上述不等式可以被推广为

定理 1.2. 假设 $X,Y$ 是两个独立同分布的随机变量, $b>a>0$ 是两个正实数, 那么$$\mathbb{P}[|X-Y|\le b]<\left(2\lceil \frac{b}{a}\rceil -1\right)\mathbb{P}[|X-Y|\le a].$$这个常数也是最优的.

这个结论也是合情合理的, 毕竟只与两个数的比值有关. 用上面类似的分布和取极限的技巧, 可以检查这里的常数是最优的. 这回我们取 $\gamma ,2\gamma ,\cdots ,m\gamma$ 这样 $m$ 个数的均匀分布, 只需要 $\gamma >a,\gamma (\lceil b/a\rceil -1)\le b$ 即可.

2组合证明

现在让我们从另一个视角来考虑这个问题. 假设现在先取定有一列实数 $x_1,\cdots ,x_m$, 对正实数 $b>0$, 定义$$T_b:=\{(x_i,x_j):1\le i,j\le m,|x_i-x_j|\le b\}.$$也就是所有距离不超过 $b$ 的有序对子, 那么我们的核心结论是下面的不等式:

引理 2.1. 对任意正整数 $r>1$, 总有 $|T_r|<(2r-1)|T_1|$.

证明. 对序列的长度 $m$ 归纳. 首先 $m=1$ 时结论显然, 现在来看 $m-1$ 到 $m$ 的归纳步. 为了方便理解我们假设 $x_i$ 单调不减. 对任意 $i$ 考虑区间 $[x_i-1,x_i+1]$, 假设其中能包含 $\{x_j{\}}_j$ 中的元素至多为 $t+1$ 个, 并记 $x_i$ 为使得上述值取到 $t+1$ 中最大者. 现在考虑子列 $x_1,\cdots ,x_{i-1},x_{i+1},\cdots ,x_m$, 我们马上从该子列的归纳假设推出我们要的结果. 现在 $|T_1|=2t+1+|T_1^{\prime }|$, 这里我们用记号 $T_b^{\prime }$ 表示对这子列统计对子.

现在来看 $[x_i-r,x_i+r]$ 这一区间, 它可以被分成 $2r-1$ 个更小的区间: $$[x_i-r,x_i-r+1),\cdots ,[x_i-2,x_i-1),[x_i-1,x_i+1],(x_i+1,x_i+2],\cdots ,(x_i+r-1,x_i+r].$$那么由于 $x_i$ 的选择, 现在每个 $[x_i-1,x_i+1]$ 左边的区间中至多只能包含原序列中的 $t+1$ 个元素, 每个 $[x_i-1,x_i+1]$ 右边的区间至多包含原序列中的 $t$ 个元素 (为什么). 由此得知$$|T_r|\le 2(r-1)(t+1)+2rt+1+|T_r^{\prime }|=(2r-1)(2t+1)+|T_r^{\prime }|.$$由此我们根据归纳假设 $|T_r^{\prime }|<(2r-1)|T_1^{\prime }|$ 即可得到 $|T_r|<(2r-1)|T_1|$.

$\square$

这样一来, 神奇的事情就来了.

推论 2.2 (弱不等式). 假设 $X,Y$ 是两个独立同分布的随机变量, $r\in {\mathbb{Z}}_{+}$ 是正整数, 那么$$\mathbb{P}[|X-Y|\le r]\le \left(2r-1\right)\mathbb{P}[|X-Y|\le 1].$$

它是弱不等式的原因是中间的符号是 $\le$ 而不是原先严格的 $<$.

证明. 固定正整数 $m$, 令 $x_1,\cdots ,x_m$ 独立同分布地按照 $X$ 的分布取随机变量.

现在由前面的组合引理, 我们得知 $|T_r|<(2r-1)|T_1|$. 由此在等式两边计算期望我们得知$$m+m(m-1)\mathbb{P}[|X-Y|\le r]<(2r-1)\left(m+m(m-1)\mathbb{P}[|X-Y|\le 1]\right).$$于是令 $m\to +\infty$ 即可得到弱不等式.

$\square$

很显然对一般的实数 $r>1$, 可以将这里的 $r$ 换成上取整 $\lceil r\rceil$.

3强不等式

从弱不等式到原来的强不等式须费点功夫. 为了方便说话我们先定义一些量$$p_r:=$$