# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

 Picking a random person with coin flips Goto page 1, 2  Next
Author Message
Trojan Horse
Daedalian Member

 Posted: Mon Mar 18, 2013 11:39 pm    Post subject: 1 This one is inspired by some experimenting I did at www.random.org recently. 1. Three friends go out to lunch together, and they decide to pick one person at random to pay the bill. Unfortunately, the only randomizing device they have is a single coin. Your task: find a way to pick one of the three people at random using a series of coin flips. Each person must have a 1/3 chance of being selected. Also, you need to minimize the number of coin flips that will be needed on average. 2. Same scenario as #1, but now there are five friends. Find a way to pick one of the five at random (each with a 1/5 chance), using as few coin flips (on average) as possible. 3. Now there are only four friends. This would make things far easier, except for one thing: one person in the group (let's call him Mr. X) has ordered a much more expensive meal than anyone else. It is decided that Mr. X should have double the chance of paying the bill as anyone else. (So, Mr. X should have a 2/5 chance, and everyone else should have a 1/5 chance.) How can they do this, using as few coin flips (on average) as possible?

 Posted: Tue Mar 19, 2013 1:38 am    Post subject: 2 Here's the naive answer. 1. For three: If Alice H, Bob H -> Charlie pays If Alice T, Bob H -> Alice pays If Alice H, Bob T -> Bob pays If Alice T, Bob T -> flip again. That's about 3 1/3 rolls on average I think (I have to sum an infinite geometric series which I forget how to do). 2, For five is it just, 3 people roll, pick your permutations, and reroll on 3/5 of the possible outcomes? What's the average number of rolls on that? Around 4.6? 3. Give one guy 2 outcomes, 3 people 1 outcomes, and reroll on 3 outcomes.
groza528
No Place Like Home

 Posted: Tue Mar 19, 2013 5:04 am    Post subject: 3 For 1. that infinite sum is actually 2.666667 For 2. it comes out to 4.8; I can improve on that by having four people flip coins and each person taking 3 permutations. Then it drops to 4.266667
groza528
No Place Like Home

 Posted: Tue Mar 19, 2013 5:33 am    Post subject: 4 Actually I think I can improve on my previous improvement with a minor change... It all comes down to taking care which permutations you assign. For example, if the three permutations assigned to Alice are HHHH, HHHT, and HHTH, then you can get away with only three tosses some of the time. If the first three come up heads then you know it will be Alice regardless of the fourth toss and you need not flip the fourth coin. All five friends can be assigned in such a manner, such that 2/3 of the time the fourth toss is not needed. This brings the average number of tosses down to 3.6 for question 2. As for question 3. we can apply a similar model, but for the chap that has twice the chances we can get away with only *two* tosses in some cases, which should bring the average I believe to 3.2
lostdummy
Daedalian Member

 Posted: Tue Mar 19, 2013 1:38 pm    Post subject: 5 This depend on what we want to minimize, number of coin ROUNDS (ie minimizing time), or number of individual coin tosses. If minimizing individual coins, then I also have 3.6 average tosses for #2 and 3.2 average tosses for #3, by using 4 coins per round.
Trojan Horse
Daedalian Member

Posted: Tue Mar 19, 2013 2:08 pm    Post subject: 6

 lostdummy wrote: This depend on what we want to minimize, number of coin ROUNDS (ie minimizing time), or number of individual coin tosses.

