• 0

Random Number API - Part 2...

Question

Posted · Report post

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)
0

Share this post


Link to post
Share on other sites

5 answers to this question

  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.