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(P_{XY},\ \varepsilon)$ as the maximum probability of correctly guessing $Y$ given an auxiliary random variable $Z$, where the maximization is taken over all $P_{Z\vert Y}$ ensuring that the probability of correctly guessing $X$ given $Z$ does not exceed $\varepsilon$. We show that the map $\varepsilon\mapsto h(P_{XY},\ \varepsilon)$ is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for $h(P_{XY},\ \varepsilon)$ when $X$ and $Y$ are connected via a binary-input binary-output channel. For $\{(X_{i},\ Y_{i})\}_{i=1}^{n}$ being pairs of independent and identically distributed binary random vectors, we similarly define $\underline{\boldsymbol{h}}_{n}(P_{X^{n}Y^{n}},\varepsilon)$ under the assumption that $Z^{n}$ is also a binary vector. Then we obtain a closed form expression for $\underline{\boldsymbol{h}}_{n}(P_{X^{n}Y^{n}},\ \varepsilon)$ for sufficiently large, but nontrivial values of $\varepsilon$.