当前位置：首页 > news >正文

霍夫丁不等式（Hoeffding‘s inequality）

news 2026/2/9 2:26:42

参考资料：Hoeffding's inequality | encyclopedia article by TheFreeDictionary

霍夫丁不等式（Hoeffding's inequality）描述了随机变量的和、与和的期望之差的上限；或者表述为：随机变量的均值、与均值的期望之差的上限。

假设 $X_{1},X_{2},...,X_{n}$ 为各自独立的随机变量，且 $X_{i}$ 限制在 $[0,1]$ 范围内，即 $0\leqslant X_{i}\leqslant 1$ ，定义 $\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ ，则对任意 $\epsilon \geq 0$ ，有

$P((\bar{X}-E(\bar{X}))\geq \epsilon )\leqslant exp(-2n\epsilon ^{2})$ (1)

$P(\left | \bar{X}-E(\bar{X}) \right |\geq \epsilon )\leqslant 2exp(-2n\epsilon ^{2})$ (2)

其中 $E(\bar{X})$ 表示平均值 $\bar{X}$ 的期望。

上面公式推广到更一般的形式：

$X_{i}$ 限制在 $[a_{i},b_{i}]$ 范围内，即 $a_{i}\leqslant X_{i}\leqslant b_{i}$ ，则对任意 $\epsilon > 0$ ，有

$P((\bar{X}-E(\bar{X}))\geq \epsilon )\leqslant exp(-\frac{2n^{2}\epsilon ^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}})$ (3)

$P(\left | \bar{X}-E(\bar{X}) \right |\geq \epsilon )\leqslant 2exp(-\frac{2n^{2}\epsilon ^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}})$ (4)

上面的公式也可表述为和的形式。

定义 $S_{n}=\sum_{i=1}^{n}X_{i}$

$P((S_{n}-E(S_{n}))\geq \epsilon )\leqslant exp(-\frac{2\epsilon ^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}})$ (5)

$P(\left | S_{n}-E(S_{n}) \right |\geq \epsilon )\leqslant 2exp(-\frac{2\epsilon ^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}})$ (6)

备注：当 $X_{i}$ 是通过不放回取样得到的，上面的不等式也成立，但此时随机变量不再是独立的。

霍夫丁不等式（Hoeffding‘s inequality）

相关文章：

霍夫丁不等式（Hoeffding‘s inequality）

【MATLAB源码-第90期】基于matlab的OQPSKsimulink仿真，对比初始信号和解调信号输出星座图。

自动驾驶芯片指标AI算力TOPS和CPU算力DMIPS

海外Leads Generation产业：中国出海群体的行业大机会

SQL sever2008中的游标

在linux中进行文件的打包（打压缩）和解压

mysql8下载与安装教程

ubuntu22.04在线安装redis，可选择版本

MYSQL加密和压缩函数详解和实战(含示例)

redis Redis::geoAdd 无效，phpstudy 如何升级redis版本

2024重庆大学计算机考研分析

二、Lua数据类型

Grabcut算法在图片分割中的应用

常用的Linux的指令

【STM32】GPIO输出

【Go语言从入门到实战】反射编程、Unsafe篇

vue实现对话框指定某个对话内容的滚动到指定位置（滚动到可视区域的中间位置）

【RTP】2：RtpPacket、RtpPacketToSend 创建、修改的简要分析

汽车租聘管理与推荐系统Python+Django网页界面+协同过滤推荐算法

qt pdf 模块简介

pam_env.so模块配置解析

STM32F4基本定时器使用和原理详解

Cinnamon修改面板小工具图标

数据链路层的主要功能是什么

从零开始打造 OpenSTLinux 6.6 Yocto 系统（基于STM32CubeMX）（九）

Spring Boot面试题精选汇总

在WSL2的Ubuntu镜像中安装Docker

Unsafe Fileupload篇补充-木马的详细教程与木马分享（中国蚁剑方式）

React---day11

return this；返回的是谁