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