My intention was to minimize individual coin tosses. So yeah, you guys got it. (Boy, this puzzle didn't last long.) #1 can be done with 2 2/3 tosses on average, #2 can be done with 3.6 tosses on average, and #3 can be done with 3.2 tosses on average.

Now I need to tell you guys what inspired this puzzle. Post forthcoming...
Trojan Horse
Daedalian Member

 Posted: Tue Mar 19, 2013 2:30 pm    Post subject: 7 My inspiration for this puzzle: www.random.org uses atmospheric noise to generate a truly random sequence of bits. These bits can then be used to generate all sorts of random things; you can use random.org to get a sequence of random die rolls, or to get a random ordering for names in a list, or whatever. Thing is, it costs money to generate random bits this way, so the guy running random.org wants to make sure that no one person hogs all the bits. He has set up a quota system; each IP address gets a quota of 1,000,000 bits. Each day, you gain back 200,000 of the bits you have used up, until you are back up to a total of 1,000,000 bits. (Those who really need more bits can always pay for more.) Given that random.org has these measures in place, I was curious: what does random.org do to minimize the number of bits used for each request? Let's say I asked random.org for 1000 rolls of a 20-sided die. Here are a few ways random.org could do that: 1. The naive solution. Assign each number from 1 to 20 a sequence of five bits. Then get five bits from the stream. If they match one of the 20 chosen sequences, fine. Otherwise, throw them out, and grab five more bits. On average, this requires 5x(32/20)=8 bits per die roll, for an overall average of 8000 bits. 2. Optimize each die roll. You guys figured out that picking a number from 1 to 5 requires 3.6 bits on average. Using that, you can pick a number from 1 to 20 using 5.6 bits on average. For 1000 die rolls, that comes to 5600 bits on average. 3. Buy in bulk. Instead of generating 1000 numbers from 1 to 20, you can generate a single number from 1 to 20^1000. Then use that to get the 1000 die rolls. You have to keep track of a lot more bits at the same time, but you end up using fewer bits: 4323, on average (rounded up to the nearest integer). So, how much optimizing does random.org do? I asked random.org for 1000 rolls of a 20-sided die, then I checked to see how many bits I had used up. The total was roughly 8000 bits, and it was an exact multiple of five. From that, and from further tests, I have concluded that random.org is using the naive solution for everything. Given that they are trying to be frugal with their bits, that's disappointing.
Zag
Tired of his old title

Posted: Tue Mar 19, 2013 3:32 pm    Post subject: 8

 Trojan Horse wrote: I asked random.org for 1000 rolls of a 20-sided die, then I checked to see how many bits I had used up. The total was roughly 8000 bits, and it was an exact multiple of five.

If it wasn't exactly 5000 bits, which is what I would have assumed they would "charge" you, then I think that the multiple of 5 is just a coincidence.
gftt*
Guest

 Posted: Tue Mar 19, 2013 4:22 pm    Post subject: 9 All of the above scenarios require an unbounded number of flips. They'll all terminate in a finite number of flips with probability one, but you can't set a cap on the number of flips prior to carrying out the experiment. Can you pick between three options with exactly 1/3 probability each if you have a bounded number of flips of an UNFAIR coin? You can choose how the coin is weighted.
Zag
Tired of his old title

Posted: Tue Mar 19, 2013 5:27 pm    Post subject: 10

 gftt* wrote: You can choose how the coin is weighted.

Then I choose exactly 1/3. I flip once. If it's heads, I choose person A. If it's tails, I pull out a real coin and flip that. Two flips and done.
Trojan Horse
Daedalian Member

Posted: Tue Mar 19, 2013 6:23 pm    Post subject: 11

 gftt* wrote: Can you pick between three options with exactly 1/3 probability each if you have a bounded number of flips of an UNFAIR coin? You can choose how the coin is weighted.

Very interesting! Yes, it can be done. Here's how:

I will choose p to be the probability of heads, where p satisfies p^4 + (1-p)^4 = 1/3. In other words, the probability of getting all heads or all tails in four flips will be 1/3. (My handy-dandy Mathematica gives me an approximation of 0.757869 for p.)

Then distribute the possible sets of four flips as follows:

Option A: HHHH, TTTT
Option B: HHHT, HHTH, HHTT, HTHT, HTTH, HTTT, THTT
Option C: HTHH, THHH, THHT, THTH, TTHH, TTHT, TTTH

In other words, options B and C each get half of the one-tail possibilities, half of the two-tail possibilities, and half of the three-tail possibilities. Since I already know option A is getting a probability of 1/3, options B and C must be getting probabilities of 1/3 also. That does it!

As for whether there is a solution where p is rational... that seems to be impossible.
grz*
Guest

Posted: Wed Mar 20, 2013 4:50 am    Post subject: 12

 Zag wrote: If it wasn't exactly 5000 bits, which is what I would have assumed they would "charge" you, then I think that the multiple of 5 is just a coincidence.

The significance of it being a multiple of 5 is that it the number of tosses for each random number is 5, to create a 5-bit number. Then, as TH has said, if it isn't between 1-20 inclusive, you simply start fresh with another set of 5. In such a case only 62.5% of the first set of flips would resolve to a single random number, which means 37.5% of the time they are making 5 more flips. And 12% or so would make a *third set of 5 flips, etc, but it would always be in increments of 5.
The *optimal* case would sometimes be an exact multiple of 5. The "easy" case would ALWAYS be a multiple of 5, and more importantly, has an expected value of 8000 flips, which is what the actual number came out to be (well, within statistical variation.)
Zag
Tired of his old title

 Posted: Wed Mar 20, 2013 10:41 am    Post subject: 13 I guess. I'm a little surprised that they would charge you for actual bits generated, rather than bits delivered. We could do a test: 1000 d32 's should be exactly 5000 bits, while 1000 d17's would be nearly 10,000. TH: Nicely done.
gftt*
Guest

Posted: Wed Mar 20, 2013 11:39 am    Post subject: 14

 Trojan Horse wrote: As for whether there is a solution where p is rational... that seems to be impossible.

I wouldn't be too surprised if this were true, but I'm curious why you seem confident in it.
Trojan Horse
Daedalian Member

 Posted: Wed Mar 20, 2013 4:50 pm    Post subject: 15 Because I think I found a proof for it. My first attempts were with p rational: I first tried p=2/3. I thought it would be a cinch. Then an issue arose that I hadn't expected. The issue was so pervasive that it seemed to preclude p from being rational at all. So I tried to prove that p can't be rational, and I think I've succeeded. To be more precise, here's what I claim: Say you are going to use a (possibly unfair) coin to choose between n alternatives, and you want each alternative to be chosen exactly 1/n of the time. Assume that 1. the probability, p, of getting heads must be rational, and 2. the overall protocol must have a finite upper bound for the number of required coin tosses. This is only possible if the coin is fair, and n is a power of 2. Due to laziness and a desire to give you guys a challenge (but mostly laziness), I won't post the proof right now.
Scurra
Daedalian Member

Posted: Wed Mar 20, 2013 7:50 pm    Post subject: 16

 Trojan Horse wrote: Due to laziness and a desire to give you guys a challenge (but mostly laziness), I won't post the proof right now.
Also because the margin is too small to contain it.

(I have been doing this the hard way and eventually managed to come up with the 2 2/3 solution for the first one. I failed miserably on the other two because I couldn't figure out how to allocate the tosses. (Admittedly I didn't spend very long trying...)
_________________
still Quiz Olympiad champion. Must get a life.
New definitions: COFFEE - someone who is coughed upon
groza528
No Place Like Home

Posted: Wed Mar 20, 2013 9:19 pm    Post subject: 17

 Scurra wrote: (I have been doing this the hard way and eventually managed to come up with the 2 2/3 solution for the first one. I failed miserably on the other two because I couldn't figure out how to allocate the tosses. (Admittedly I didn't spend very long trying...)

The generic explanation for allocating the tosses seems to be...
1. Determine which desired outcome has the highest probability; define that probability as P1.
2. Flip as few times as possible until the probability of a single outcome is less than or equal to P1, and assign permutations to that outcome.
3. Consider only the remaining unassigned permutations and leftover probabilities.
4. Goto 1.
Amb
Amb the Hitched.

Posted: Thu Mar 21, 2013 1:32 am    Post subject: 18

 Quote: Three friends go out to lunch together, and they decide to pick one person at random to pay the bill. Unfortunately, the only randomizing device they have is a single coin. Your task: find a way to pick one of the three people at random using a series of coin flips. Each person must have a 1/3 chance of being selected. Also, you need to minimize the number of coin flips that will be needed on average.

Who needs flipping:

Give the coin to the waitress, and ask her to pick who is paying the bill. SHe can keep the coin towards her tip.

Put your dinner plates upside down and have the waiter slip the coin under one while your backs are turned. Each person selects a plate, and whoever picks the plate with the coin - pays.

Add the digits of the year of the coin. eg 1969 = 25. Repeat until you get 1 digit. 1969 = 25 = 7 Divide by 3. If remainder is 1, pick person A. If remainder is 2, pick person B. If remainder is 0 pick person C. For extra security have the waitress switch the coin with one in the till.
groza528
No Place Like Home

 Posted: Thu Mar 21, 2013 3:33 am    Post subject: 19 We usually just play credit card roulette
bonanova
Daedalian Member

 Posted: Thu Mar 21, 2013 9:03 am    Post subject: 20 Corollary: simulate an unfair coin (heads has probability p) using a fair coin, and fewest flips._________________ Vidi, vici, veni.
lostdummy
Daedalian Member

Posted: Fri Mar 22, 2013 10:07 am    Post subject: 21

 Trojan Horse wrote: 3. Buy in bulk. Instead of generating 1000 numbers from 1 to 20, you can generate a single number from 1 to 20^1000. Then use that to get the 1000 die rolls. You have to keep track of a lot more bits at the same time, but you end up using fewer bits: 4323, on average (rounded up to the nearest integer).

I would have used this one ;p

But problem is that it may have (VERY) small variation from perfect random, because 2^4322 (or 2^n for any n) is not divisible by 20 - remainder is 4, which is lowest possible remainder for 2^n%20.

I don't know how to calculate how that would influence 'randomness', and I bet answer is 'very little', in range of 1/2^4320.

But I guess people who use 'random.org' instead of regular random generator could be very sensitive about purity of their random numbers ;p

Anyway, optimization with 5600 bits would return 'perfect' random20, and for not using that one they have no excuse .... EXCEPT if they actually use that one, and 'charge' you for naive implementations, thus earning 40% more ;p
lostdummy
Daedalian Member

Posted: Fri Mar 22, 2013 10:21 am    Post subject: 22

 bonanova wrote: Corollary: simulate an unfair coin (heads has probability p) using a fair coin, and fewest flips.

One way to do it: toss twice, and if you get TH , then its 'head', and if you get HT then its 'tail', since their chances are same, p(1-p)=(1-p)p. If you get TT or HH, you toss again.

I think average number of flips would be 1/(p(1-p)) , since probability to get either HT or TH is p(1-p), so probability to get valid result in first round in pV=2*p(1-p). And average number of needed rounds is 1/pV, with two coin flips per round, resulting in 2/pV average flips = 1/(p(1-p)). Average needed flips minimize for p close to 1/2, and gets very large for p close to 0 or 1.

Of course, knowing exact p, this could be optimized. In above case, we have valid solution only with HT or TH.

For example, if for some p, p(HT+TH)=p(TT), then those could be used . Solving that [(1-p)^2=2p(1-p) ] gives p=1/3. In generic solution (HT vs TH), for p=1/3 it would be needed 4.5 flips on average, while with this (HT+TH vs TT) it needs only 2.25 flips.

Interestingly, aside from this HT+TH=TT, and its mirror HT+TH=TT, which both resutl in p=1/3, I checked most of other possible combinations, and they either have result p=1/2 ( TH+HT=TT+HH) or have no solutions (TH=HH+TT), so it seems with two coin flips only 1/3 can be easily optimized ;p

There is possibility for more of this 'grouping' combinations with 3 or 4 flips per round, but it would depend on p if they would be possible, or more efficient.
bonanova
Daedalian Member

 Posted: Fri Mar 22, 2013 1:32 pm    Post subject: 23 Actually it's the inverse problem. You want to use a fair coin but not have the outcomes be equally probable: Option a is to be chosen with probability p and option b with (1-p). How, using fewest flips could that be done?_________________ Vidi, vici, veni.
lostdummy
Daedalian Member

Posted: Fri Mar 22, 2013 2:21 pm    Post subject: 24

 bonanova wrote: Actually it's the inverse problem. You want to use a fair coin but not have the outcomes be equally probable: Option a is to be chosen with probability p and option b with (1-p). How, using fewest flips could that be done?

Well, its very similar problem - but I don't think there is universal solution for any p.

It is similar because if we toss N coins, we again end up with some probabilities for each possible combination (only here they are all same , 1/2^n), and we again try to group those probabilities so that p(desired) = p(group1)/[p(group1)+p(group2)], and in case we roll something outside that group, we reroll.

For p=1/n , where n is integer, there could be some general solution, in form of: Toss n-1 coins. If you get all heads (HH...) it "Head", and if you get single head (HTT.., THTT...), it is "Tail". Otherwise reroll.

This because looking at all combinations with N coins, number of "all heads" is 1, and number of "single head" is N, meaning p(all heads)=1/(N+1). Thus if we want p=1/n, we toss (n-1) coin.

This can be probably optimized. For example, for n>3, we can call "Head" if either all heads or all tails drop, and we can call "Tail" if either single head or single tail drop. This will significantly reduce number of rerolls. It cant be used for n=3, since with two coins, "single head" is same case as "single tail".

But solving this for arbitrary p would be harder, and I doubt it can be solved for ANY p.
lostdummy
Daedalian Member

esme
^^^^-- is female! Get the pronouns right

Posted: Fri Mar 22, 2013 3:32 pm    Post subject: 26

 Trojan Horse wrote: Because I think I found a proof for it. My first attempts were with p rational: I first tried p=2/3. I thought it would be a cinch. Then an issue arose that I hadn't expected. The issue was so pervasive that it seemed to preclude p from being rational at all. So I tried to prove that p can't be rational, and I think I've succeeded. To be more precise, here's what I claim: Say you are going to use a (possibly unfair) coin to choose between n alternatives, and you want each alternative to be chosen exactly 1/n of the time. Assume that 1. the probability, p, of getting heads must be rational, and 2. the overall protocol must have a finite upper bound for the number of required coin tosses. This is only possible if the coin is fair, and n is a power of 2. Due to laziness and a desire to give you guys a challenge (but mostly laziness), I won't post the proof right now.

Ok, I would do it like this:

Lemma 1: p has to be of the form 1/a for some integer a.
(proof uses basic properties of integer polynomials)

Lemma 2: a equals 2, that is, the coin has to be fair.
(proof uses symmetry for q=1-p)

Lemma 3: With a fair coin, we succeed exactly for n a power of two.
(proof uses p=1-p and basic properties of fractions)

Proof of Lemma 1:
We can assume that we always toss up to the finite upper bound N (and possibly disregard some of the last tosses). So, we have to partition the various events with probabilities of the form p^k*(1-p)^(N-k) into sets that have total probability 1/n.

At least one of these parts does not contain the single event of proba (1-p)^N, so the sum is a polynomial in p with integer coefficients without constant term that equals 1/n.
Multiplying through with n, we can use the fact that any rational root of a polynomial with integer coefficients is a divisor of the constant term divided by a divisor of the leading coefficient.

Since the constant term is -1, we have shown that p is of the form 1/a for some integer a.
Q.E.D

Proof of Lemma 2:
The probability q=1-p fulfills the conditions of Lemma 1, so (a-1)/a is also of the form 1/b. Since (a-1) and a are relatively prime and a is positive, this implies a=2.
Q.E.D.

Proof of Lemma 3:
All events have the same probability (1/2)^N.
So, any set in the partition has a total probability of c/2^N which is always a fraction with denominator a power of two.
So, n has to be a power of two.

On the other hand, it is trivial to get powers of two with a fair coin, just toss it k times for n=2^k and attribute one full sequence to each player.
Q.E.D

How often do you have to toss a coin of *unknown* fairness to distinguish fairly between n players? (This is the real-life situation, btw. Coins are not fair, I seem to recall that it is especially egregious to spin a penny on the table.)
_________________
Mundus vult decipi, ergo decipiatur.

Last edited by esme on Fri Mar 22, 2013 3:51 pm; edited 1 time in total
bonanova
Daedalian Member

 Posted: Fri Mar 22, 2013 3:41 pm    Post subject: 27 My approach was this. Write the fractional binary expansion of p with coin tosses. H = 1, say, and T = 0. As soon as there is disagreement, the selection has been made. _________________ Vidi, vici, veni.
esme
^^^^-- is female! Get the pronouns right

 Posted: Fri Mar 22, 2013 3:53 pm    Post subject: 28 @bonanova: And how do you know that your approach has the fewest flips?_________________Mundus vult decipi, ergo decipiatur.
bonanova
Daedalian Member

Posted: Fri Mar 22, 2013 4:32 pm    Post subject: 29

 esme wrote: how do you know that your approach has the fewest flips?

I could use Chomsky's weak "It seems to me ... " but I'll let someone else say that.

p is described, generally and precisely by its binary representation.
A flip of a coin makes exactly a binary decision.

The method inspects p's binary representation digit by digit, as it must, using all the information contained in the outcome of a toss. Is the next digit 1? Is it zero? It inspects them in decreasing order of importance, so that as soon as you get H for a 0 (choose 1-p) or a T for a 1 (choose p), you are finished, and the remaining digits are of no consequence.

n tosses are required with probability 2 -n.

p can be arbitrary, and depending on p a single toss might suffice.

Could there be a more efficient method? (That's not a proof.)
_________________
Vidi, vici, veni.
esme
^^^^-- is female! Get the pronouns right

 Posted: Fri Mar 22, 2013 4:39 pm    Post subject: 30 Well, it is definitely not the most efficient method to simulate a fair coin (or any power of two)._________________Mundus vult decipi, ergo decipiatur.
bonanova
Daedalian Member

 Posted: Fri Mar 22, 2013 6:56 pm    Post subject: 31 Right. And perhaps by extension any rational. But how better could you discern probability regions bounded by 0, 1/pi, 1/e and 1?_________________ Vidi, vici, veni.
lostdummy
Daedalian Member

Posted: Fri Mar 22, 2013 7:03 pm    Post subject: 32

 bonanova wrote: My approach was this. Write the fractional binary expansion of p with coin tosses. H = 1, say, and T = 0. As soon as there is disagreement, the selection has been made.

Which problem from above are you solving here? Getting fair toss from unfair coin? Or selecting one out of n players with unfair coin? ;p

And can you give example of your solution, for example for p=1/3?
Thok
Oh, foe, the cursed teeth!

Posted: Fri Mar 22, 2013 8:55 pm    Post subject: 33

 esme wrote: Exercise for the reader: How often do you have to toss a coin of *unknown* fairness to distinguish fairly between n players? (This is the real-life situation, btw. Coins are not fair, I seem to recall that it is especially egregious to spin a penny on the table.)

You can always turn an unfair coin into a perfectly fair coin by the following process:

a. Flip the coin twice
b. Treat HT as heads and TH as tails
c. Reroll on HH or TT.

This requires (ln(N)/ln2)/P(H)P(T) coin flips on average to fairly pick from N people, but doesn't require you to know anything about the coin (except that P(H) is not 0 or 1, but in that case nothing will work).
bonanova
Daedalian Member

 Posted: Fri Mar 22, 2013 9:05 pm    Post subject: 34 Neither really. My post 20 stated a new problem: using a fair coin to simulate an arbitrarily biased one. In binary, 1/3 is .010101010101010101010.... Flip an unbiased coin, and associate say H with 1 and T with 0. A flip sequence that evaluates to a smaller value chooses the p case. A larger value chooses the 1-p case. First flip is T, it matches 0 so flip again. Second flip is H, it matches 1 so flip again. Third flip is H, it does not match 0 so you're done. THH evaluates to .011, larger than p, so you've chosen the 1-p case. First flip is H, evaluates to .1, larger than p, you've chosen 1-p case. First two flips are TT, evaluates to .00, smaller than p, you've chosen the p case. And of course you can divide [0, 1] arbitrarily into multiple intervals whose widths give arbitrary handicaps to multiple players._________________ Vidi, vici, veni.
bonanova
Daedalian Member

 Posted: Fri Mar 22, 2013 9:24 pm    Post subject: 35 So, who gets a free dinner? Have everyone write down a number in [0, 1]. Convert to binary and start flipping. Each person's interval starts at his number and extends down to next lowest. If the flip sequence ends up in the top interval, above the highest number chosen, everyone buys his own._________________ Vidi, vici, veni.
lostdummy
Daedalian Member

Posted: Sat Mar 23, 2013 12:54 pm    Post subject: 36

 bonanova wrote: Neither really. My post 20 stated a new problem: using a fair coin to simulate an arbitrarily biased one.

Ah, I see now ;p

That is probably optimal in number of coin tosses, since it is easy to see you need exactly 2 coin tosses on average to determine result. Basically, you stop when random toss bit is different from p binary fraction bit, and chance for that to happen on each toss is 1/2, so on average it will happen after only 2 tosses.

But it has small error margin, meaning you will not get exactly probability "p", because for cases when randomly generated number match exactly p, you will have to stop after some number of bits. Although it should be small error margin, around 1/2^(n+1), and also it does not differ from "toss again" solutions above, since those also have chance to never finish.

And since it works for any p, and for any p it has average 2 coin toss, it does look like optimal solution to select unfair P from fair coin.
lostdummy
Daedalian Member

Posted: Sat Mar 23, 2013 2:02 pm    Post subject: 37

 bonanova wrote: So, who gets a free dinner? Have everyone write down a number in [0, 1]. Convert to binary and start flipping. Each person's interval starts at his number and extends down to next lowest. If the flip sequence ends up in the top interval, above the highest number chosen, everyone buys his own.

While this method looks like optimal to select one value of 'unfair' p, it does NOT look optimal to select from range, like in above example "select one from N persons"

If my calculations are correct, you will need 2 tosses on average for 2 persons, 3 tosses for 3 persons, 4 tosses for 5 persons, 5 tosses for 9 persons etc...

Some formula for average needed number of tosses, nAvg(n) :
L = FLOOR(ln2(n-1))
nAvg(n) = (L+2)+(n-2^L-1)/2^L

When you compare average tosses for 5 persons (4.00), it is more than we had in solution to above random.org, with 3.6 tosses only needed.

I believe reason is that here it is not possible so easy to implement that "grouping" optimization.
bonanova
Daedalian Member

Posted: Sun Mar 24, 2013 12:15 am    Post subject: 38

 lostdummy wrote: you will not get exactly probability "p", because for cases when randomly generated number match exactly p, you will have to stop after some number of bits.

Help me understand "randomly generated number" or how having to stop when bits don't match removes exactness. (excluding 2 -n cases)

My own initial doubt of this method was that by stopping at a mismatch meant I hadn't exactly represented the target probability. But that's not the goal. You stop as soon as you know you have exceeded, or fallen short of, a number that exactly represents the target probability. That is, you divide [0, 1] into regions that have exact boundaries and stop flipping as soon as you are certain which region you have reached. A dart that hits a region of a dartboard does not have to hit the boundary of that region. Nevertheless it hits that region with a probability that is exactly determined by the placement of that boundary.

Is it not the case that the 2 -n cases (in which the binary p has infinite trailing zeros) hit boundaries, and all other cases hit regions whose boundaries are not describable by a finite number of coin tosses.

Or do you mean something different?
_________________
Vidi, vici, veni.
bonanova
Daedalian Member

Posted: Sun Mar 24, 2013 12:28 am    Post subject: 39

 lostdummy wrote: While this method looks like optimal to select one value of 'unfair' p, it does NOT look optimal to select from range, like in above example "select one from N persons"

I agree. But add optimal also for multiple 'unfair' p's, as in the case of arbitrarily handicapping multiple participants. Although it's not clear when you would want to do this. If you divide [0, 1] into three regions bounded by 1/pi and 1/e, what other method would work?

But picking fairly among several outcomes (e.g. the above boundaries are 1/3 and 2/3) can be done more efficiently than the mismatched digit method. And this is after all the main topic of this thread.
_________________
Vidi, vici, veni.
lostdummy
Daedalian Member

Posted: Sun Mar 24, 2013 2:53 pm    Post subject: 40

 bonanova wrote: Help me understand "randomly generated number" or how having to stop when bits don't match removes exactness. (excluding 2 -n cases)

That was not about stopping when bits mismatch, but stopping when they match ... and yes, it happens only in 2 -n cases, and is not different from having to stop in such rare cases in other solutions proposed here (including mine) where re-rolls could in theory be infinite. So that is not big negative side of your method, I just mentioned it to show that your method have same 'weakness' as other methods.

BUT on issue of "optimal", I just remembered cases where even for single 'p', ie for simulating single unfair coin with fair coins, your method can be less than optimal.

For example, p=1/4. With other methods ( like in my post #25), we can get average number of flips to be only 1.5 ( let TT be "Tail", anything else "Head". If we get H first time, we can stop, so we need one flip for HH, HT, and two flips for TH, TT ... making average number of flips 1.5).

And 1.5 is better than 2.0 which is average needed number of flips for your method, regardless of p.

- it can work for any p, while my method in #25 post works only for fractional A/B
- it is easier to define, since it does not need 'grouping' that is specific for different p and N
- it probably gives better result (2.0 average flips) than other methods for more complex cases

But unfortunately it is not optimal solution for all cases, only for some. I wonder if there exists some method that is optimal for any p.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAmbAnonymousbonanovaesmegroza528jadesmarlostdummyScurraThokTrojan HorseZag Oldest FirstNewest First
 All times are GMTGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum