The Lost Luggage Problem

Here’s a little brainteaser to think about if the Super Bowl ends up being a bit dull. Imagine that you are standing at the baggage carousel at an airport waiting for your bag. A percentage x of the bags from your flight have already appeared on the carousel and yours is not among them. How large does x have to be before there is a probability greater than one half that your bag has been lost by the airline?

Of course, we need to make a few assumptions before we can attempt a proper mathematical analysis of the situation.

First, you can assume that the airline loses two percent of all the bags that it handles. According to this 2006 article from the USA Today, this figure is roughly accurate for the least reliable U.S. airlines. The industry average is closer to .63 percent, but that number is ugly and harder to work with.

We will also assume that your bag is as likely to occupy any place in line as any other. I think it also simplifies the computations if you assume there are exactly 100 bags. If you number the bags from one to 100 with one being the first bag to appear and one hundred being the last, then the number assigned to your bag is chosen randomly from the numbers between one and one hundred.

Using Bayes’ Theorem I’ve managed to cook up my own little formula for the probability that your bag has been lost given that x percent of the bags have appeared without yours being among them. My formula gives the correct answers for the extreme cases. That is, if all of the bags have appeared then my formula says there is probability one that your bag is not there. And when none of the bags have yet appeared my formula reutrns a probability of 1/50, or two percent, exactly as it should be.

Still, the answer it gives me to the specific question I posed above seems a bit hard to believe. So I figured I would turn it over to all of you. Let me know what you come up with!

