Editing Piling-up lemma (section)

==Boolean derivation==
The piling-up lemma allows the cryptanalyst to determine the [[probability]] that the equality:

:<math>X_1\oplus X_2\oplus\cdots\oplus X_n=0</math>

holds, where the ''X''{{'}}s are [[binary variable]]s (that is, bits: either 0 or 1).

Let ''P''(A) denote "the probability that A is true". If it equals [[probability one|one]], A is certain to happen, and if it equals zero, A cannot happen. First of all, we consider the piling-up lemma for two binary variables, where <math>P(X_1 = 0)=p_1</math> and <math>P(X_2 = 0)=p_2</math>.

Now, we consider:

:<math>P(X_1 \oplus X_2 = 0)</math>

Due to the properties of the [[xor]] operation, this is equivalent to

:<math>P(X_1=X_2)</math>

''X''<sub>1</sub> = ''X''<sub>2</sub> = 0 and ''X''<sub>1</sub> = ''X''<sub>2</sub> = 1 are [[mutually exclusive events]], so we can say

:<math>P(X_1=X_2)=P(X_1=X_2=0) + P(X_1=X_2=1)=P(X_1=0, X_2=0) + P(X_1=1, X_2=1)</math>

Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are '''[[Dependent and independent variables|independent]]'''; that is, the state of one has no effect on the state of any of the others. Thus we can expand the probability function as follows:

:{|
|-
|<math>P(X_1 \oplus X_2 = 0)</math>
|<math>=P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)</math>
|-
|
|<math>=p_1p_2 + (1-p_1)(1-p_2)</math>
|-
|
|<math>=p_1p_2 + (1-p_1-p_2+p_1p_2)</math>
|-
|
|<math>=2p_1p_2-p_1-p_2+1</math>
|}

Now we express the probabilities ''p''<sub>1</sub> and ''p''<sub>2</sub> as {{sfrac|1|2}} + ε<sub>1</sub> and {{sfrac|1|2}} + ε<sub>2</sub>, where the ε's are the probability biases &mdash; the amount the probability deviates from {{sfrac|1|2}}.

:{|
|-
|<math>P(X_1 \oplus X_2 = 0)</math>
|<math>=2(1/2+\epsilon_1)(1/2+\epsilon_2)-(1/2+\epsilon_1)-(1/2+\epsilon_2)+1</math>
|-
|
|<math>=1/2+\epsilon_1+\epsilon_2+2\epsilon_1\epsilon_2-1/2-\epsilon_1-1/2-\epsilon_2+1</math>
|-
|
|<math>=1/2+2\epsilon_1\epsilon_2</math>
|}

Thus the probability bias ε<sub>1,2</sub> for the XOR sum above is 2ε<sub>1</sub>ε<sub>2</sub>.

This formula can be extended to more ''X''{{'}}s as follows:

:<math>P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)=1/2+2^{n-1}\prod_{i=1}^n \epsilon_i</math>

Note that if any of the ε's is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased &mdash; equal to {{sfrac|1|2}}.

A related slightly different definition of the bias is
<math> \epsilon_i = P(X_i=1) - P(X_i=0),</math> 
in fact minus two times the previous value. The advantage is that now with

:<math>\varepsilon_{total}= P(X_1\oplus X_2\oplus\cdots\oplus X_n=1)- P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)</math>

we have

:<math>\varepsilon_{total}=(-1)^{n+1}\prod_{i=1}^n \varepsilon_i,</math>
 
adding random variables amounts to multiplying their (2nd definition) biases.