Search   Memberlist   Usergroups
 Page 2 of 8 [110 Posts] View previous topic :: View next topic Goto page:  Previous  1, 2, 3, 4, 5, 6, 7, 8 Next
Author Message
Jon Haugsand
science forum beginner

Joined: 03 May 2005
Posts: 37

Posted: Tue Jun 14, 2005 6:31 pm    Post subject: Re: Probability question, was Re: Mensa Forgot Another Possibility!

* Scott Hemphill
 Quote: That's why I gave a reference. There are some smart and easy explanations depending on your background. I'll give one below which uses generating functions.

Thanks. I actually have a lot of background, but somehow generating
functions have escaped my education. Time to look into it.

--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Tue Jun 14, 2005 1:56 pm    Post subject: Re: Probability question, was Re: Mensa Forgot Another Possibility!

Scott Hemphill <hemphill@hemphills.net> writes:

 Quote: d(n) = n! sum(k=0,n) (-1)^k/k! = n! (e^-1 - sum(k>n) (-1)^k/k!) It's pretty easy to establish that this sum for k>n is less than 1/2 for n > 0, and since d(n) is an integer, it must be the one you get when you round n!/e to the nearest integer. The expression has to be fixed to get the correct answer for n = 0. Hence,

I meant to say that it's easy to establish that

n! sum(k>n) (-1)^k/k! has absolute value less than 1/2 for n > 0.

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Tue Jun 14, 2005 1:41 pm    Post subject: Re: Probability question, was Re: Mensa Forgot Another Possibility!

Jon Haugsand <jonhaug@ifi.uio.no> writes:

 Quote: * Scott Hemphill and subfactorial(n) is the number of derangements of n objects, i.e. the number of permutations for which none of objects are in their original position. subfactorial(n) is further developed: subfactorial(n) = round(n!/e) + [n==0] where round is the function which rounds to the nearest integer and the bracket notation yields 1 if the boolean expression inside is true and 0 if the boolean expression is false. I've used == for the equality operator, and e is Euler's constant e = 2.71828.... Interesting, but hardly educational. This /is/ a mysterious formula. Why does it work? I don't really want an answer (unless you have some smart and easy explanation), but will try to search the answer for myselv.

That's why I gave a reference. There are some smart and easy explanations
depending on your background. I'll give one below which uses generating
functions.

 Quote: Anyway, it might be useful to point out a recursive solution to the whole problem: h(n,k) = number of ways K hats land on a correct head out of N heads. h(n,n) = 1 h(n,n-1) = 0 h(n,k) = choose(n,k) * h(n-k,0) h(n,0) = n! - [ sum(i=1,n) h(n,i) ] This formula is implementable on a computer, and follows naturally from the problem description. It is of course the h(n,0) that is different, i.e. your subfactorial.

n! = sum(k=0,n) h(n,k)

n! = sum(k=0,n) choose(n,k) h(n-k,0)

I'll notate h(n,0) as d(n), the number of derangements of n objects.

n! = sum(k=0,n) choose(n,k) d(n-k)

1 = sum(k=0,n) 1/k! d(n-k)/(n-k)!

The sequence generated by the right half of this equation for n = 0, 1, ...
is the convolution of the sequences 1/n! and d(n)/n! Therefore the
generating function of the sequence for the left side of the equation,
(1, 1, ...) will be equal to the product of the generating functions
for 1/n! and d(n)/n!.

The generating function for (1, 1, ...) is sum(k>=0) 1*z^k = 1/(1-z).
The generating function for 1/n! is sum(k>=0) 1/k! z^k = e^z.
Let the generating function for d(n)/n! be D(z).

Then

1/(1-z) = e^z D(z), or D(z) = e^-z/(1-z)

D(z) = 1/(1-z) (z^0/0! - z^1/1! + z^2/2! - ... )

The value of d(n)/n! will be the coefficient of z^n. Since
1/(1-z) = 1 + z + z^2 + ..., the coefficient of z^n will be

sum(k=0,n) (-1)^k/k!

So

d(n)/n! = sum(k=0,n) (-1)^k/k!

Note that this sum goes to e^-1 as n goes to infinity.

d(n) = n! sum(k=0,n) (-1)^k/k!

= n! (e^-1 - sum(k>n) (-1)^k/k!)

It's pretty easy to establish that this sum for k>n is less than 1/2
for n > 0, and since d(n) is an integer, it must be the one you get
when you round n!/e to the nearest integer. The expression has to
be fixed to get the correct answer for n = 0. Hence,

