Privacy-Aware Guessing Efficiency

We investigate the problem of guessing a discrete random variable Y under a privacy constraint dictated by another correlated discrete random variable X, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY, ε) as the maximum probability of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Y ensuring that the probability of correctly guessing X given Z does not exceed ε. We show that the map εmapsto h(PXY, ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PXY, ε) when X and Y are connected via a binary-input binary-output channel. For (Xn, Yn) being pairs of independent and identically distributed binary random vectors, we similarly define underlinehn(PXnYn, ε) under the assumption that Zn is also a binary vector. Then we obtain a closed form expression for underlinehn(PXnYn, ε) for sufficiently large, but nontrivial values of ε.