123 theorem

The 123-theorem is a theorem of stochastics :

For two stochastically independent and identically distributed real-valued random variables and applies ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle P(|X-Y|\leq 2)<3\cdot P(|X-Y|\leq 1)}$.

Under the same conditions applies to the generalization ${\displaystyle 0<a<b}$

${\displaystyle P(|X-Y|\leq b)<(2\lceil b/a\rceil -1)\cdot P(|X-Y|\leq a)}$.

Here denotes the rounding function . ${\displaystyle \lceil x\rceil }$

This theorem was proven by Noga Alon and Raphael Yuster .

Individual evidence

1. ↑ Noga Alon, Raphael Yuster: The 123 theorem and its extensions (PDF, 147 kB).