wu :: forums « wu :: forums - Re: Expected number » Welcome, Guest. Please Login or Register. Jun 8th, 2023, 11:01am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, SMQ, Icarus, Eigenray, william wu, Grimbal)    Re: Expected number « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Re: Expected number  (Read 1042 times)
teekyman
Full Member

Gender:
Posts: 199
 Re: Expected number   « on: Jan 21st, 2009, 6:54pm » Quote Modify

The probability that the tool you are currently holding is the tool that you eventually need is 1/p p. 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
 « Last Edit: Jan 21st, 2009, 8:04pm by teekyman » IP Logged
teekyman
Full Member

Gender:
Posts: 199
 Re: Expected number   « Reply #1 on: Jan 21st, 2009, 8:02pm » Quote Modify

on Jan 21st, 2009, 7:26pm, 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 Jan 21st, 2009, 7:40pm, 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.
 IP Logged
teekyman
Full Member

Gender:
Posts: 199
 Re: Expected number   « Reply #2 on: Jan 21st, 2009, 9:16pm » Quote Modify

on Jan 21st, 2009, 8:48pm, 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)
 IP Logged
teekyman
Full Member

Gender:
Posts: 199
 Re: Expected number   « Reply #3 on: Jan 22nd, 2009, 12:01am » Quote Modify

on Jan 21st, 2009, 10:18pm, 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.
 IP Logged
howard roark
Full Member

Posts: 241
 Re: Expected number   « Reply #4 on: Jan 22nd, 2009, 2:14pm » Quote Modify

Is there any way to recover removed messages.

I was trying to modify the question in this thread, but I removed it accidentally.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Expected number   « Reply #5 on: Jan 22nd, 2009, 2:26pm » Quote Modify

on Jan 22nd, 2009, 2:14pm, 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?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »