443,730 Members | 1,540 Online Need help? Post your question and get tips & solutions from a community of 443,730 IT Pros & Developers. It's quick & easy.

# Probability Problem

 P: n/a 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 This link may help: http://www.math.csusb.edu/faculty/st...o_prob_models/ calcprob.html -- Elliot Temple http://www.curi.us/blog/ Apr 25 '06 #1
8 Replies

 P: n/a In article , Elliot Temple wrote: Problem: Randomly generate 10 integers from 0-100 inclusive, and sumthem. Do that twice. What is the probability the two sums are 390 apart? I think the sum would come close to a normal distribution. Apr 25 '06 #2

 P: n/a Lawrence D'Oliveiro wrote: In article , Elliot Temple wrote:Problem: Randomly generate 10 integers from 0-100 inclusive, and sumthem. 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 Apr 25 '06 #3

 P: n/a On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote: Lawrence D'Oliveiro wrote: In article , 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 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/ Apr 25 '06 #4

 P: n/a Elliot Temple wrote: On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote: Lawrence D'Oliveiro wrote: In article , 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 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 Apr 25 '06 #5

 P: n/a [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 =  * (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 =  * 101 result =  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). Apr 25 '06 #6

 P: n/a 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 =  for i in xrange(10): result = combine( * 101, result) return result def combine(a, b): results =  * (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 wrote: On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote: Lawrence D'Oliveiro wrote: In article , 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 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/ Apr 25 '06 #7

 P: n/a I had a possibly similar problem calculating probs related to premium 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 This link may help: http://www.math.csusb.edu/faculty/st.../calcprob.html -- Elliot Temple http://www.curi.us/blog/ Apr 25 '06 #8

 P: n/a [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 =  for i in xrange(10): result = combine( * 101, result) return result def combine(a, b): results =  * (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. Apr 25 '06 #9

### This discussion thread is closed

Replies have been disabled for this discussion. 