2

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!

martineau
  • 119,623
  • 25
  • 170
  • 301
Marco
  • 45
  • 1
  • 4
  • Not exactly sure what you're trying to do – wjk2a1 Jul 30 '16 at 16:11
  • Hi! I'm trying to generate a random number X which follow the distribution I described. What the problem requests is to choose X according to distribution Pr X ≥ k = 1/k – Marco Jul 30 '16 at 16:14
  • is this what you are looking for :http://stackoverflow.com/a/4266312/2348704 – bhaskarc Jul 30 '16 at 16:17
  • If that's a common type of distribution, try searching for its name & python—you may be able to find a third-party library that does it (or even if it's something built-in). – martineau Jul 30 '16 at 16:19
  • Is $k$ given as input? – wjk2a1 Jul 30 '16 at 16:21
  • Is `k` continuous? People commonly use letters i through n for integers (a holdover from FORTRAN). – pjs Jul 30 '16 at 16:36

2 Answers2

6

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.

Rory Daulton
  • 21,934
  • 6
  • 42
  • 50
2

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.

pjs
  • 18,696
  • 4
  • 27
  • 56
  • 1
    I fail to see how my math was wrong. I admit it was brief, showing only one step, but that was because I thought the rest was obvious to those knowing probability. You have motivated me to add more steps to my equalities, but nothing was changed. Do you agree that my current exposition is correct? (I still left out a few details, of course--I don't want to be pedantic.) – Rory Daulton Jul 30 '16 at 19:34
  • 1
    @RoryDaulton Your second line is premised on your assertion of what X should be, it doesn't follow from any fundamental rules of probability. The math works out from there because your assertion happens to be true, but that doesn't make the assertion valid a priori. By contrast, my derivation follows well-known rules of probability to end up at your asserted result. – pjs Jul 30 '16 at 20:28
  • 1
    Apparently, you mean that you derived the expression from the desired goal, while I showed that my expression satisfies the goal. We worked in opposite directions, but that does not make my math "invalid." For a good discussion on the differences between the two methods, see *How to Solve It* by George Polya. – Rory Daulton Jul 30 '16 at 22:14
  • Proof by lack of contradiction establishes correctness of your result, but doesn't show anybody how to get there other than by a leap of intuition. Deriving the result from first principles generalizes. – pjs Jul 30 '16 at 22:23