CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

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

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Post Office"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #693
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  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)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 is

pr = 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 that

S = qp/(1 - q)2 = q/p.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Mar-26-06, 12:30 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1809 posts
Mar-26-06, 12:36 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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



  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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!


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
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/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 Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1809 posts
Mar-27-06, 12:52 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Mar-27-06, 07:52 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK