Statistical difference

From CRYPTUTOR

Revision as of 14:46, 15 July 2008; view current revision
←Older revision | Newer revision→
Jump to: navigation, search

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

If X and Y are random variables on a discrete universe U, then the statistical difference between X and Y is defined to be

StatDiff(X,Y)=max_{S \in U}|Pr[X \in S]- Pr[Y \in S]|

The following two sets will satisfy the above definition

S=S_X={{\alpha \in U:Pr[X=\alpha]>Pr[Y=\alpha]}}
S=S_Y={\alpha \in U:Pr[Y=\alpha]>Pr[X=\alpha]}

Statistical Difference is metric to measure the resemblance between two probability ensembles. By definition StatDiff(X,Y) \in [0,1].StatDiff(X,Y)=1 if X and Y are dijoint and it equals 0 if they are identical. Statistical Difference can also be defined in the following manner, based on the L1 distance

StatDiff(X,Y)=\frac{1}{2} \sum_\alpha | \Pr[X=\alpha] - \Pr[Y=\alpha] |.
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Statistical_difference"
Personal tools