473,320 Members | 2,107 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Probability Problem

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 2734
In article <ma***************************************@python. org>,
Elliot Temple <cu**@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.
Apr 25 '06 #2
Lawrence D'Oliveiro <ld*@geek-central.gen.new_zealand> wrote:
In article <ma***************************************@python. org>,
Elliot Temple <cu**@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.
Alex
Apr 25 '06 #3

On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
Lawrence D'Oliveiro <ld*@geek-central.gen.new_zealand> wrote:
In article <ma***************************************@python. org>,
Elliot Temple <cu**@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.

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

Apr 25 '06 #4
Elliot Temple <cu**@curi.us> wrote:
On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
Lawrence D'Oliveiro <ld*@geek-central.gen.new_zealand> wrote:
In article <ma***************************************@python. org>,
Elliot Temple <cu**@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
Apr 25 '06 #5
[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).
Apr 25 '06 #6
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 <cu**@curi.us> wrote:
On Apr 24, 2006, at 8:24 PM, Alex Martelli wrote:
Lawrence D'Oliveiro <ld*@geek-central.gen.new_zealand> wrote:

In article <ma***************************************@python. org>,
Elliot Temple <cu**@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
--
http://mail.python.org/mailman/listinfo/python-list


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

Apr 25 '06 #7
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
[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.
Apr 25 '06 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: Robert Best | last post by:
I have the z-score value and what i need is the corresponding probability. I can determine it with a table like this one: http://www.epatric.com/documentation/statistics/z-score_table.html But...
1
by: kpp9c | last post by:
Greetings, I am working on a program to produce patterns. What would like is for it to exhaustively produce all possible permutations of a sequence of items but for each permutation produce...
1
by: Richard Fleming | last post by:
hi, i need to write a probability engine that works out the score in a football match based on player stats, formation, weather etc. I dont even know how to use probability in c..... so please can...
2
by: Andreas Schmitt | last post by:
Hi, Sorry for posting in German before, totally forgot about that when I was pasting this in here from another German newsgroup I was writing to, trying to get help I am programming a simple...
11
by: Mayank Kaushik | last post by:
hi everyone, im trying to create a function that generates a 1 or a 0, with the probability of a 1 being generated equal to X (which is passed to the function as a parameter). any ideas?...
3
by: Arun Nair | last post by:
''' Can anyone help me with this program it just takes probability of the first team and runs the program doesnt takes the probability of the second team even though specified''' from random...
2
by: Efrat Regev | last post by:
Hello, Let's say a probability vector of dimension d is x_1, ..., x_d, where each one is a non-negative term, and they all sum up to 1. Now I'd like to iterate over all probability vectors, but...
1
by: coolguyraj | last post by:
I have a PHP and javascript code to take value from two text boxes and calculate on triggering the "OnBlur" function and display in the third box. The code works fine with one line item,If i have...
7
by: Extremity | last post by:
Hi, I am taking a intro to C++ course so my knowledge base only limits to areas such as if/else, functions, and recursions. We are creating a program which will determine the probability of Poker...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.