







CTK Exchange
Monty Phister
guest

Mar2306, 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 onethird 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 nday 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


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


alexb
Charter Member
1809 posts 
Mar2606, 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 = 1p. You are interested in the expectation of the length of a failure run. The general formula is q/p, which in your case is ((n1)/n)/(1/n) = n1. 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 p_{r} of success on an experiment #r is p_{r} = q^{r1}p. The geometric sum shows that all p_{r} add up to 1. For the expectation of the waiting period you have the sum of the terms (r1)p_{r}: S = qp(1 + 2q + 3q^{2} + ...) where, obviously, in the parentheses, you have the derivative of the geometric series, so that S = qp/(1  q)^{2} = q/p.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



mr_homm
Member since May2205

Mar2606, 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 wellknown 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 FFFFFFFFFFFFFFF.... 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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




alexb
Charter Member
1809 posts 
Mar2606, 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. >FFFFFFFFFFFFFFF.... 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


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 






Monty Phiste
guest

Mar2706, 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/p 2. 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?) 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 






mr_homm
Member since May2205

Mar2706, 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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny

