[Guest]

You have a function that can generate a random value, it only generate True or False (1 & 0) with equal probability (50/50), now it is easy to use that function to pick out a random number out of a group of numbers if that group is one of the powers of 2, but what if it wasn't?

Use the function to make a function that picks out a random number out of 7 numbers with equal probability, how can this be done?

[bonanova]

Add an 8th number to the group and select one randomly.

If you pick the 8th number, ignore the result and select again.

[Guest]

Assign a number of 0 through 6 to the seven choices. Perform the function 6 times, add the results, and subtract 5 from the total. Old school D&D "I only have a penny and no dice" way of rolling - ((choices-1)d2)-(choices-2).

Edited September 22, 2010 by HellforgedX

[EventHorizon]

Add an 8th number to the group and select one randomly.

If you pick the 8th number, ignore the result and select again.

Exactly what I was thinking, but here's a follow-up question (which isn't that much harder than the original). Is there a solution that is guaranteed to pick an option out of 7 with equal probability within a specified number of uses of the random number generator? If not, prove it.

[EventHorizon]

Assign a number of 0 through 6 to the seven choices. Perform the function 6 times, add the results, and subtract 5 from the total. Old school D&D "I only have a penny and no dice" way of rolling - ((choices-1)d2)-(choices-2).

Interesting approach, but it doesn't choose with equal probability.

Let there be 3 choices, so you flip the coin 2 times.

Here are the probabilities:

2:1/4

3:1/2

4:1/4

Subtract 1 gives

1:1/4

2:1/2

3:1/4

You are picking from a binomial distribution, which favors the middle options.

Edited September 22, 2010 by EventHorizon

[bonanova]

Exactly what I was thinking, but here's a follow-up question (which isn't that much harder than the original). Is there a solution that is guaranteed to pick an option out of 7 with equal probability within a specified number of uses of the random number generator? If not, prove it.

Write the number of options in binary. apply the rng to each of the digits.

There's a problem with the most significant digit, I think.

Edit: Problem is if rng returns 0 each time.

Would be interesting to simulate this. [no need]

Edited September 28, 2010 by bonanova
Make sense of the method's fault

[Guest]

one possibility is to run the function 3 times until you get a Boolean value between 1-7. (if you get all false, run 3 times again.)

another possibility it to run the function 7 times, record the indexes that come up true, and run that many times again, until you only have one true index. (if all ever get eliminated, start over.)

[bonanova]

one possibility is to run the function 3 times until you get a Boolean value between 1-7. (if you get all false, run 3 times again.)

another possibility it to run the function 7 times, record the indexes that come up true, and run that many times again, until you only have one true index. (if all ever get eliminated, start over.)

Similar to my second suggestion, Does this give all numbers an equal chance? I haven't though through it.

[Guest]

as my second solution, flip 7 times, record the indexes that come up true. add the indexes and mod 7.

does this work??!!

[EventHorizon]

As for your answers to the original problem, I believe they both will work.

as my second solution, flip 7 times, record the indexes that come up true. add the indexes and mod 7.

does this work??!!

As for your solution for a specified number of coin flips: it was a good attempt, but...

1 flip outcome totals

0:1

1:1

2 flips

0:1

1:1

2:1

3:1

3 flips (now just given as a list where the first index is 0)

1,1,1,2,1,1,1

4 flips

1,1,1,2,2,2,2,2,1,1,1

5 flips

1,1,1,2,2,3,3,3,3,3,3,2,2,1,1,1

6 flips

1,1,1,2,2,3,4,4,4,5,5,5,5,4,4,4,3,2,2,1,1,1

I won't do the 7th flip because adding 7 will not change the mod 7 result.

Totals after mod 7

0:1+4+4+1 = 10

1:1+4+4 = 9

2:1+5+3 = 9

3:2+5+2 = 9

4:2+5+2 = 9

5:3+5+1 = 9

6:4+4+1 = 9

As you see, impressively close, but 0 is favored slightly.

[Guest]

I think bonanova's and phillip's first solutions are right.

Each number has probability 1/8

P[0] = 1/8

P[1] = 1/8

P[2] = 1/8

P[3] = 1/8

P[4] = 1/8

P[5] = 1/8

P[6] = 1/8

P[7] = 1/8

Given that the answer is not zero,

! = not

P[1|!0]*P[!0] = P[1 and !0] = 1/8

P[!0] = 7/8

P[1|!0] = (1/8)/(7/8) = 1/7

Altogether,

P[1|!0] = (1/8)/(7/8) = 1/7

P[2|!0] = (1/8)/(7/8) = 1/7

P[3|!0] = (1/8)/(7/8) = 1/7

