Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Probability Discussions of probability theory

Reply
 
Thread Tools Display Modes
Old 07-14-2021, 09:43 PM   #1
somigosaden
adept
 
Join Date: Dec 2013
Location: sean-a-paul, somigosaden
Posts: 914
Flipping a coin to determine a winner with three people

Say I need to choose a random winner amongst three people and all I have to provide random outcomes is a coin. I could assign the first person TT, the second person HH, and the third person TH, and then HT is a "re-do." But that could theoretically continue indefinitely if I get unlucky enough to keep flipping HTs. I thought about flipping the coin three times, but with eight permutations possible, I'd still have a remainder (say, HTH and HTT) that I'd have to assign to the "re-do" outcome, so I haven't improved anything. I suspect that since there are no powers of two that are divisible by three, no amount of flips will leave me without some remainder that could result in a re-do. (It does get less likely that there won't be a winner with the more flips I do—5 flips means only a 2/32 chance it'll be a re-do, but it's still possible to have to do countless flips.)

Is there a way to fairly choose a random winner amongst three people with a definite number of coin flips?
somigosaden is offline   Reply With Quote
Old 07-15-2021, 12:42 AM   #2
pocketzeroes
veteran
 
Join Date: Aug 2010
Posts: 2,332
Re: Flipping a coin to determine a winner with three people

No, you can’t be certain to be able to select someone with a finite number of flips at exactly 1/3 chance of selection.
Imagine the whole (binary) tree of an infinite sequence of coin flips. Ie a tree with that always divides into two branches. We want to select exactly 1/3 of that tree by combining subtrees. No matter how you add the subtrees of that tree together, you are essentially always adding fractions of the tree with powers of two as denominator. Like you can add half the tree, or a quarter of the tree, or an eighth of the tree…

So you can only select events with probabilities that look like: a1 / 2 + a2 / 4 + a3 / 8… where a1, a2, a3, etc are all either 0 or 1.

This probability is equivalent to a decimal in base 2. Eg something that looks like
0.100011101010101100111111

But if you want exactly a 1/3 chance, you have to be able to express the decimal 1/3 =
0.010101010101010101010101…

In other words, there’s never going to be a way to add a finite number of subtrees together to get exactly 1/3 of the tree.
pocketzeroes is offline   Reply With Quote
Old 07-16-2021, 12:33 AM   #3
somigosaden
adept
 
Join Date: Dec 2013
Location: sean-a-paul, somigosaden
Posts: 914
Re: Flipping a coin to determine a winner with three people

Thanks for the response.
somigosaden is offline   Reply With Quote
Old 07-19-2021, 06:52 PM   #4
rivercitybirdie
Pooh-Bah
 
Join Date: May 2012
Posts: 4,323
Re: Flipping a coin to determine a winner with three people

i can't see a way but it's an interesting question.

obviously if you keep flipping in a round robin format, you will have a winner.. or 99.99%+ chance of a winner fairly quickly
rivercitybirdie is offline   Reply With Quote
Old 07-21-2021, 04:51 AM   #5
AllInNTheDark
veteran
 
AllInNTheDark's Avatar
 
Join Date: Jun 2011
Location: Pacific coast
Posts: 2,952
Re: Flipping a coin to determine a winner with three people

So we have entities A, B & C.

1. Split A & B into camp 1 and camp 2
2. Flip coin to add C to either camp 1 or camp 2
3. Flip coin to determine which camp is eliminated.
4. Remaining camp has either one (winner) or two entities.
5. If camp has two entities, use coin to determine winner.
AllInNTheDark is offline   Reply With Quote
Old 07-21-2021, 09:30 AM   #6
heehaww
Pooh-Bah
 
heehaww's Avatar
 
Join Date: Aug 2011
Location: Tacooos!!!!
Posts: 4,954
Re: Flipping a coin to determine a winner with three people

Quote:
Originally Posted by AllInNTheDark View Post
So we have entities A, B & C.

