The Matching Car

  1. To pass the time while driving, you start looking for cars with the same three-digit number on their license plates as you have on your own. Assuming three-digit numbers are uniformly distributed among the cars you'll be passing, what is the average number of cars you'll pass before you'll see a matching car?
  2. Now tired of that game, you exercise your memory - what is the average number of cars you'll pass before you'll see a duplicated three-digit number?

Source: Reader Rich Polster.


Solutions were received from Nick Baxter, and Philippe Fondanaiche.
  1. On average, the first matching car will be car 1000. There are 1000 different combinations of three digits. The probability the n-th car is the first match (and the previous n-1 cars weren't matches) is:

    P(n) = (1/1000)(999/1000)^n

    To find the expected value of n, we use the summation:

    E(n) = sum [n*P(n)] 1->infinity
    E(n) = 1000

  2. At least 38 cars must pass by. Philippe's solution:
    The probability Q(x) that the x-th car matches for the first time my own car
    or one of the cars previously identified (all of them being different) is
    defined by:
    
    x=1 Q(1) = 1/1000
    x=2 Q(2) = 2 * 999/1000 * 1/1000
    x=3 Q(3) = 3 * 999/1000 * 998/1000 * 1/1000
    x=4 Q(4) = 4 * 999/1000 * 998/1000 * 997/1000 * 1/1000
    .......
    x any Q(x) = x * 999/1000 *........* (1000-x+1)/1000 * 1/1000
    .....
    For x>1000 Q(x) = 0
    
    We can check that for x=1 to 1000 sum(Q(x)) = 1
    
    The average number N2 of the cars which pass before I see a duplicated three-
    digit number is equal to:
    N2 = Q(1) +2Q(2) + 3Q(3) + 4Q(4)+....xQ(x)+.... - 1 = sum(xQ(x)) - 1 =
    38.3032..
    

Mail to Ken