P[4|!0] = (1/8)/(7/8) = 1/7

P[5|!0] = (1/8)/(7/8) = 1/7

P[6|!0] = (1/8)/(7/8) = 1/7

P[7|!0] = (1/8)/(7/8) = 1/7

[Guest]

Exactly what I was thinking, but here's a follow-up question (which isn't that much harder than the original). Is there a solution that is guaranteed to pick an option out of 7 with equal probability within a specified number of uses of the random number generator? If not, prove it.

I don't know about guarantee, but here's a solution that's pretty close:

Flip your coin 100 times, count the number of heads. Assign that value to N1.

Flip your coin 100 times, count the number of heads. Assign that value to N2.

Repeat for N3, N4, N5, N6.

The value with the most heads wins. The only problem is if you get a tie. Otherwise, you've flipped exactly 700 times and almost guaranteed yourself an answer. Likelihood of getting a tie decreases as the number of flips increases, so if you're willing to accept infinity flips, then probability of a tie = 0.

[EventHorizon]

I don't know about guarantee, but here's a solution that's pretty close:

Flip your coin 100 times, count the number of heads. Assign that value to N1.

Flip your coin 100 times, count the number of heads. Assign that value to N2.

Repeat for N3, N4, N5, N6.

The value with the most heads wins. The only problem is if you get a tie. Otherwise, you've flipped exactly 700 times and almost guaranteed yourself an answer. Likelihood of getting a tie decreases as the number of flips increases, so if you're willing to accept infinity flips, then probability of a tie = 0.

That's a nice variable-time solution, but I am looking for exactly equal... or a proof that no such solution exists. Also, infinity is not acceptable (or this question would be no different that the first).

[phaze]

Cant be guaranteed as no power of 2 is divisible by 7 (all powers of 2 are divisible by 2 or other powers of 2)

Edit:

Unless you accept fractions in which case throw the coin at least 3 times and divide the answer by the number of times u threw the coin and multiply by 7

Edited September 23, 2010 by phaze

[Guest]

flip the coin 7 times. let each result represent a binary fraction. (ie. 1/2, 1/4, 1/8 etc.)

then multiply by 7. round to the closest integer.

[plainglazed]

Take each datum and use the function on it. If the function returns a 1, that number proceeds to the next round. Repeat until you have a random(?) winner. Or maybe better; take each of the seven individually and use the function on it alone returning 1 or 0, repeat, keep a running total until you have one data point that has a unique highest total. dont know that this would be valid or even if it's already been said as I dont understand alot of what's been proffered here. am just a word guy so please dont go all Monty Hall on me...

[Guest]

flip the coin 7 times. let each result represent a binary fraction. (ie. 1/2, 1/4, 1/8 etc.)

then multiply by 7. round to the closest integer.