d(n) = round(n!/e) + [n==0]

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
Jon Haugsand
science forum beginner

Joined: 03 May 2005
Posts: 37

Posted: Tue Jun 14, 2005 12:16 pm    Post subject: Re: Probability question, was Re: Mensa Forgot Another Possibility!

* Scott Hemphill
 Quote: and subfactorial(n) is the number of derangements of n objects, i.e. the number of permutations for which none of objects are in their original position. subfactorial(n) is further developed: subfactorial(n) = round(n!/e) + [n==0] where round is the function which rounds to the nearest integer and the bracket notation yields 1 if the boolean expression inside is true and 0 if the boolean expression is false. I've used == for the equality operator, and e is Euler's constant e = 2.71828....

Interesting, but hardly educational. This /is/ a mysterious formula.
Why does it work? I don't really want an answer (unless you have some
smart and easy explanation), but will try to search the answer for
myselv.

Anyway, it might be useful to point out a recursive solution to the
whole problem:

h(n,k) = number of ways K hats land on a correct head out of N heads.

h(n,n) = 1
h(n,n-1) = 0
h(n,k) = choose(n,k) * h(n-k,0)
h(n,0) = n! - [ sum(i=1,n) h(n,i) ]

This formula is implementable on a computer, and follows naturally
from the problem description. It is of course the h(n,0) that is

--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
Martin Evans
science forum beginner

Joined: 10 Jun 2005
Posts: 3

Posted: Tue Jun 14, 2005 10:07 am    Post subject: Re: Probability question

Scott Hemphill wrote:

 Quote: Scott Hemphill writes: Martin Evans writes: Scott Hemphill wrote: Pr = (T-R-1)! / (R! * (T-R)!) And what is the probability for 19 right answers out of 20? Hint: where does the 20th answer go? For T = 20 and R = 19 we get Pr = (20 - 19 - 1)!/(19! * (20 - 1)!) = 0!/19! = 0 I think this is what we would expect - the probablity of getting exactly 19 questions right would be zero, wouldn't it? PS - I don't need the hint, thanks! :-P No. 0! is not zero. It is one. I mean, yes the probability is zero. But, no your formula doesn't produce that result. Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear

I had forgotten that 0! is not zero - it's all too long ago!
There is a problem with the formula I derived anyway, as you have correctly said in another
posting, but I haven't had the time to look at it yet! I need to go round the loop again,
but I think the basic approach is right.
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Mon Jun 13, 2005 12:45 pm    Post subject: Re: Probability question

Scott Hemphill <hemphill@hemphills.net> writes:

 Quote: Martin Evans writes: Scott Hemphill wrote: Pr = (T-R-1)! / (R! * (T-R)!) And what is the probability for 19 right answers out of 20? Hint: where does the 20th answer go? For T = 20 and R = 19 we get Pr = (20 - 19 - 1)!/(19! * (20 - 1)!) = 0!/19! = 0 I think this is what we would expect - the probablity of getting exactly 19 questions right would be zero, wouldn't it? PS - I don't need the hint, thanks! :-P No. 0! is not zero. It is one.

I mean, yes the probability is zero. But, no your formula doesn't produce
that result.

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Mon Jun 13, 2005 12:39 pm    Post subject: Re: Probability question

Martin Evans <Martin.Evans@arm.com> writes:

 Quote: Scott Hemphill wrote: Pr = (T-R-1)! / (R! * (T-R)!) And what is the probability for 19 right answers out of 20? Hint: where does the 20th answer go? For T = 20 and R = 19 we get Pr = (20 - 19 - 1)!/(19! * (20 - 1)!) = 0!/19! = 0 I think this is what we would expect - the probablity of getting exactly 19 questions right would be zero, wouldn't it? PS - I don't need the hint, thanks!

No. 0! is not zero. It is one.

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
Martin Evans
science forum beginner

Joined: 10 Jun 2005
Posts: 3

Posted: Mon Jun 13, 2005 11:09 am    Post subject: Re: Probability question

Scott Hemphill wrote:

 Quote: Pr = (T-R-1)! / (R! * (T-R)!) And what is the probability for 19 right answers out of 20? Hint: where does the 20th answer go?

For T = 20 and R = 19 we get Pr = (20 - 19 - 1)!/(19! * (20 - 1)!) = 0!/19! = 0

