Let the statistical difference[1] between two distributions X and Y be defined as

 \Delta(X,Y)=\frac{1}{2} \sum _a | \Pr[X=\alpha] - \Pr[Y=\alpha] |.

We say that two probability ensembles \{X_k\}_{k\in\N} and \{Y_k\}_{k\in\N} are statistically close if \Delta(X_k,Y_k) is a negligible function in k.

Statistical difference is based on the L1 norm.


  1. Amit Sahai, Salil P. Vadhan: A complete problem for statistical zero knowledge. J. ACM 50(2): 196-249 (2003)

See alsoEdit

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.