2
$\begingroup$

There are 2 people A and B and 2 experiments:

Experiment 0: $A$ flips a fair coin (probability $\frac{1}{2}$ for HEADS and $\frac{1}{2}$ for TAILS) and sends to $B$.

Experiment 1: $A$ always sends TAILS to $B$.

$B$'s goal is to output a bit indicating which experiment it is in.

For $i = 0, 1$ let $W_i$ be the event that in experiment $i$ the $B$ output $1$.

$B$ tries to maximize its distinguishing advantage, namely the quantity

$$|Pr[W_0] - Pr[W_1]|$$

How can I calculate the advantage given that $B$ behaves like this:

(i) Always output 1.

(ii) Output 1 if HEADS was received, else output 0.

(iii) If HEADS was received, output 1. Otherwise, randomly output 0 or 1 with even probab


I'm not familiar with these concepts, so every way I tried to calculate $|Pr[W_0] - Pr[W_1]|$ seemed to be wrong.

$\endgroup$
1
$\begingroup$

I think the main difficulty in that problem is that notation is not straightforward.

$Pr[W_0]$ is just the probability of B outputting 1 when A performs the experiment 0, and $Pr[W_1]$ is the probability of B outputting 1 when A performs the experiment 1.

For example, in (i), $Pr[W_0]=1$ and $Pr[W_1]=1$, too.

In (ii), $Pr[W_0]=\frac{1}{2}$, because $\frac{1}{2}$ is the probability of HEADS being received by B when A performs the experiment 0, and $Pr[W_1]=0$

(iii) can be solved the same way, although computing probabilities is a bit longer and an event tree may be helpful.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! I was thinking that I should take the probability of the experiment be 0 or 1 in consideration when computing $Pr[W_i]$ $\endgroup$ – Daniel Apr 2 '18 at 17:23

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