interesting problem, try it?

[coke]

Anybody want to try this problem?

 

I know the answer and how to do it, I'll tell you later.

 

Anyways...

You have a random number generator, that generates the numbers 1-5 randomly (equal probability of each).

 

You need to make a random number generator out of it that generates the numbers 1-7 randomly (equal probability of each).

 

How do you make it out of the first generator? For example, you can take a number from the first one, and run it through the first one 5 more times, and say if you get some answers tell the generator to start over again, etc.

[BigMoosie]

Your question is not specific enough as there are an infinite number of ways this can be done. Here is the first that comes to mind:

 

Run the 1st generator twice, if you get:

 

1,1 -> return 1

1,2 -> return 2

1,3 -> return 3

1,4 -> return 4

1,5 -> return 5

2,1 -> return 6

2,2 -> return 7

else -> try again

 

Each of these has equal probability, though it may take several iterations before it ends. Efficiency was not a requirement you provided.

[the tree]

I'm fairly sure there wouldn't be a simpler way to do it.

Obviously this would get a result quicker:

1,1 -> return 1
1,2 -> return 2
1,3 -> return 3
1,4 -> return 4
1,5 -> return 5
2,1 -> return 6
2,2 -> return 7

2,3 -> return 1
2,4 -> return 2
2,5 -> return 3
3,1 -> return 4
3,2 -> return 5
3,3 -> return 6
3,4 -> return 7

3,5 -> return 1
4,1 -> return 2
4,2 -> return 3
4,3 -> return 4
4,4 -> return 5
4,5 -> return 6
5,1 -> return 7

else -> try again.

Still horrendously ineffecient, though, and there's a [imath](4/25)^n[/imath] chance that it wont give you a result after [imath]n[/imath] attempts.

[Sisyphus]

You want efficiency? Cheat. Just have it run once and directly copy the results. Sure, you'll never get a 6 or 7, but if you hide the mechanism, then nobody can ever actually prove they weren't as likely as any other result. It will just quickly become a larger and larger statistical anomaly...

[SH3RL0CK]

How about running it seven times? Run a filter to determine which of these seven times resulted in the largest value.

 

For example, if run # 6 resulted in a 4 (for example) and all other runs were smaller (3 or less) then the answer is 6. Running it again, if the highest value was in run # 1, then the answer is 1. Repeat as desired. If there is a tie, simply do it again until there isn't a tie.

 

As the numbers 1 to 5 will be randomly selected, the highest value in runs# 1 to 7 should also be random. Essentially you are relying on the randomness of the occurance of the highest value, 1 to 5, within a specific set of seven runs to determine whether to pick 1 to 7 as your value.

[BigMoosie]

I'm fairly sure there wouldn't be a simpler way to do it.

 

I was not thinking simplicity, just computational efficiency, which yours of course improves upon.

 

