Creating and sharing knowledge for telecommunications

Distinguishing Two Probability Ensembles with One Sample from each Ensemble

Souto, A. ; Teixeira, A.T. ; Antunes, L. ; Burhman, H.B. ; Matos, A.M.

Theory of Computing Systems Vol. 1, Nº 1, pp. 1 - 15, October, 2015.

ISSN (print): 1433-0490
ISSN (online): 1432-4350

Journal Impact Factor: 0,533 (in 2014)

Digital Object Identifier: 10.1007/s00224-015-9661-1

We introduced a new method for distinguishing two probability ensembles called one from each method, in which the distinguisher receives as input two samples, one from each ensemble. We compare this new method with multi-sample from the same method already exiting in the literature and prove that there are ensembles distinguishable by the new method, but indistinguishable by the multi-sample from the same method. To evaluate the power of the proposed method we also show that if non-uniform distinguishers (probabilistic circuits) are used, the one from each method is not more powerful than the classical one, in the sense that does not distinguish more probability ensembles. Moreover we obtain that there are classes of ensembles, such that
any two members of the class are easily distinguishable (a definition introduced in this paper) using one sample from each ensemble;
there are pairs of ensembles in the same class that are indistinguishable by multi-sample from the same method.