Probability Problem

[Tim Peters]

[Alex Martelli]
>> ...
>> You can compute the requested answer exactly with no random number
>> generation whatsoever: compute the probability of each result from
>> 0 to 1000, then sum the probabilities of entries that are exactly 390
>> apart.

[Elliot Temple]
> That was the plan, but how do I get the probability of any given
> result?

As the link you gave suggests, the number of ways to get a given sum s
is the coefficient of x**s in (1 + x + x**2 + ... +x**100)**10. 
Divide that by 101**10 to compute the probability of getting sum s.

> (in a reasonable amount of time)
>
> BTW I'm not in a math course, just curious.

Computing exact results is probably too hard for "just curious".  This
little Python program computes the exact number of ways to get each
sum in 0 .. 1000 quickly (fraction of a second on my box):

"""
def mul(p1, p2):
    result = [0] * (len(p1) + len(p2) - 1)
    for i, x1 in enumerate(p1):
        for j, x2 in enumerate(p2):
            result[i+j] += x1 * x2
    while result and result[-1] == 0:
        del result[-1]
    return result

base = [1] * 101
result = [1]
for dummy in range(10):
    result = mul(result, base)

assert len(result) == 1001
assert sum(result) == 101**10
"""

Then result[s] is the exact number of ways to get sum s, for each s in
range(1001).

Figuring out why that works is the "probably too hard for 'just
curious'" part.  If you want to pursue that, it's a straightforward
implementation of fully multiplying out:

    (1 + x + x**2 + ... +x**100)**10

A polynomial here is represented by a list L of coefficients, where
L[i] is the coefficient of x**i.  `mul()` implements polynomial
multiplication using this format.  For example,

>>> mul([1, 1], [-1, 1])
[-1, 0, 1]

or, IOW, (x+1)*(x-1) = (x**2 - 1).