BrainDen.com - Brain Teasers
• 0

# Random Number API - Part 2...

## Question

You must solve before reading this one.

Ok so we saw that a uniform binary number generator (fair coin) isn't good for us when we want to generate stuff with probability 1/n where n isn't a power of 2.

So instead of a [0.5 , 0.5] generator, I am allowing you to customize your own random generator, namely you choose some k>1 and give me {p1...pk} and I will give you a random number generator that generates numbers between 1 and k with those probabilities.

What kind of generator do you choose and how will you use it to generate numbers with probability 1/n?

(note again I ask that your algorithm guarantee not to run for ever, as in for every n exists M such that you use the customized generator at most M times)

## Recommended Posts

• 0

so here would be my probabilities.

(1/2,1/3,1/10,1/15)

the binary case would be easy.

if 1 for my four numbers, give 0. else give 1.

the ternary case gets a bit more challenging.

generate twice.

if you get the combo

1,1 or 1,3 or 1,4 return 0. if 2,1 or 1,2, return 1. else return 2.

can it be indefinitely extended???

Edited by phil1882
##### Share on other sites

• 0

Suppose we have an algorithm that calculates rand(n) using generator based on probabilities {p

1, ..., pk}
Consider a diagram of the algorithm in a form of decision tree.
Each time we use the generator, the algorithm forks into k branches (it is possible for some pi and pj to produce identical branches).
Forking corresponds to a node in the tree of the diagram and each edge is labeled with corresponding pi.
The probability of each leaf is a product of pi's assigned to edges that form path from root to given leaf.
Probability of any subset of leaves is a sum of such products.

Obviously there exists such prime number p, that no pi has it's denominator divisible by p.
No matter how we combine pi's using addition and/or multiplication, there is no way to arrive at 1/p.
Therefore it is not possible for rand(p) to return values with probability 1/p.

##### Share on other sites

• 0

okay so clearly none of my denominators are divisible by 7.

so let's say for the sake of argument, i could generate any rng that's a power of 2, 3, 5, or a combination thereof.

(so 6, 12, 15, 25, 27, 32 etc.)

could i generate a rng(7)? or a rng(49)?

i'm pretty sure the answer is no.

1/3 is my only infinite decimal expansion, and there's no conceivable way to combine 1/3 with 1/2 and 1/5 to get 1/7;

without going to infinity. dang! nicely done wiztar.

##### Share on other sites

• 0

Suppose we have an algorithm that calculates rand(n) using generator based on probabilities {p

1, ..., pk}

Consider a diagram of the algorithm in a form of decision tree.

Each time we use the generator, the algorithm forks into k branches (it is possible for some pi and pj to produce identical branches).

Forking corresponds to a node in the tree of the diagram and each edge is labeled with corresponding pi.

The probability of each leaf is a product of pi's assigned to edges that form path from root to given leaf.

Probability of any subset of leaves is a sum of such products.

Obviously there exists such prime number p, that no pi has it's denominator divisible by p.

No matter how we combine pi's using addition and/or multiplication, there is no way to arrive at 1/p.

Therefore it is not possible for rand(p) to return values with probability 1/p.

You're on to something but the proof isn't complete.

The limit M(n) is is different for each n, so for example it could be that for rng(3) you use your generator just once and for rng(7) you need it 1023 times.

I can prove it in the case p

1...pn are all rational, if we assume they're rational then we can write them as r1/q1...rn/qn, now, let Q=q1*...*qn be the product of all the q's, we can see that a generator that generates numbers in the set {1...Q} with probability 1/Q each is stronger that our generator because one could easily use it to mimic our generator (if it outputs a number in the range [1,r1] answer 1, if in the range [r1+1,r1+r2] answer 2...etc

But now it's easy to see that this generator has the same problem as the binary one, if you take any primary number that doesn't divide Q, or even take Q+1, there is no way you can generate something with exactly probability 1/(Q+1)

But this is only for rational numbers, does it apply for irrational numbers as well?

Edited by Anza Power
##### Share on other sites

• 0

hmmm! in an interesting puzzle. is there a finite set of irrational numbers you could use to get every whole number?

i would think not. but how to prove it?

let's say i wanted the fraction 1/2. if i take 1 / the square root of 5, the only way i could get 1/2 that i know of would be to use 1/2 - 1/sqrt(5) (or something longer, like 1/2 -1/sqrt(5) -1/cbrt(3381))

both numbers would be irrational, but then i run into the same problem as before, i can get 1/2, 1/3, etc, but there would be some fraction i couldn't get because i didn't do 1/p -1/sqrt(q) in my probabilities; where p is a large prime.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.