I think this is what we would expect - the probablity of getting exactly 19 questions
right would be zero, wouldn't it? PS - I don't need the hint, thanks! :-P

 Quote: [1] As this is cam.misc, that is an absolute certainty, whether I am right or wrong! :-) There are a few more newsgroups than just cam.misc.

Yes, of course there are.
alan truelove
science forum beginner

Joined: 09 Jun 2005
Posts: 8

 Posted: Sat Jun 11, 2005 5:23 am    Post subject: Re: Probability question Piled higher and even more deeper .. Develop iterative method for the following and then show a VB.Net code to implement it .. (I have a nice solution which goes on from my previous solutions, and uses a neat combinatorial method, but this space is too small to contain it) OK, it's June 11th, 2005, let's just see... ..- - - - - - - - - - - - - k groups of n objects each are presented; select one object from each group (a 'tuple') Given the first object, the (correct) other k-1 are unique. Repeat until all tuples have been selected. P(k,n,x) is prob(get x correct tuples)
Alex Selby
science forum beginner

Joined: 30 May 2005
Posts: 10

Posted: Fri Jun 10, 2005 9:53 pm    Post subject: Re: Probability question

alan truelove wrote:
 Quote: From rec.org.mensa anyone got a slicker solution ?? ' - - - - - - - - - - - - On Thu, 9 Jun 2005 13:56:11 +0200, "Mark" Markiehatesspam@notelespam2.fr> wrote: "BruceS" wrote in message news:1118264621.238754.254340@f14g2000cwb.googlegroups.com... I wouldn't be at all offended if you reposted there and returned here with any answers. I try to avoid crossposting, especially to groups I don't follow. Here then is the question as I remember it: on consideration this may not be precisely on topic for sci.stat.math although I suppose that in general people who are up on stats are up on probability too. A student sits a test that has 20 questions; every question has precisely 1 matching answer. There are 20 answers, no duplication. The student answers every question with a different answer from the 20. What is the probability, of a student answering randomly, answering precisely 1 right? precisely 10 right? Mark ' - - - Getting 1 right: 0.3679 Getting 10 right: 0.01378 * 10^(-7) '- - - -

The probability of getting r right out of n is D(n-r)/(r!(n-r)!)
where D(k) = / 1 if k=0
\ the nearest integer to k!/e if k>0

This is well approximated by 1/(r!e) if r isn't too close to n.

---

Alex
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Fri Jun 10, 2005 7:31 pm    Post subject: Re: Probability question

Martin Evans <Martin.Evans@arm.com> writes:

 Quote: Then we have T-R columns left, each of which has the cell on the leading diagonal forbidden to us, as well as the rows already containing 'x's for right answers. The first column we add an 'x' to would thus have (T-R-1) valid cells available. So we would have No = (T-R-1)! using a similar argument as that for Nt.

This is where the error is. The first column will indeed have (T-R-1) valid
cells. However the second column and each additional column will will either
have (T-R-2) valid cells or (T-R-1) valid cells depending on whether the
corresponding row has already been picked.

For example, consider the case where T-R = 3, and just look at the 3x3 matrix
of containing the remaining rows and columns.

X . .
X . O = chosen, X = unavailable
O . X

Working column by column, if we pick the third row for the first column,
then there is only one choice for the second column.

X . .
O X .
. . X

If we instead pick the second row for the first column, then there are
two choices for the second column.

 Quote: The chance, Pr, of getting *exactly* R right answers in T tests is therefore Nr/Nt = (Nd * No) / Nt = (T! * (T-R-1)!) / (T! * (T-R)! * R!) Simplifying the above expression, we get: Pr = (T-R-1)! / (R! * (T-R)!)

This formula can't be right. What if T=R? You get a (-1)! term (which is
infinite).

If you have a correct formula, you should expect it to get the correct
results for easily verifiable simple cases:

T = 0
R = 0, Pr = 1

T = 1
R = 0, Pr = 0
R = 1, Pr = 1

T = 2
R = 0, Pr = 1/2
R = 1, Pr = 0
R = 2, Pr = 1/2

T = 3
R = 0, Pr = 1/3
R = 1, Pr = 1/2
R = 2, Pr = 0
R = 3, Pr = 1/6

T = nonnegative integer
R = T-1, Pr = 0
R = T, Pr = 1/T!

You should also expect that the sum of the probabilities for a given T
will be one!

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
alan truelove
science forum beginner

Joined: 09 Jun 2005
Posts: 8

