Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following game between party 1 and party 2. Party 1 is honest; i.e. it follows the game exactly:

Assume that party 1 flips a fair coin $b$, encrypts it to $c$, and sends $c$ to party 2. Party 2 returns a value $b'$. Finally, party 1 reveals b by decrypting c.

Party 2 wins if $b'=b$, and loses otherwise. Assume that the encryption is not perfect; therefore $c$ reveals partial information about $b$, such that party 2 learns that there's a 60% chance that $b=0$. What strategy maximizes the winning chance of party 2?

I think the problem can be symbolically denoted as follows:

  1. $\Pr[b=0] = \Pr[b=1] = 0.5$
  2. $\Pr[b=0 \mid c] = 1-\Pr[b=1 \mid c]= 0.6$

and we want to choose $\Pr[b'=0 \mid c]$ such that $\Pr[b'=b \mid c]$ is maximized.

PS: The encryption used above is in fact a commitment scheme, but let's not care about that.

share|cite|improve this question
Do you mean $Pr[b=0∣c]=1−Pr[b=1∣c]=0.6$? Also, shouldn't things depend on what $c$ is? If the probability that $b=0$ (given that you know $c$) is 60% regardless of what $c$ is, then the probability that $b=0$ (in the absence of knowing $c$ should be 60%). – Aaron Jun 23 '11 at 13:58
@Aaron: Corrected, thanks. Regarding the second point, party 2 knows c, and given his knowledge, he wants to bias $b'$ to maximize his winning chance. – M.S. Dousti Jun 23 '11 at 14:11
Why shouldn't party 2 just pick $b'=0$ and win 60%? – Ross Millikan Jun 23 '11 at 14:15
@Ross: That's a possibility; yet it assumes $b'$ is chosen independently of $b$. I need a proof for the optimized strategy. – M.S. Dousti Jun 23 '11 at 14:21
If, given what Party 2 knows, there is a 60% chance that $b=0$, he should set $b'=0$. The prior probabilities do not enter the problem at all. So assuming there is a 60% chance of $b=0$, if he guesses 0 with probability $p$ and 1 with probability $1-p$, he will be right $.6p+.4(1-p)=.4+.2p$, which is maximized when $p=1$. – Aaron Jun 23 '11 at 14:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.