When you generate a Dungeons & Dragons character, you are particularly interested in the character’s best attributes, so you might like to know the distribution of the maximum attribute.
There are three ways to compute the distribution of a maximum:
Given a Pmf that represents the distribution for a single selection, you can generate random samples, find the maximum, and accumulate the distribution of simulated maxima.
Given two Pmfs, you can enumerate all possible pairs of values and compute the distribution of the maximum.
If we convert a Pmf to a Cdf, there is a simple and efficient algorithm for finding the Cdf of the maximum.
The code to simulate maxima is almost identical to the code for simulating sums:
def RandomMax(dists): total = max(dist.Random() for dist in dists) return total def SampleMax(dists, n): pmf = MakePmfFromList(RandomMax(dists) for i in xrange(n)) return pmf
All I did was replace “sum” with “max”. And the code for enumeration is almost identical, too:
def PmfMax(pmf1, pmf2): res = thinkbayes.Pmf() for v1, p1 in pmf1.Items(): for v2, p2 in pmf2.Items(): res.Incr(max(v1, v2), p1*p2) return res
In fact, you could generalize this function by taking the appropriate operator as a parameter.
The only problem with this algorithm is that if each Pmf has
m values, the run time is proportional to
m2. And if we
want the maximum of
k selections, it
takes time proportional to .
If we convert the Pmfs to Cdfs, we can do the ...