If the bottleneck of the original random number generator is a heavy bottleneck (eg. using an external generator), then I would probably try to devise some system where 50 random numbers are generated and something like ~35 numbers 1-7 are extracted from the results (can't be bothered figuring out exactly how many) and stored in a stack for later use, the larger the stack the fewer the random numbers will need to be discarded.

Edited April 3, 2009 by BigMoosie

[the tree]

To not discard any numbers with what you originally posted, you'd need a power of five which is also a multiple of seven. Since five is prime, I don't think that'd happen.

---

Merged post follows:

Consecutive posts merged

On that note, I can't think of a way to use a d5 to generate a random bit fairly (without discarding data) - which would be the ideal solution.

Edited April 3, 2009 by the tree
Consecutive posts merged.

[BigMoosie]

I think there is an ideal solution where no random numbers are lost. It would involve running an algorithm which will produce a random number of random numbers in the range 0-6 (I'll start at zero to make the math nicer) and queue them up until when they are needed.

 

In the algorithm random numbers (0-4) are iteratively added to a stack. Each time one is added, the following check is made:

 

Let L be the length of the stack.

 

Let X be the base 5 number representation of the stack, eg: a stack of [2,4,0,3] = 2*125 + 4*25 + 3.

 

Is there a K such that [math]X < 7^K <= 5^L[/math]

?

 

If so we can break this loop. Now let Y be the base 7 number representation of X.

The digits of Y are our random numbers in the range of 0-6 that can be queued up for when needed (when they run out run this algorithm again).

 

I'm quite sure the loop will use a finite but arbitrarily large number of iterations, but am not sure how to prove it. And of course, using an arbitrary number of iterations is fine since it also outputs a correspondingly large number of 0-6 range numbers, hence nothing wasted.

 

In case it's hard to understand what I mean, my first post here would be what would happen on the second iteration.

Edited April 3, 2009 by BigMoosie

[coke]

Here's how a computer would create any random number generator from a 2 number generator (and the 2 number generator is mechanical in the processor, i guess)

 

Because I'm sure most of you know thats how numbers are written in binary in the first place... i.e. 7 is 111. or 00000111, same thing.

 

0,0,0 -> try again
0,0,1 -> return 1
0,1,0 -> return 2
0,1,1 -> return 3
1,0,0 -> return 4
1,0,1 -> return 5
1,1,0 -> return 6
1,1,1 -> return 7

 

That would have efficiency of 8/125, or 6.4%.... after 3 runs.

 

I guess the tree's method is the best possible efficiency, it gets 84% chance, as he said, after 2 runs.

 

And 2 runs is the minimum, seeing as 7 > 5^1, but 7 < 5^2

 

Sisyphus... if you are going to try to hide a failed mechanism, at least make it appear functional! say sum of first attempt + second attempt, throw out 8-10.

Edited April 7, 2009 by coke

[BigMoosie]

Here's how a computer would create any random number generator from a 2 number generator (and the 2 number generator is mechanical in the processor, i guess)

 

Not many computers use that technique, only ones hooked up to special hardware, like a half silvered mirror + laser aparatus, mostly for scientific research.

 

Most computers instead use the computer's internal clock to create Pseudo-random numbers.

 

Sisyphus... if you are going to try to hide a failed mechanism, at least make it appear functional! say sum of first attempt + second attempt, throw out 8-10.

 

But then you would never get '1', if you want to cheat I would suppose this would be hard to notice:

 

var count = random5();

function random7()
{
 var r1 = random5();
 var r2 = random5();

 count++;

 return (r1+r2+count)%7 + 1;
}

Edited April 7, 2009 by BigMoosie

[the tree]

Well, the internal clock for the initial seed - usually just the previous numbers after that. If a number is random within a sufficiently large range - then taking it's value mod 7, would give a small bias - which is essentially what mine a Moosie's suggestions were - with the bias chopped off at the expense of inefficiency. If your willing to cheat then (r₁.r₂.r₃ mod 7) would only get noticed on a large scale, or if someone were looking for suspicious data.

[D H]

Well, the internal clock for the initial seed - usually just the previous numbers after that.

How a pseudo random number generator (PRNG) is initialized is up to the caller. The library interface simply calls for an integer (or set of integers, depending on which PRNG is used). In particular, most PRNGs do not provide an option to set the PRNG from the system clock. There is nothing to stop the caller from using the clock, however.

 

If a number is random within a sufficiently large range - then taking it's value mod 7

This is a bad idea, and with some PRNGs this is a notoriously bad idea. The low-order bits are not nearly as random as the high order bits. In one infamously bad implementation the low order bit alternated between zero and one on subsequent calls. Using the mod N approach with N=2 would yield a sequence 0,1,0,1,0,1,... --- not very random at all. A better approach is to normalize the PRNG output to a floating point number between 0 and 1, multiply by N, and take the integral part of the result.

[the tree]

I meant that for the sake of cheating - not for the sake of producing a genuinely random output.