0
$\begingroup$

Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof.

Problem: Let $S$ be a set of $n$ elements, where $n\geq 2$ is even. And let $f:S \rightarrow \{0, 1\}$ be a function that maps half of the elements in $S$ to $0$, and the other half to $1$. Suppose Alice picks an element from $S$ at random and passes it through $f$ to obtain a value $x \in \{0, 1\}$. Prove there exists no algorithm $A$ that can correctly predict the value $x$ given only $f$ and $S$ (Take $A$ to be a probabilistic polynomial-time algorithm for example).

I understand that this statement seems entirely trivial, but I cannot really form an argument that feels rigorous. What is the basic proof I am missing, or the definition I need to use?

$\endgroup$

1 Answer 1

0
$\begingroup$

Assuming you are sampling from $S$ uniformly, let $X$ be the random variable you are sampling.

Then the random variable $f(X)$ is a Bernoulli distribution with probability 0.5 to get either $0$ or $1$.

Thus, $\Pr[f(x)=a]=0.5$ for any $a\in\{0,1\}$. So no matter which outcome the algorithm predicts (it has to be independent of the choice of $x$), the probability it is right is exactly $0.5$ - meaning that it cannot predict anything.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.