Randomizing with a coin

[BruceZ]

Actually it's easy. Just take a marker and divide each side into three 120 degree sectors. [img]/images/graemlins/laugh.gif[/img]

For the methods that depend on heads and tails, worrying about the game never terminating makes no more sense than worrying about the coin landing on its edge. I suggest flipping the coin until it comes up heads. Then:

Rock: First head is on an even numbered flip.

Paper: First head is on an odd numbered flip, and the next flip is also heads.

Scissors: First head is on an odd numbered flip, and the next flip is tails.

[AlienBoy]

[ QUOTE ]
Actually it's easy. Just take a marker and divide each side into three 120 degree sectors. [img]/images/graemlins/laugh.gif[/img]

For the methods that depend on heads and tails, worrying about the game never terminating makes no more sense than worrying about the coin landing on its edge. I suggest flipping the coin until it comes up heads. Then:

Rock: First head is on an even numbered flip.

Paper: First head is on an odd numbered flip, and the next flip is also heads.

Scissors: First head is on an odd numbered flip, and the next flip is tails.

[/ QUOTE ]





MMMmmmmmmmmm.


Then 50% will be ROCK, and paper or scissors will be 25% each.

AB

[AlienBoy]

It can be done with double flips.

H=Head T=Tail

If the next TWO flips are:

HH = ROCK

HT = PAPER

TH = SCISSORS

TT = NULL (discarded result)


AB

[BruceZ]

[ QUOTE ]
[ QUOTE ]
Actually it's easy. Just take a marker and divide each side into three 120 degree sectors. [img]/images/graemlins/laugh.gif[/img]

For the methods that depend on heads and tails, worrying about the game never terminating makes no more sense than worrying about the coin landing on its edge. I suggest flipping the coin until it comes up heads. Then:

Rock: First head is on an even numbered flip.

Paper: First head is on an odd numbered flip, and the next flip is also heads.

Scissors: First head is on an odd numbered flip, and the next flip is tails.

[/ QUOTE ]





MMMmmmmmmmmm.


Then 50% will be ROCK, and paper or scissors will be 25% each.

AB

[/ QUOTE ]

No, they will be 1/3 each.

rock (even): 1/4 + 1/16 + 1/64 + 1/256 + ... = 1/(1 - 1/4) - 1 = 1/3

paper or scissors (odd): the other 2/3, or 1/3 each

You can generate any probabilty this way, even irrational ones like sqrt(2)/pi, by writing out its binary representation, in our case 1/3 = .01010101..., and letting the winner be when heads occurs on the flips with a 1.

[jason1990]

The algorithm that BruceZ proposes for deciding whether or not to throw rock has two nice properties.
<ul type="square">
[1] It terminates with probability one.
[2] It generates an event with probability p = 1/3.[/list]If I've done my calculations correctly, the expected running time of this algorithm is 2 flips. Can we do better than that? Clearly, the expected running time of any algorithm is at least 1, but can we find an algorithm whose expected running time is between 1 and 2? What is the optimal expected running time? What if we change p to something else? Must p be rational?

[punter11235]

[ QUOTE ]
If I've done my calculations correctly, the expected running time of this algorithm is 2 flips. Can we do better than that? Clearly, the expected running time of any algorithm is at least 1, but can we find an algorithm whose expected running time is between 1 and 2? What is the optimal expected running time? What if we change p to something else? Must p be rational?

[/ QUOTE ]

You are teasing with us , right ? [img]/images/graemlins/smile.gif[/img]
I remember solving similair excersise at my exam (probabilistic algorithm). It was about finding the best algorithm to use a coin to determine on of 5 equally probable event or something like that.
I cant remember anything from it though [img]/images/graemlins/frown.gif[/img] ( I am bad computer scientists...).

[AlienBoy]

[ QUOTE ]


No, they will be 1/3 each.

rock (even): 1/4 + 1/16 + 1/64 + 1/256 + ... = 1/(1 - 1/4) - 1 = 1/3

paper or scissors (odd): the other 2/3, or 1/3 each

You can generate any probabilty this way, even irrational ones like sqrt(2)/pi, by writing out its binary representation, in our case 1/3 = .01010101..., and letting the winner be when heads occurs on the flips with a 1.

[/ QUOTE ]


Sorry Bruce - thought I caught a mistake - I should have known better! [img]/images/graemlins/smile.gif[/img]


Looking at it I think I now see the genius behind your statement, which on the surface was not apparent.

Do I understand this correctly?? :


The first head on the second (an even) flip is probability of 1/4, and on the fourth is thus 1/16 etc etc - and the sum of all possible probabilities here to infinity equals 1/3.

It's funny how un-intuitive it is (at least to me), but explained the elegance is sublime...


AB



EDIT: I fixed a typo in my equation that you quoted. = -BZ

[AaronBrown]

AlienBoy's system is correct, but it doesn't guarantee a decision in any finite number of flips.

[SumZero]

[ QUOTE ]
AlienBoy's system is correct, but it doesn't guarantee a decision in any finite number of flips.

[/ QUOTE ]

But does BruceZ's guarantee a decision in any finite number of flips either? Both of them keep going as long as you keep flipping T.

For both of them what is the probability that I have no decision after N flips can be determined and is non-0 for all N. For both of them if you said I want a probability that I have no decision to be less than epsilon for any given epsilon &gt; 0 you can pick an M such that the probability that you have no decision after M flips is less than epsilon.

[AlienBoy]

Can't have a finite number, because there always must be a null event.


AB