Proposition

Lemma 3 ([Bounded differences]). Let Z be a function of s≥1 independent finite random variables. If changing one variable changes Z by at most b>0 , then (|Z-𝔼Z|≥u) ≤2(-u^2/(2sb^2)) (u>0).

Prove 1Disprove 0Cited as proposition 3Chain graphAdd Your Proof

Add Your Proof1

Prove
Lemma 2. Suppose |V(P)|≤n , where n≥1 , and f(P)≤r , where r≥1 . There is a…Theorem 2.3 ([Grouping terminals]). There is an absolute integer γ≥1 such that…Proposition
Expose the variables in order. The martingale of conditional expectations has differences of conditional mean zero and absolute value at most b . Convexity bounds the conditional exponential moment of a difference at λ by (λb)≤(λ^2b^2/2) . Multiplying these bounds and applying Markov's inequality with λ=u/(sb^2) gives the upper tail. Apply the same argument to -Z and add the two bounds.
Show More →