CODEWITHSUNDEEP
pythonrandomprobability
Marco
Marco

Reputation: 45

Random Number following a certain distribution

I'm stuck with a problem. I have to implement an algorithm in python which needs a random number X such as Pr[X ≥ k] = 1/k. I don't know if already exists a distribution which can give me this exact value or if there is a way to implement this random generator using the simple random python library. Is there a way to do this? Thank you in advance for your help!

Upvotes: 2

Views: 617

Answers (2)

pjs
pjs

Reputation: 19855

Rory ended up at the correct answer, but his math justifying it is not constructive—it doesn't show how to get to the answer, it only shows that his assertion is correct. The following uses basic rules of probability to derive the answer.

Pr{X ≥ k} = 1 - Pr{X < k}

If X is a continuous random variable,

Pr{X < k} = Pr{X ≤ k}

The right hand side is the definition of the cumulative distribution function FX(k), so

Pr{X ≥ k} = 1 - F(k) = 1/k
F(k) = 1 - 1/k

Then by the inversion theorem we can set that equal to U, a uniform(0,1) RV, and solve for k:

U = 1 - 1/k
1 - U = 1/k
k = 1 / (1 - U)

Use your random number generator for U, and you're done. As Rory pointed out this is only valid for k ≥ 1, otherwise it would drive the CDF out of bounds.

Upvotes: 2

Rory Daulton
Rory Daulton

Reputation: 22544

The easiest attempt is to make

X = 1.0 / random.random()

However, random.random() can have a value of zero, so this may result in a divide-by-zero error. The value can never be 1.0, according to the documentation, so use

X = 1.0 / (1.0 - random.random())

For this distribution,

Pr[X ≥ k] = Pr[0 < 1/X ≤ 1/k]

= Pr[0 < 1 - random.random() ≤ 1/k]

= Pr[1 - 1/k ≤ random.random() < 1]

= 1 - (1 - 1/k) {since random() is uniform in [0,1) and [1-1/k, 1) is a subinterval}

= 1/k

(I wish I could use MathJax here!) Of course, all this assumes that k ≥ 1, since your condition makes no sense otherwise. I also assumed that X was to be a continuous random variable, from 1 to plus infinity. If X is to be an positive integer (thus k is also a positive integer), just take the floor of the formula I gave.

Upvotes: 6

Related Questions