[superprismatic]

Two really talented mathematicians are

chosen to play a little game. Neither

mathematician is told the identity or

whereabouts of the other. So, we can

assume that there is no possibility that

these two can communicate regarding this

game until it is completed. The game

itself is simple: Each is given a fair

coin. Each must then decide whether he

will make an "official" coin flip with

this coin. If at least one of the two

mathematicians makes an "official" coin

flip AND every "official" coin flip

comes up heads, each of them will

receive $1,000,000. If neither of them

makes an "official" coin flip OR an

"official" coin flip comes up tails,

they lose and get nothing. What strategy

should these mathematicians employ to

maximize the probability that they will

win? What is the winning probability

associated with the best strategy?

Please note: I use the term "official"

coin flip because I didn't want to

preclude allowing the mathematicians

the ability to use the coin in some way

to decide whether to make an "official"

coin flip or not.

[bonanova]

Here's a start.

Each players flips his coin unofficially and then officially iff first flip is HEADS.

1/4 of the time both will flip officially, with expectation of $1/4 million.

1/2 of the time one will flip officially, with expectation of $1/2 million.

1/4 of the time neither will flip officially, with expectation of $0 million.

Total expectation would be $5/16 million.

Probably that's not optimum

What the probability is, that it is not optimum, I don't know how to calculate.

But, probably, this can be improved by multiple unofficial flips, that will increase

the probability the only one of them will flip - the highest expectation case.

[bonanova]

Next try.

Each person rolls officially with probability p.

Expectation is 1/4 p² + 1/2 2p(1-p). Which is 5/16 when p=1/2.

Differentiating wrt p and setting equal to zero we get p=2/3.

So if both persons roll officially with the same probability, their expectation is maximized when p=2/3.

The maximum expectation is 1/3 = 5/15, slightly larger than the previous outcome of 5/16.

And clearly better than the 1/4 = 4/16 which obtains when both officially roll with certainty.

Next question, obviously, is how do you roll with probability 2/3 using a fair coin?

You can flip a coin N times, where N is a large number, and find a combination of HT outcomes

that comes arbitrarily close to 2/3, but how do you get 2/3 exactly?

And, is the supposition valid that both roll officially with the same probability?

I guess it is, simply by symmetry.

If symmetry could be broken, then A flips and B does not flip might be possible,

yielding a 50% chance of winning. There can't be a way to do that without communicating.

[superprismatic]

Next try.

Each person rolls officially with probability p.

Expectation is 1/4 p² + 1/2 2p(1-p). Which is 5/16 when p=1/2.

Differentiating wrt p and setting equal to zero we get p=2/3.

So if both persons roll officially with the same probability, their expectation is maximized when p=2/3.

The maximum expectation is 1/3 = 5/15, slightly larger than the previous outcome of 5/16.

And clearly better than the 1/4 = 4/16 which obtains when both officially roll with certainty.

Next question, obviously, is how do you roll with probability 2/3 using a fair coin?

You can flip a coin N times, where N is a large number, and find a combination of HT outcomes

that comes arbitrarily close to 2/3, but how do you get 2/3 exactly?

And, is the supposition valid that both roll officially with the same probability?

I guess it is, simply by symmetry.

If symmetry could be broken, then A flips and B does not flip might be possible,

yielding a 50% chance of winning. There can't be a way to do that without communicating.

Nice! You have it nailed. Now, you can decide with probability p exactly with coin flips.

Simply write p as a binary number and flip until the number the flips give is not equal to the

binary p. Flip number less than p, call the decision made; greater than p, call it not made;

equal to p so far, flip again. You could be in for a lot of flips, however. It's interesting to

see what the winning flip probability and associated win probability are as the number of

players approach infinity.

[CaptainEd]

If I understand the goal right, you want to generate A with probability 2/3 and B with probability 1/3, using coin flips

Flip two coins.

If both heads, declare B

If HT or TH, declare A

if both tails, repeat.

let E be the expectation of getting A

When you flip two coins, half the time you get A, one quarter of the time you get B, and the other quarter you get E.

E = 1/2 + E/4

3*E / 4 = 1/2

E = 2/3

Probably don't have to flip a whole lot.

[superprismatic]

If I understand the goal right, you want to generate A with probability 2/3 and B with probability 1/3, using coin flips

Flip two coins.

If both heads, declare B

If HT or TH, declare A

if both tails, repeat.

let E be the expectation of getting A

When you flip two coins, half the time you get A, one quarter of the time you get B, and the other quarter you get E.

E = 1/2 + E/4

3*E / 4 = 1/2

E = 2/3

Probably don't have to flip a whole lot.

Nice way of getting 2/3! It works well with this problem.

[bonanova]

Yeh Ed, good one. I forgot you could ignore cases, I was trapped in powers of two.