In that case you have 8 possible outcomes (the first step will give out a fractions from 0 to 1 so afterward it's from 0 to 7) and even if you do it for 6 or any other number, the two numbers on the edges (0 and 6) will have half the probability of the other numbers cause they'll be chosen only if the result falls in an area half of that of the others...

Well actually I came to the conclusion that it's impossible, the reason is that no matter how many times you use that function, it'll always give out a 2ⁿ number of paths, for instance for 2 uses there are 00 01 10 11, to give each number the same probability you have to give it the same amount of paths, and if the number of paths isn't divisible by the number of figures then either a few figures will be favored or you'll just have to assign a "reset" result and hope you won't be randomizing forever...

The best way IMO (in a human's eye, not mathematician) is to do it in rounds where each round everyone uses the function and if they get 0 they're eliminated until only one is left, if all are eliminated in one round you restart that round (not the whole game)

[EventHorizon]

It is impossible to guarantee equal probability without allowing infinite coin flips.

They are also correct that the only number of options for which you can guarantee equal probability are powers of 2 (in the case of a coin flip).

It gets a little more interesting when using a standard 6-sided die. The number of options for which you can have equal probability are those numbers that only have 2's and 3's as prime factors (1,2,3,4,6,8,9,etc). Obviously, this generalizes based on the prime factors for the number of outcomes of the random number generator.

[superprismatic]

It is impossible to guarantee equal probability without allowing infinite coin flips.

They are also correct that the only number of options for which you can guarantee equal probability are powers of 2 (in the case of a coin flip).

It gets a little more interesting when using a standard 6-sided die. The number of options for which you can have equal probability are those numbers that only have 2's and 3's as prime factors (1,2,3,4,6,8,9,etc). Obviously, this generalizes based on the prime factors for the number of outcomes of the random number generator.

Can you supply a proof of your first claim about the impossibility of guaranteeing equal probability without allowing infinite coin flips?

I believe it, but I can only prove it for the case where only N flips are used (for some particular N). The complication of allowing a cascade of

differing number of flips eludes me.

[Guest]

You have a function that can generate a random value, it only generate True or False (1 & 0) with equal probability (50/50), now it is easy to use that function to pick out a random number out of a group of numbers if that group is one of the powers of 2, but what if it wasn't?

Use the function to make a function that picks out a random number out of 7 numbers with equal probability, how can this be done?

Iv gotta agree with philip1882 (post 8 I think)

As we know already, 2 does not divide 7 so easily.

If it an algorithm, what could a couple more steps do to harm.

I thought the same as philip when I read this, to get 3 random 0/1 values and turn them into numbers...

000 = 1

001 = 2

010 = 3

100 = 4

011 = 5

101 = 6

110 = 7

111 = Do another set of 3 random vaules until a number from 1-7 appears

Of course we have the problem that '111' may appear continously, but lets just hope that there is such a minute chance of that happening that is = 0 (1-0.99999999... - 0)

[EventHorizon]

Can you supply a proof of your first claim about the impossibility of guaranteeing equal probability without allowing infinite coin flips?

I believe it, but I can only prove it for the case where only N flips are used (for some particular N). The complication of allowing a cascade of

differing number of flips eludes me.

I'll approach it two ways...first by modifying the decision process, and second by analyzing the decimal expansions.

1) Let N be the maximum number of coin flips a decision process D uses to choose between 7 options.

Create decision process D₂ such that it does what D does unless D would stop before N flips. In this case, flip the coin until N flips have been performed, ignore the flips that D would not have flipped, and return the result D would have chosen.

Each sequence of N flips of the coin have the same probability of occurring, and each sequence is mapped to a choice of a given option by D₂. There are 2^N sequences of flip outcomes. Since 2^N only has prime factors of 2, it cannot be divisible by 7. Therefore one option must be more likely than another of occurring.

2) The decimal expansion for any value 1/2^N uses N decimal places after the decimal point (always ends in 5 (an odd number), so dividing by 2 takes 1 more decimal place to represent). If a decision process uses at most N flips, the sum of the probability for all occurrences where the decision process results in a certain option (each having a probability of 1/2^k for some k) can have at most N decimal places. Since 1/7 is a repeating fraction, it cannot be represented by this sum.

[phaze]

flip the coin 7 times. let each result represent a binary fraction. (ie. 1/2, 1/4, 1/8 etc.)

then multiply by 7. round to the closest integer.

I realize Anza has already said something but you could also think of it as it is no longer evenly distributed after rounding. You also only need to flip coin 3 times to get a number larger than 7 (8). Flipping 7 times will get a random number between 1 - 127 which is better but still not 100% accurate after rounding. If we could convince Event Horizon to accept fractions however it would remain evenly distributed.

7/128 2*7/128 3*7/128 ....

[bonanova]

Is there a solution that is guaranteed to pick an option out of 7 with equal probability within a specified number of uses of the random number generator?

Here's the pseudo code, with built-in counter to verify the claim.

.

1. Cnt=0
2. r1=rng[Cnt+]
3. r2=rng[Cnt+]
4. r3=rng[Cnt+]
5. if r1=r2=r3=0 go to 1.
6. Result= binary_to_int {r1 r2 r3}, Cnt
   .

Well, someone had to try it ...

[EventHorizon]

Here's the pseudo code, with built-in counter to verify the claim.

.

1. Cnt=0
2. r1=rng[Cnt+]
3. r2=rng[Cnt+]
4. r3=rng[Cnt+]
5. if r1=r2=r3=0 go to 1.
6. Result= binary_to_int {r1 r2 r3}, Cnt
   .

Well, someone had to try it ...

If you keep getting 0's, the process can take an indefinite number of coin flips. Going to step 1 resets the counter, but doesn't undo the coin flips.

I'm sure you know all that, but I thought I'd post so people don't think that method will always terminate within a certain finite number of coin flips.

[bonanova]

It was a joke.

I thought branching to the counter reset on failure was ... almost subtle.

This bit of silliness reminds me of an NCAA basketball tournament office pool a few years ago.

The $5 entry fee was due end of business day to an office in another building.

I couldn't get there in time, so I faxed him a $5 bill.

I amuse myself, at least, sometimes ...

[Guest]

It was a joke.

I thought branching to the counter reset on failure was ... almost subtle.

This bit of silliness reminds me of an NCAA basketball tournament office pool a few years ago.

The $5 entry fee was due end of business day to an office in another building.

I couldn't get there in time, so I faxed him a $5 bill.

...Nice...XD XD