Discrete probability distribution with a given maximum

Question

I have to generate a random discrete probability distribution of n elements with a given maximum value.

I know how to create a classic one but I have no clues how to generate a random discrete probability distribution of n elements who respect max(distribution) = p. By that I mean that the highest probability of the distribution must be p in [0;1[.

Any idea ?

Let random function returns values in interval [0; 1]. You can use a formula values[i] = expectedValue + 2 * p * (random() - 1); — Mark Shevchenko
What do you mean by max(distribution) = p? With discrete probability distributions you have two sets of numbers -- the numbers that occur (e.g. 1,2,3,4,5,6 when rolling a die) and the probability of those numbers occurring (e.g. the number 1/6). It is unclear what you intend. — John Coleman
@MarkShevchenko What is expectedValuein your comment ? And is preally in the distribution ? — elnabo
@JohnColeman by max(distribution)=p I mean that the highest probability in the distribution must be equal to p in [0;1[ — elnabo
@elnabo -- that is of course trivial (let p(0) = p, pick n large enough so that (1-p)/(n-1) < p, and assign the probability (1-p)/(n-1) to the elements 2,3,...,n.) Since you probably are not looking for an answer like that I suspect that there are some constraints you are not specifying. — John Coleman

John Coleman John Coleman · Accepted Answer · 2015-07-03T15:10:13

You could use a hit and miss approach (often used in probability simulations to randomly choose elements which satisfy certain constraints). The performance is acceptable unless np is too close to 1. Here is a Python implementation, which should be easy enough to translate to other languages:

from random import random

def makeDist(n,p):
    #assumes p*n > 1
    miss = True
    while miss:
        x = [p]
        rest = [random() for i in range(1,n)]
        total = sum(rest)
        rest = [x*(1-p)/total for x in rest]
        if all(x < p for x in rest):
            x.extend(rest)
            miss = False #we have a hit!
    return x

Typical output:

>>> dist = makeDist(6,0.2)
>>> dist
[0.2, 0.08986510724051082, 0.18690143846768711, 0.19758176720598397, 0.19299989610231708, 0.13265179098350102]
>>> max(dist)
0.2
>>> sum(dist)
1.0
>>> makeDist(3,0.35)
[0.35, 0.31154704906869274, 0.33845295093130723]
>>>

Discrete probability distribution with a given maximum

1 Answers