Velocity Reviews > Probability Problem

# Probability Problem

Elliot Temple
Guest
Posts: n/a

 04-25-2006
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 have code to do part of it (below), and I know how to write code to
do the rest. The part I have calculates the number of ways the dice
can come out to a given number. The problem is the main loop has 9
iterations and it takes about 2.5 minutes to begin the 4th one, and
each iteration is about 101 times longer than the previous one. So:

>>> x = 2.5 * 101**6
>>> x /= (60*24*365.25)
>>> x

5045631.5622908585

It'd take 5,000 millennia. (If my computer didn't run out of memory
after about 4 minutes, that is.)

Any suggestions? Either a way to do the same thing much more
efficiently (enough that I can run it) or a different way to solve
the problem.

Code:

li = range(101)
li2 = []
range101 = range(101)
for x in xrange(9):
print "x is %s" % x
li2 = []
for y in li:
for z in range101:
li2 += [y+z]
li = li2
print li.count(800)
# prints how many ways the dice can add to 800

http://www.math.csusb.edu/faculty/st...o_prob_models/
calcprob.html

-- Elliot Temple
http://www.curi.us/blog/

Lawrence D'Oliveiro
Guest
Posts: n/a

 04-25-2006
In article <(E-Mail Removed)>,
Elliot Temple <(E-Mail Removed)> 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.

Alex Martelli
Guest
Posts: n/a

 04-25-2006
Lawrence D'Oliveiro <(E-Mail Removed)_zealand> wrote:

> In article <(E-Mail Removed)>,
> Elliot Temple <(E-Mail Removed)> 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.

Alex

Elliot Temple
Guest
Posts: n/a

 04-25-2006

On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:

> Lawrence D'Oliveiro <(E-Mail Removed)_zealand> wrote:
>
>> In article <(E-Mail Removed)>,
>> Elliot Temple <(E-Mail Removed)> 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.

-- Elliot Temple
http://www.curi.us/blog/

Alex Martelli
Guest
Posts: n/a

 04-25-2006
Elliot Temple <(E-Mail Removed)> wrote:

> On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
>
> > Lawrence D'Oliveiro <(E-Mail Removed)_zealand> wrote:
> >
> >> In article <(E-Mail Removed)>,
> >> Elliot Temple <(E-Mail Removed)> 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

Tim Peters
Guest
Posts: n/a

 04-25-2006
[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).

Elliot Temple
Guest
Posts: n/a

 04-25-2006
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

On Apr 24, 2006, at 9:14 PM, Alex Martelli wrote:

> Elliot Temple <(E-Mail Removed)> wrote:
>
>> On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
>>
>>> Lawrence D'Oliveiro <(E-Mail Removed)_zealand> wrote:
>>>
>>>> In article <(E-Mail Removed)>,
>>>> Elliot Temple <(E-Mail Removed)> 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
> --
> http://mail.python.org/mailman/listinfo/python-list
>

-- Elliot Temple
http://www.curi.us/blog/

Peter Tillotson
Guest
Posts: n/a

 04-25-2006
bond permutation. With 10^12 memory ran out v quickly. In the end I got
round it by writing a recursive function and quantising the probability
density function.

Elliot Temple 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 have code to do part of it (below), and I know how to write code to do
> the rest. The part I have calculates the number of ways the dice can
> come out to a given number. The problem is the main loop has 9
> iterations and it takes about 2.5 minutes to begin the 4th one, and each
> iteration is about 101 times longer than the previous one. So:
>
>>>> x = 2.5 * 101**6
>>>> x /= (60*24*365.25)
>>>> x

> 5045631.5622908585
>
> It'd take 5,000 millennia. (If my computer didn't run out of memory
> after about 4 minutes, that is.)
>
> Any suggestions? Either a way to do the same thing much more efficiently
> (enough that I can run it) or a different way to solve the problem.
>
> Code:
>
> li = range(101)
> li2 = []
> range101 = range(101)
> for x in xrange(9):
> print "x is %s" % x
> li2 = []
> for y in li:
> for z in range101:
> li2 += [y+z]
> li = li2
> print li.count(800)
> # prints how many ways the dice can add to 800
>
>
> http://www.math.csusb.edu/faculty/st.../calcprob.html
>
>
> -- Elliot Temple
> http://www.curi.us/blog/
>

Tim Peters
Guest
Posts: n/a

 04-25-2006
[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.