FANDOM


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.

ReferencesEdit

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

See alsoEdit