Probability Problem

[Tim Peters]

[Elliot Temple]
> I think I got it. I noticed my code is essentially the same as Tim
> Peter's (plus the part of the problem he skipped). I read his code 20
> minutes before recreating mine from Alex's hints. Thanks!
>
> def main():
>      ways = ways_to_roll()
>      total_ways = float(101**10)
>      running_total = 0
>      for i in range(1000-390+1):
>          j = i + 390
>          running_total += ways[i] * ways[j]
>      print running_total / total_ways**2
>      print ways[:10]
>
> def ways_to_roll():
>      result = [1]
>      for i in xrange(10):
>          result = combine([1] * 101, result)
>      return result
>
> def combine(a, b):
>      results = [0] * (len(a) + len(b) - 1)
>      for i, ele in enumerate(a):
>          for j, ele2 in enumerate(b):
>              results[i+j] += ele * ele2
>      return results
>
> main()
> # output: 3.21962542309e-05 and
> # [1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620]
> # 3.21962542309e-05 is 32 out of a million

You should sanity-check the computation by generalizing it, then
applying it to a case so small you can easily work out the result via
exhaustive enumeration by hand.

For example, suppose you took integers from the much smaller set {0,
1}, and did that only twice.  Then the possible sums and their
probabilities are clearly:

   0  1/4
   1  1/2
   2  1/4

If you did this twice, what's the probability that the sums differ by
1?  Suitably generalized, your program above would compute 1/4.  Is
that actually right?  It depends on what exactly "the sums differ by
1" means.  If it means the second sum is one larger than the first
sum, 1/4 is correct.  Ditto if it means the second sum is one smaller
than the first sum.  But if it means 1 is the absolute value of the
difference of the sums, the right answer is 1/2.  I'm not sure which
meaning you have in mind, but the last one was my guess.