Editing Coupling (probability) (section)

===Biased coins===

Assume two biased coins, the first with probability ''p'' of turning up heads and the second with probability ''q'' > ''p'' of turning up heads. Intuitively, if both coins are tossed the same number of times, we should expect the first coin turns up fewer heads than the second one. More specifically, for any fixed ''k'', the probability that the first coin produces at least ''k'' heads should be less than the probability that the second coin produces at least ''k'' heads. However proving such a fact can be difficult with a standard counting argument.<ref>{{cite book |last1=Dubhashi |first1=Devdatt |last2=Panconesi |first2=Alessandro |title=Concentration of Measure for the Analysis of Randomized Algorithms |publisher=Cambridge University Press |date=June 15, 2009|edition=1st |isbn=978-0-521-88427-3| page=91}}</ref> Coupling easily circumvents this problem.

Let ''X''<sub>1</sub>, ''X''<sub>2</sub>, ..., ''X''<sub>''n''</sub> be [[indicator random variable|indicator variables]] for heads in a sequence of flips of the first coin. For the second coin, define a new sequence ''Y''<sub>1</sub>, ''Y''<sub>2</sub>, ..., ''Y''<sub>''n''</sub> such that

* if ''X<sub>i</sub>'' = 1, then ''Y<sub>i</sub>'' = 1,
* if ''X<sub>i</sub>'' = 0, then ''Y<sub>i</sub>'' = 1 with probability (''q''&nbsp;−&nbsp;''p'')/(1&nbsp;−&nbsp;''p'').

Then the sequence of ''Y<sub>i</sub>'' has exactly the [[probability distribution]] of tosses made with the second coin. However, because ''Y<sub>i</sub>'' depends on ''X<sub>i</sub>'', a toss by toss comparison of the two coins is now possible. That is, for any ''k'' ≤ ''n''

:<math> \Pr(X_1 + \cdots + X_n > k) \leq \Pr(Y_1 + \cdots + Y_n > k).</math>