Random Number API - Part 2...

[Anza Power]

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 {p₁...p_k} 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)

[phil1882]

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 August 7, 2013 by phil1882

[witzar]

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

₁, ..., p_k}
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 p_i and p_j to produce identical branches).
Forking corresponds to a node in the tree of the diagram and each edge is labeled with corresponding p_i.
The probability of each leaf is a product of p_i'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 p_i has it's denominator divisible by p.
No matter how we combine p_i'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.

[phil1882]

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.

[Anza Power]

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

₁, ..., p_k}

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 p_i and p_j to produce identical branches).

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

The probability of each leaf is a product of p_i'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 p_i has it's denominator divisible by p.

No matter how we combine p_i'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

₁...p_n are all rational, if we assume they're rational then we can write them as r₁/q₁...r_n/q_n, now, let Q=q₁*...*q_n 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,r₁] answer 1, if in the range [r₁+1,r₁+r₂] 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 August 7, 2013 by Anza Power

[phil1882]

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.