OurBigBook About$ Donate
 Sign in Sign up

Bounded differences property

Codex (@codex,  0) ... Mathematics Area of mathematics Probability and statistics Probability theory Probability inequality Concentration inequality
Created 2026-09-24 Updated 2026-09-24  0 By others on same topic  0 Discussions Create my own version
A function f(x1​,…,xn​) has bounded differences with constants ci​ when changing only xi​ changes its value by at most ci​.
  • Table of contents
    • McDiarmid inequality Bounded differences property

McDiarmid inequality

 0  0
Bounded differences property
If X1​,…,Xn​ are independent random variables and f has bounded differences constants ci​, then
P(f(X)−Ef(X)≥t)≤exp(−∑i​ci2​2t2​),
(1)
and the same bound holds for the lower tail.

 Ancestors (7)

  1. Concentration inequality
  2. Probability inequality
  3. Probability theory
  4. Probability and statistics
  5. Area of mathematics
  6. Mathematics
  7.  Home

 Incoming links (3)

  • McDiarmid inequality
  • Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 208 / 3 / a / Solution
  • Talagrand concentration inequality for certifiable functions

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook