wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Re: Expected number
        
(Message started by: 1337b4k4 on Jan 21^st, 2009, 6:54pm)

Title: Re: Expected number
Post by 1337b4k4 on Jan 21^st, 2009, 6:54pm

[hide]The probability that the tool you are currently holding is the tool that you eventually need is ~~http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif1/phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subi.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif~~ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifphttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subi.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sup2.gif. Call this number x for convenience. Then with probability x, s/he only examines 1 tool, and with probability 1-x, s/he needs on average (n-1)/2 additional tools after the first until s/he finds the right one (this assumes that this person still mindlessly "examines" the last possible tool needed, even though this is unnecessary). So the expected value is ~~1 + (1-x)(n-1)/2.~~ 1 + (1-x)*n/2[/hide]

Title: Re: Expected number
Post by 1337b4k4 on Jan 21^st, 2009, 8:02pm

on 01/21/09 at 19:26:25, howard roark wrote:

Isn't the probability of current tool we are holding to be the correct one sum(i=1ton) pi^2??

I dont understand why it is the reciprocal of pi^2

Also in the expected number dont we have to multiply 1 with x in the first term??

Yes, that's my mistake - it should not be the reciprocals. We don't mutliply 1 with x in the first term, because we know for a fact that we will see at least one, that we need to add to the (n-1)/2 term. 1 + (1-x)(n-1)/2 = x(1) + (1-x)[(n-1)/2 + 1]

on 01/21/09 at 19:40:31, howard roark wrote:

I was actually working on calculating the actual probabilities of finding the correct tool in x=2,3,....n number of examinations..

E(x)=sum(x=1ton)x.p(x)

I found the terms to be really annoying. I wasnt able to simplify them. Can we use the average number of (n-1)/2 instead?

You can think of the person going through some permutation of the remaining n-1 elements, looking for the right one. Since the choice of what tool to look at is not affected by the probabilities that those tools are useful, we just consider the average position in this array of n-1 elements, which is actually n/2 (my second mistake).

So the revised answer is 1 + (1-x)*n/2 with the correct x.

Title: Re: Expected number
Post by 1337b4k4 on Jan 21^st, 2009, 9:16pm

on 01/21/09 at 20:48:22, howard roark wrote:

Never mind! I understood......

What if the mechanic actually places the tools in THE BOX INSTEAD OF PUTTING ON THE FLOOR.

I think in this case the expected number of tools examined will be infinite (not defined).

Nope, in this case, since his decision making still is not based on the probabilities, there is simply a 1/(n) chance that any tool he picks up is the right one. We just need to keep doing this over and over again until we see a success. Thus the number of extra examinations has a geometric(1/(n)) distribution, which has an expected value of n. this makes the total expected value 1 + n(1-x)

Title: Re: Expected number
Post by 1337b4k4 on Jan 22^nd, 2009, 12:01am

on 01/21/09 at 22:18:23, howard roark wrote:

In the case where mechanic puts the tools on the floor, I think we get n/2 in the following way....

Number of tools to be examined till we get the correct one:

=1*1/(n-1)+2*1/(n-1)+.....+(n-1)*1/(n-1)

Similarly in the case where he puts them back in the box should be

1*1/n + 2*(1/n)*(1-1/n)+3*(1/n)(1-1/n)(1-1/n)+.........

Did I make any mistake in calculating the above equation??

Looks good to me. The first one simplifies to n/2, and the second simplifies to n.

Title: Re: Expected number
Post by howard roark on Jan 22^nd, 2009, 2:14pm

Is there any way to recover removed messages.

I was trying to modify the question in this thread, but I removed it accidentally.

Title: Re: Expected number
Post by towr on Jan 22^nd, 2009, 2:26pm

on 01/22/09 at 14:14:25, howard roark wrote:

Is there any way to recover removed messages.

I doubt it. Not for us moderators, in any case. And if the records are removed from the database as soon as they're deleted from the board, I doubt William can do anything about it.

Best I can do is edit the first message and add something there to explain the topic.

Quote:

I was trying to modify the question in this thread, but I removed it accidentally.

A lot more than just the initial message seems to be gone, though.
Don't you get a confirmation box when trying to delete a message?