Azuma–Hoeffding inequality
martingale
\(\mathbb{E}\!\left[M_\ell \mid \mathcal{F}_{\ell-1}\right] = M_{\ell-1}\)
bounded differences
\(\left|M_\ell - M_{\ell-1}\right| \le c\)
Azuma
\(\Pr\!\left(|M_k - M_0| \ge \lambda\right) \le 2\exp\!\left(-\dfrac{\lambda^2}{2kc^2}\right)\)
envelope
\(\lambda = \theta\,c\sqrt{k}\ \Rightarrow\ \Pr \le 2e^{-\theta^2/2}\)
On screen now
Walk
Lemma
Pause
Restart
‹ Back
Next ›
Step
00 / 40
Deviation
0
Mean
—
tail level \(\theta\) in \(\lambda = \theta\,c\sqrt{k}\)
2.60
Azuma bound · leaves
≤ 6.8%
observed · 4000 samples
0.0%
value axis
vertex shown good
accumulated failure \(n\varepsilon\)
failure budget
triple through \(v\)
other triple of \(H\)
triple \(\{v,u,w\}\) of \(H\)
its link edge \(uw\)
tracked path
ensemble · 8 runs
envelope \(\pm\lambda\)
extreme run
inside \(\pm\lambda\)
escape region · Azuma bounds its probability
step gate \(\pm c\)
good band · the rails \(r'_v\) must stay between
forced-pivot offset \(F_v\)