|
|
| Author |
Message |
wasknijper
science forum beginner
Joined: 03 May 2005
Posts: 16
|
 Posted: Fri May 20, 2005 3:47 pm Post subject:
A probability problem
|
|
|
Here is a probability problem from real life (I am now running the
program that the problem is about).
A computer program goes through 720 loops to find the best score (no
need to elaborate on what score that is). The program has now finished
25 loops; the best score so far was found in loop 7.
How do you calculate the probability p that this score will remain the
best, if, at the start, each loop is equally likely to find the best
score, and the chance of more than 1 loop both/all finding it is zero?
Is the number 7 relevant at all, or are 720 and 25 enough to find p? I
hope my wording is clear. |
|
| Back to top |
|
 |
Bill McCray
science forum beginner
Joined: 18 May 2005
Posts: 44
|
| Posted: Fri May 20, 2005 4:48 pm Post subject:
Re: A probability problem
|
|
|
On Fri, 20 May 2005 19:47:39 +0200, wasknijper <wasknijper@x.y> wrote:
| Quote: | Here is a probability problem from real life (I am now running the
program that the problem is about).
A computer program goes through 720 loops to find the best score (no
need to elaborate on what score that is). The program has now finished
25 loops; the best score so far was found in loop 7.
How do you calculate the probability p that this score will remain the
best, if, at the start, each loop is equally likely to find the best
score, and the chance of more than 1 loop both/all finding it is zero?
Is the number 7 relevant at all, or are 720 and 25 enough to find p? I
hope my wording is clear.
|
I think there is a need for an elaboration of the scoring. For
example, if the score found in loop 7 is the highest possible score,
the probably of finding a high score in the remaining loops is zero.
The distribution function of the scores and where the score found in P
falls among the possible scores are both significant.
With only the information you've given, I expect that the probability
of the highest score being found in the remaining 695 loops is
695/720.
Bill
Swap first and last parts of username and ISP for address. |
|
| Back to top |
|
|
Guest
|
| Posted: Fri May 20, 2005 5:51 pm Post subject:
Re: A probability problem
|
|
|
wasknijper wrote:
| Quote: | Here is a probability problem from real life (I am now running the
program that the problem is about).
A computer program goes through 720 loops to find the best score (no
need to elaborate on what score that is). The program has now
finished
25 loops; the best score so far was found in loop 7.
How do you calculate the probability p that this score will remain
the
best, if, at the start, each loop is equally likely to find the best
score, and the chance of more than 1 loop both/all finding it is
zero?
Is the number 7 relevant at all, or are 720 and 25 enough to find p?
I
hope my wording is clear.
|
The probability of the best score being found ANYWHERE in the first 25
loops is 25/720. |
|
| Back to top |
|
|
wasknijper
science forum beginner
Joined: 03 May 2005
Posts: 16
|
| Posted: Fri May 20, 2005 5:55 pm Post subject:
Re: A probability problem
|
|
|
Bill McCray wrote:
| Quote: | I think there is a need for an elaboration of the scoring. For
example, if the score found in loop 7 is the highest possible score,
the probably of finding a high score in the remaining loops is zero.
The distribution function of the scores and where the score found in P
falls among the possible scores are both significant.
|
Thanks for your reply. I cancelled my message, because I thought after
all that 7 didn't play any role, but the posting reached you anyway.
It's an exhaustive search, so it will be known what the highest
possible score is, but only after the program has finished. It cannot
be calculated beforehand.
I have reason to believe the result from loop 7 is rather good, as
it's higher than results found in several non-exhaustive searches, but
it's impossible to quantify things. The important thing for me is
that, apparently, 7 isn't relevant here.
70 loops have been completed, and the result from loop 7 still stands... |
|
| Back to top |
|
|
John Bailey
science forum addict
Joined: 05 May 2005
Posts: 72
|
| Posted: Sat May 21, 2005 12:01 pm Post subject:
Re: A probability problem
|
|
|
On Fri, 20 May 2005 19:47:39 +0200, wasknijper <wasknijper@x.y> wrote:
| Quote: | A computer program goes through 720 loops to find the best score (no
need to elaborate on what score that is). The program has now finished
25 loops; the best score so far was found in loop 7.
How do you calculate the probability p that this score will remain the
best, if, at the start, each loop is equally likely to find the best
score, and the chance of more than 1 loop both/all finding it is zero?
|
As commented in another response, the probability that the largest
score is found within 25 loops is 25/720. The probability that a
higher score will be found on a later loop is therefore 695/720. That
sounds pretty bad. OTOH, suppose you can only afford 25 loops.
Knowing that the largest score came on loop 7 must tell you something.
Refer to: National Institute of Standards articles on Extreme Value
statistics and Rank Order statistics.
http://www.itl.nist.gov/div898/handbook/apr/section1/apr163.htm
http://www.itl.nist.gov/div898/handbook/prc/section2/prc252.htm
If you can forego absolute assurance that loop 7 is the largest score
and are satisfied with knowing the probability that the value on loop
7 is close to the maximum--say, within the top 4%, this might help.
Order statistics provide a way of estimating proportions of the data
that should fall above and below a given value, called a percentile.
The pth percentile is a value, Y(p), such that at most (100p)% of the
measurements are less than this value and at most 100(1- p)% are
greater. The 50th percentile is called the median.(NIST quote)
Percentiles can be estimated from N measurements as follows: for the
pth percentile, set p(N+1) equal to k + d for k an integer, and d, a
fraction greater than or equal to 0 and less than 1.(NIST quote)
Formulae for estimating p(N) are given on the same page as the above
quotes:
http://www.itl.nist.gov/div898/handbook/prc/section2/prc252.htm
| Quote: | Is the number 7 relevant at all, or are 720 and 25 enough to find p?
The number 7 isn't relevant except as a label for the extreme value |
found within the first 25 loops.
| Quote: | I hope my wording is clear.
The part about "...the chance of more than 1 loop both/all finding it |
is zero?" left me wondering what you meant.
John Bailey
http://home.rochester.rr.com/jbxroads/mailto.html |
|
| Back to top |
|
|
Peter Webb
science forum Guru Wannabe
Joined: 05 May 2005
Posts: 192
|
| Posted: Sat May 21, 2005 12:51 pm Post subject:
Re: A probability problem
|
|
|
| Quote: | I hope my wording is clear.
The part about "...the chance of more than 1 loop both/all finding it
is zero?" left me wondering what you meant.
|
He means the maximum value is unique.
Just to repeat what some others have said, and add slightly,
If you check x% of your 720 possible loops, then you have an x% chance of
finding the largest.
However, by checking only x% of values, you may expect to be within y% - say
20% - of the true highest. Exactly what this y is (or the formula linking x%
and y%) depends upon how variable your data is. In the context of a game -
like checking character strengths - the number you calculate is likely to be
sum of a wjole lot of independent variables, in which case you get a Normal
(Gaussian) distribution. There are tables which you can use to calculate
this, and if this is of interest it can be calculated if you know the
distribution of each independent variable. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 8:39 pm | All times are GMT
|
|
Debt Consolidation | Credit Card Debt | Personal Loans | Loans | Guitar Lessons
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Recreational
