Probability Problem

[Alex Martelli]

Elliot Temple <curi at curi.us> wrote:

> On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
> 
> > Lawrence D'Oliveiro <ldo at geek-central.gen.new_zealand> wrote:
> >
> >> In article <mailman.4949.1145931967.27775.python-list at python.org>,
> >>  Elliot Temple <curi at curi.us> wrote:
> >>
> >>> Problem: Randomly generate 10 integers from 0-100 inclusive, and sum
> >>> them. Do that twice. What is the probability the two sums are 390
> >>> apart?
> >>
> >> I think the sum would come close to a normal distribution.
> >
> > Yes, very close indeed, by the law of large numbers.
> >
> > However, very close (in a math course at least) doesn't get the cigar.
> >
> > 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.
> 
> That was the plan, but how do I get the probability of any given  
> result? (in a reasonable amount of time)
> 
> BTW I'm not in a math course, just curious.

OK, I'll trust that last assertion (sorry for the hesitation, but it's
all too easy to ``help'' somebody with a homework assignment and
actually end up damaging them by doing it FOR them!-).


I'm still going to present this in a way that stimulates thought, rather
than a solved problem -- humor me...!-)


You're generating a uniformly distributed random number in 0..100 (101
possibilities), 10 times, and summing the 10 results.

How do you get a result of 0?  Only 1 way: 0 at each attempt --
probability 1 (out of 1010 possibilities).

How do you get a result of 1?  10 ways: 1 at one attempt and 0 at each
of the others - probability 10 (again in 1010'ths;-).

How do you get a result of 2?  10 ways for '2 at one attempt and 0 at
each of the others', plus, 10*9/2 ways for '1 at two attempts and 0 at
each of the others' -- probability 55 (ditto).

...and so forth, but you'd rather not work it out...


So, suppose you start with a matrix of 101 x 10 entries, each of value 1
since all results are equiprobable (or, 1/1010.0 if you prefer;-).

You want to compute the number in which you can combine two rows.  How
could you combine the first two rows (each of 101 1's) to make a row of
201 numbers corresponding to the probabilities of the sum of two throws?

Suppose you combine the first entry of the first row with each entry of
the second, then the second entry of the first row with each entry of
the second, etc; each time, you get a sum (of two rolls) which gives you
an index of a entry (in an accumulator row starting at all zeros) to
increment by the product of the entries you're considering...


Can you generalize that?  Or, do you need more hints?  Just ask!


Alex