Comments

  1. #1 Markk
    February 2, 2008

    Well off the top of my head, you could change the problem a little to get an idea. Suppose there are 98 bags instead of 100. There are now 100 possibilities – bag in positions 1-98 or lost which we will call 99 or 100. Not quite right (There is no ordering in the lost bags) but close enough for an estimate. Each possibility has a 1% chance of happening. When would you have a 50% chance that your bag is in the lost slot? In this case you would have to have 96 bags gone – i.e. there would be 4 places left when you would have 50% chance of having a lost bag. You could do this exactly with 98/100 as the odds for each place in the bag line and 2% as the last place, but the location would be similar, about 2 bags left would bring you above 50% chance.

  2. #2 ned rosen
    February 2, 2008

    Given that you have seen portion x of the bags without seeing your own, the probability that yours is lost is, by my calculation, 0.02 / (1 – 0.98x). I drew a tree with first branch being Lost vs. NotLost (with prob’s 0.02 and 0.98) and next branch Seen vs NotSeen (with conditional probabilities 0 and 1 given Lost, and x and (1-x) given NotLost). Multiplying along the branches gives the values to plug into:

    P(L | NS) = P (L and NS) / P (NS) = 0.02 / (0.02 + 0.98(1-x)) = 0.02/ (1 – 0.98x).

    So with P ( L | NS) = 0.5 we get x = 0.96/ 0.98 which is about 0.98, so you are more likely to have lost it than not, only after 98% of the bags have gone by. That does seem longer than you might think but for me it is probably the lousy mood I’m in when waiting for luggage that makes me assume the worst :)

  3. #3 ned rosen
    February 2, 2008

    very nice Markk! That shows exactly why it is x = 96/98, and also how it generalizes to

    x = (1-2q)/(1-q)

    with q = luggage loss rate, for the point x at which it is more likely to be lost than not.

  4. #4 _Arthur
    February 2, 2008

    The chances for any aircraft to contain a bomb are very small, and the chances for an aircraft to contain TWO bombs are greatly smaller. So, to have a safe flight, just smuggle in a bomb, and you’ll be safe.

  5. #5 Jason Rosenhouse
    February 2, 2008

    ned rosen-

    That’s precisely the formula I got.

    Markk-

    That’s an interesting way of looking at it.

    Arthur-

    That reminds me of the joke about the person who, upon learning that ninety percent of all accidents occur within a five mile radius of the home, decided to move.

  6. #6 royiles
    February 2, 2008

    As the bags progressively appear, won’t the probability that yours has been stolen become different from the probability that it hasn’t been?

  7. #7 RogerP
    February 3, 2008

    Presumably, bags are lost at random in this model, which is not the case at Johannesburg’s O R Tambo airport. If your luggage contains valuables, it is more likely to be pilfered than lost.

    How do the thieves know which bags contain valuables?

    Easy. The security staff that X-rays luggage are in cahoots with the thieves.

  8. #8 scienceteacherinexile
    February 3, 2008

    RogerP:
    I have lived in Jo’burg for almost 10 years now.
    I learned early on when I was traveling back and forth a lot more often to carry on any valuables. Actually was advised to, so I never learned the hard way.
    I remember the investigative report on TV here a few years ago where they caught the baggage handlers pilfering the luggage. It was more blatant than you could believe.
    However, at one stage, at least one of my bags was lost on 50% of all my flights (flying SA airways and American airways) to and from Jo’burg to Dallas. British Airways has never lost one of my bags even with strange connections (like landing at Heathrow and departing from Gatwick and then changing planes again in Chicago).
    And how did you manage to get the name of the airport right? That is, if they haven’t changed it again this week!!

  9. #9 Tegumai Bopsulai, FCD
    February 3, 2008

    First, you can assume that the airline loses two percent of all the bags that it handles. According to this 2006 article from the USA Today, this figure is roughly accurate for the least reliable U.S. airlines. The industry average is closer to .63 percent, but that number is ugly and harder to work with.

    Have you actually flown anywhere lately? The last flight I took, about half of the passengers did not have their bags come out on the conveyor, and about half the bags that did come out did not belong to passengers on that flight. Are those numbers for bags that get lost at all, or bags that are never reunited with their owners? Flying has become very unpleasant.

  10. #10 Matt Daws
    February 4, 2008

    Tim Gowers also seems to discussing probability at the moment. In particular, this post might interest readers here.

  11. #11 fjgiie
    February 4, 2008

    After 51 bags arrive. (or there abouts)

  12. #12 Michael Ralston
    February 5, 2008

    … actually, thinking about it, it makes perfect sense.

    You aren’t getting useful information from the first few bags to arrive, really.

    Your initial expectation is that about two bags are lost. So the naive estimate would be that you’d need to see 96 bags go by for the number of bags you expect to still come to be equal to the number you expect to see lost, since you assume your bag is not special in that respect.

    And then we factor in that sometimes only one bag is lost, and in those occasions when several are lost, we only discover that by suddenly getting surprised when the bags stop early… it makes sense that it’d take longer than the naive estimate says.

  13. #13 Jason Rosenhouse
    February 5, 2008

    Matt-

    Thanks for the link. I was not aware that Gowers had a blog.

  14. #14 ctw
    February 5, 2008

    For anyone still interested, here is the full solution (subject, of course, to possible errors).

    Let L = {your bag lost}, {N=n} = {n bags appear, none yours}, M = number of bags checked, and q = the a priori probability that a specific bag is lost.

    Then the conditional probability that your bag is lost given that n bags, none yours, has appeared is:

    P(L|N=n) = P{N=n|L} P{L}/P{N=n} = P{N=n|L}q/(P{N=n|L}q + P{N=n|notL}(1-q))

    The conditional probability that n bags appear given that your bag is lost is the cumulative binomial probability that no more than M-1-n other bags were lost (M-1 because your bag is given as lost):

    P{N=n|L} = sum(k,0,M-1-n)[B(M-1,k) q**k (1-q)**(M-1-k)]

    if n not equal to M, 0 otherwise (M bags can’t appear if yours was lost). (The symbol sum(k,0,m)[f(k)] means “sum f(k) for k from 0 to m”; B is the binomial coefficient).

    The conditional probability that n bags appear given that your bag is not lost is the cumulative probability for k &lt M-n that no more than k of the M-1-n other bags were lost and that your bag is one of those that has not appeared:

    P{N=n|notL} = sum(k,0,M-1-n)[B(M-1,k) q**k (1-q)**(M-1-k)(M-k-n)/(M-k)]

    if n not equal to M, 0 otherwise (only M-1 bags not yours can appear if yours wasn’t lost).

    For small q and n &lt &lt M, P{N=n|L} is approximately 1 and P{N=n|notL} is approximately 1-n/M. Then

    P{L|N=n} ~ q/((q+(1-n/M)(1-q)) = 1/(1 + (1-n/M)(1-q)/q) as others have said.

    Here are some computed values for the exact (Ex) and approximate (App) formulas:

    n___Ex___App

    100 Undef 1.00
    99__0.67__0.67
    98__0.60__0.51
    97__0.53__0.41
    96__0.45__0.34
    90__0.22__0.17
    0___0.02__0.02

    Both the exact and approximate calculations are correct for n=0. The approximation is incorrect for n=100 because the conditional probabilities for L and notL are both zero (since in neither case can an M-th bag appear that is not your bag) and P{L|N=n} is undefined. The approximtion is not too good for roughly 90 &lt n &lt 99, hence the decrepancies. It is exact at n=M-1.

    - Charles

  15. #15 david
    February 10, 2008

    i was gonna say x(+1)/3. i am certainly not a mathemetician! check out my website!

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.