1. Split A & B into camp 1 and camp 2
2. Flip coin to add C to either camp 1 or camp 2
3. Flip coin to determine which camp is eliminated.
4. Remaining camp has either one (winner) or two entities.
5. If camp has two entities, use coin to determine winner.
That's unfair to C because C is always in a camp of two people. C has a 1/4 chance of winning while A and B each have a 3/8 chance.
heehaww is offline   Reply With Quote
Old 07-22-2021, 11:25 AM   #7
AllInNTheDark
veteran
 
AllInNTheDark's Avatar
 
Join Date: Jun 2011
Location: Pacific coast
Posts: 2,952
Re: Flipping a coin to determine a winner with three people

Quote:
Originally Posted by heehaww View Post
That's unfair to C because C is always in a camp of two people. C has a 1/4 chance of winning while A and B each have a 3/8 chance.
I knew it was too easy, back to the drawing board.
AllInNTheDark is offline   Reply With Quote
Old 07-22-2021, 11:43 PM   #8
Pokerlogist
veteran
 
Pokerlogist's Avatar
 
Join Date: Jul 2005
Location: "turn on ,tune in, drop out"
Posts: 2,938
Re: Flipping a coin to determine a winner with three people

Outside of the box: By some fortunate circumstances, the circumference of a America quarter is almost exactly 3 inches. So mark the quarter's coin edge with three marks at one inch intervals on each side. Now you have a coin that can be tossed and help you randomize into three equal probability outcomes on a single toss.
Pokerlogist is offline   Reply With Quote
Old 07-26-2021, 10:11 AM   #9
stremba70
centurion
 
Join Date: Aug 2020
Posts: 180
Re: Flipping a coin to determine a winner with three people

Take your coins to a store. Trade them for a six-sided die. Assign each player two integers between 1 and 6. Roll the die to determine the winner.

Obviously tongue-in-cheek, but there is no way to generate any space of outcomes using a coin whose size is anything but a power of 2. All powers of 2 are not divisible by 3, so your problem has no solution.
stremba70 is offline   Reply With Quote
Old 07-27-2021, 05:22 PM   #10
Eric
Carpal \'Tunnel
 
Eric's Avatar
 
Join Date: Oct 2009
Location: Still bitter about '94
Posts: 12,821
Re: Flipping a coin to determine a winner with three people

Again: no guarantee of finiteness, but in practice it will end.

Each person flips the coin. If all get the same result, do it again. Otherwise, the odd result is the winner.
Eric is offline   Reply With Quote
Old 07-28-2021, 11:29 AM   #11
whosnext
Carpal \'Tunnel
 
whosnext's Avatar
 
Join Date: Mar 2009
Location: California
Posts: 6,342
Re: Flipping a coin to determine a winner with three people

Yes, if three different "sequences" are allowed (one for each person), then there are innumerable ways to select a "winner" via randomness.
whosnext is offline   Reply With Quote
Old 07-28-2021, 01:27 PM   #12
stremba70
centurion
 
Join Date: Aug 2020
Posts: 180
Re: Flipping a coin to determine a winner with three people

Quote:
Originally Posted by Eric View Post
Again: no guarantee of finiteness, but in practice it will end.

Each person flips the coin. If all get the same result, do it again. Otherwise, the odd result is the winner.
OP was asking about solutions that don’t require “do overs” though. In practice you will always get a winner in a finite number of iterations. For any given N, the value 2^N has a remainder of either 1 or 2, so there are either 1 or 2 sequences of N flops that will not be assigned to one of the three players. The probability of such a sequence actually occurring is 2^-N if the remainder is 1 and 2^(-N+1) for a remainder of 2. In either case that probability tends to zero as N goes to infinity, so in practice we can make it as small as we like by increasing N. That doesn’t give a solution to OPs problem though. Since 2^N is never divisible by 3, no solution exists.
stremba70 is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 09:34 PM.


Powered by vBulletin®
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright © 2008-2020, Two Plus Two Interactive