Posted: Fri Jun 10, 2005 5:56 pm    Post subject: Re: Probability question

(Correctedt code!)

-- but I took T=4, and got a total for all
 Quote: probs R=0,1,2,3,4 of 0.5833 Shomething wrong shurely! (I may well have made a dumb mistake ..) with best wishes ' - - - Public Sub Button1_Click(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles Button1.Click
Dim i, j, iii, jjj, ii, jj As Integer
ReDim P(100, 100)
ReDim Q(100, 100)

Dim T, R, Rfact, TRfact, TR1fact As Integer
Dim tot, hold As Single
T = 4
tot = 0
For R = 0 To T
TRfact = fact.fact(T - R)
TR1fact = fact.fact(T - R - 1)
Rfact = fact.fact(R)
'(T-R-1)! / (R! * (T-R)!)
hold = Rfact * TRfact
If hold > 0 Then tot = tot + TR1fact / hold
Next
MsgBox(tot)
 Quote: ' - - - Module fact Function fact(ByVal j As Integer) As Integer Dim i As Integer fact = 1 If j = 0 Then fact = 0 Exit Function End If For i = 2 To j fact = fact * i Next End Function End Module
alan truelove
science forum beginner

Joined: 09 Jun 2005
Posts: 8

Posted: Fri Jun 10, 2005 4:29 pm    Post subject: Re: Probability question

 Quote: we get: Pr = (T-R-1)! / (R! * (T-R)!) For T = 20, R = 1 I get Pr = 18! / (1! * 19!) = 1/19 = 0.0526 For T = 20, R= 10 I get Pr = 9!/(10! * 10!) = 1/(10 * 10!) = 2.76 x 10^-8 I am sorry that my answers differ from the previously quoted ones! It is of course possible that the above is in error, and maybe[1] one of the real mathematicians here will correct me in that case. Even if the above is wrong, the method may be of interest. Or, of course, it may be right! - - -

I applaud your efforts -- but I took T=4, and got a total for all
probs R=0,1,2,3,4 of 6.25
Shomething wrong shurely!
(I may well have made a dumb mistake ..)
with best wishes
' - - -
Public Sub Button1_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button1.Click
Dim i, j, iii, jjj, ii, jj As Integer
ReDim P(100, 100)
ReDim Q(100, 100)

Dim T, R, Rfact, TRfact, TR1fact As Integer
Dim tot, hold As Single
T = 4
TRfact = fact.fact(T - R)
TR1fact = fact.fact(T - R - 1)
tot = 0
For R = 0 To T
Rfact = fact.fact(R)
TRfact = fact.fact(T - R - 1)
'(T-R-1)! / (R! * (T-R)!)
hold = Rfact * TRfact
If hold > 0 Then tot = tot + TR1fact / hold
Next
MsgBox(tot)
end sub
' - - -
Module fact
Function fact(ByVal j As Integer) As Integer
Dim i As Integer
fact = 1
If j = 0 Then
fact = 0
Exit Function
End If
For i = 2 To j
fact = fact * i
Next
End Function
End Module
Scott Hemphill
science forum beginner

Joined: 09 Jun 2005
Posts: 21

Posted: Fri Jun 10, 2005 4:21 pm    Post subject: Re: Probability question

Martin Evans <Martin.Evans@arm.com> writes:

And what is the probability for 19 right answers out of 20? Hint: where

 Quote: [1] As this is cam.misc, that is an absolute certainty, whether I am right or wrong!

There are a few more newsgroups than just cam.misc.

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
alan truelove
science forum beginner

Joined: 09 Jun 2005
Posts: 8

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 2 of 8 [110 Posts] Goto page:  Previous  1, 2, 3, 4, 5, 6, 7, 8 Next View previous topic :: View next topic
 The time now is Fri Apr 26, 2019 9:39 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics about uni. continuous proof bill1158 Math 1 Tue Jul 18, 2006 10:30 pm Distribution of Goldbach pairs as even integers n increases stargene@sbcglobal.net Math 1 Mon Jul 17, 2006 5:02 am (humor) Another hand-waving incredibly simple proof of FLT DGoncz@aol.com Math 0 Fri Jul 14, 2006 7:50 pm Odd Squares, 8 (2^3), and the Sum of the First n Positive... rer Math 1 Thu Jul 13, 2006 1:58 am JSH: Way too interesting jstevh@msn.com Math 22 Thu Jul 13, 2006 1:15 am