CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site

CTK Exchange

 Subject: "Post Office" Previous Topic | Next Topic
 Conferences The CTK Exchange This and that Topic #693 Printer-friendly copy     Email this topic to a friend Reading Topic #693
Monty Phister
guest
Mar-23-06, 01:29 PM (EST)

"Post Office"

 Dear Alex, There is this editor who goes from place to place in times past, present, and future, and not long ago he visited a small country near Transylvania where the King had found a way to save money in the Post Office. Since people who can't read take less pay, he arranged that only one-third of postal workers were literate. The editor saw that if the letter was first handled by a reader, it was delivered in one day. Otherwise, the next day it was again sorted by a postal worker. And our editor discovered that the average time for a letter to be delivered was 3 days. A similar hiring philosophy was used in other nearby kingdoms. Where 1/5 of the workers could read, the average delivery time was 5 days. Where 1/20 could read, it was 20 days. With the help of a little mathematics, the editor discovered that, if one of n workers was literate, the letters were delivered on an average in n days. In his book "How to Solve It" George Polya said that once one had solved a problem, one should look back and see whether the answer was perhaps obvious, or whether there was a simpler way of solving it. If the editor's analysis is correct, and the n-day delivery for 1/n literate sorters is correct, the answer is so elegant it'seems that it ought somehow be obvious. But your friendly editor can't see how. Do you, by any chance? Regards, Monty Phister

Subject     Author     Message Date     ID
Post Office Monty Phister Mar-23-06 TOP
RE: Post Office alexb Mar-26-06 1
RE: Post Office mr_homm Mar-26-06 2
RE: Post Office alexb Mar-26-06 3
RE: Post Office Monty Phister Mar-26-06 4
RE: Post Office Monty Phiste Mar-27-06 5
RE: Post Office alexb Mar-27-06 6
RE: Post Office mr_homm Mar-27-06 7

 Conferences | Forums | Topics | Previous Topic | Next Topic
alexb
Charter Member
1809 posts
Mar-26-06, 08:29 AM (EST)

1. "RE: Post Office"
In response to message #0

 Your problem is known to have what's called "geometric distribution". In general, you run experiments with the probability of success p and that of failure q = 1-p. You are interested in the expectation of the length of a failure run. The general formula is q/p, which in your case is ((n-1)/n)/(1/n) = n-1. The number you are looking for is that+1. You can find everything in Feller's book, v. 1. The result is pretty well known. I do not find it intuitive at all. Further, there some apparent paradoxes related to the waiting time.Probability pr of success on an experiment #r ispr = qr-1p.The geometric sum shows that all pr add up to 1.For the expectation of the waiting period you have the sum of the terms (r-1)pr:S = qp(1 + 2q + 3q2 + ...)where, obviously, in the parentheses, you have the derivative of the geometric series, so thatS = qp/(1 - q)2 = q/p.

mr_homm
Member since May-22-05
Mar-26-06, 12:30 PM (EST)

2. "RE: Post Office"
In response to message #1

 Hi Alex,Here is an alternate way of looking at it, which does not involve the use of any specific formulas, only the fact that (as is both obvious and well-known for a geometric distribution) this process has no memory. Chances of success are independent of past history.Instead of following single letter through the post office, think of generating a random sequence of N successes and failures, such as FFFSFFSSFFFFFFSFFSFFF..., where there are Nq failures and Np successes. (Of course, Nq and Np are only expected values, but we are going to look at very large N, so they become firm values in the limit.) Now consider the successes as positions to cut the sequence and failures as the "substance" being cut, so that the string looks like FFF|FF||FFFFF|FF|FFF.... Since a string of Nq failures is cut by Np successes into Np+1 pieces, the average length of each piece must be Nq/(Np+1), and in the limit of large N, this goes to q/p.Since the process has no memory, one can start counting failures from ANY point (as long as the point is chosen without reference to the part ot the sequence that is further to the right), and find the same expected waiting time. For clarity, choose any particular success as the starting point. Then it is certain that we have not landed in the middle of a string of failures, so we are at the start of one. Thus the expected number of failures before the next success is simply the average mentioned above, q/p.The time the letter spends in the post office will then by q/p + 1, since one more day is needed for the success to occur. Your way is briefer, but just for fun, I decided to try to set up a model for the probability and then find a way to look at the model that makes the answer come out without a formal analysis.--Stuart Anderson

alexb
Charter Member
1809 posts
Mar-26-06, 12:36 PM (EST)

3. "RE: Post Office"
In response to message #2

 Stuart, thank you.In all likelihood your explanation is what Monty was looking for.>FFF|FF||FFFFF|FF|FFF.... Since a string of Nq failures is >cut by Np successes into Np+1 pieces, the average length of >each piece must be Nq/(Np+1), and in the limit of large N, >this goes to q/p. Alex

Monty Phister
guest
Mar-26-06, 05:11 PM (EST)

4. "RE: Post Office"
In response to message #3

 Great!!! Just what I hoped would be possible!

Monty Phiste
guest
Mar-27-06, 11:55 AM (EST)

5. "RE: Post Office"
In response to message #4

 Something else occurred to me.Isn't the 1/n statement better than the "classical" p/q via the following argument?1. They are equivalent when n=q/p2. The first statement is more elegant, having only one parameter instead of two.3. The p/q statement implies that the probability must be a rational number. But in fact it can be any real number, as is more or less implied by 1/n. For example, n may equal pi (so q=pi, p=1?)

alexb
Charter Member
1809 posts
Mar-27-06, 12:52 PM (EST)

6. "RE: Post Office"
In response to message #5

 I am sure that the ancient Egyptians would have voted for your suggestion with two hands.P.S. The p/q statement does not imply that the probability must be a rational number.

mr_homm
Member since May-22-05
Mar-27-06, 07:52 PM (EST)

7. "RE: Post Office"
In response to message #5

 Hi Monty,>1. They are equivalent when n=q/p >2. The first statement is more elegant, having only one >parameter instead of two. I agree here!>3. The p/q statement implies that the probability must be a >rational number. But in fact it can be any real number, as >is more or less implied by 1/n. For example, n may equal pi >(so q=pi, p=1?) Here, I see a little problem. Alex has mentioned already that p and q need not be integers, so p/q need not be rational. I would also like to point out that you can't have q=pi, p=1 since p and q are probabilities, so 0 <= p <= 1 and 0 <= q <= 1. Since p+q = 1, you would get q = pi/(pi+1) and p = 1/(pi+1).I assume you're planning to use this on GnarlyMath. It looks like the 1/n version of the explanation above in post #3 would be just about right for your publication, better than the p/q version. Have fun with it!--Stuart Anderson