3
$\begingroup$

Staying in the traffic again this morning, I decided to find a mathematical motivation behind me always being in the slowest lane.

Consider the following formalization: there are 4 empty lanes and 100000 cars. For each car in turn we choose one of the four lanes uniformly at random, and add the car at the end of that lane.

Now, you are in one of those cars. What is the probability that you end up in the longest late? To remove ambiguity, let's say that if two lanes have the same length, the leftmost one is the longest.

Now consider two solutions:

  1. After all the cars are assigned, let's rearrange the lanes such that the longest lane is the first one. Your car was originally assigned to each of the lanes with equal probability. What was the chance it was assigned to the first lane? Well, clearly it was exactly 25%. Hence the answer is 25%.

  2. The probability your car is in a certain lane after all the cars are assigned is equal to the length of that lane divided by the total number of cars. Almost certainly the longest lane has more than 25% of the cars, hence the answer is strictly larger than 25%.

Which of the two solutions is wrong?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Are you that Ishamael? [readies balefire] $\endgroup$
    – Rand al'Thor
    Dec 12, 2016 at 20:52
  • 1
    $\begingroup$ If your car is the last car placed and the lane lengths are currently (in order): [24999, 25000, 25000, 25000], then there is a 100% probability that you will be added to the longest lane. $\endgroup$
    – Ian MacDonald
    Dec 12, 2016 at 20:58
  • $\begingroup$ Funny but true: The very fact that you are in a line (a traffic lane, a window queue, etc.) increases the chance of that line being the longest. The random assignment system in this puzzle exaggerates that chance because nobody has the choice of avoiding an already crowded lane. At least, in most cases, you still have more than 1/2 chance of not being in the longest line (but not as high as 3/4, which would be nice, in this case). $\endgroup$
    – humn
    Dec 13, 2016 at 6:20
  • 2
    $\begingroup$ Had to check your profile to see if you lived in the DC metro too :P My sympathies.. I've come up with a few ideas for traffic models while commuting, I like your idea of turning it into a puzzle! $\endgroup$
    – user812786
    Dec 13, 2016 at 14:44

5 Answers 5

Reset to default
4
$\begingroup$

The first line of reasoning is wrong: the order in which you rearrange them depends on the locations of all the cars, including your own.

It's clearer why the 25% argument doesn't hold if you repeat the problem with only 1 car instead of 100,000, so the probability of you being in the longest lane is 100%.

Improve this answer
$\endgroup$
0
2
$\begingroup$

I think the answer is always more than 25%, but not quite because of your line of reasoning.

Assuming you are not the last car, I would apply a weighted probability of any car being in each lane AFTER all cars have been placed. This is the proportion of the total car population residing in that lane. For instance, consider 4 lanes (A, B, C and D) with cars 200, 100, 60, 0. The respective weighted probabilities of your car being in each lane would be 56%, 28%, 16% and 0% (duh).

In this case, the probability of your car being in the longest lane can never go below 25% (all lanes equal), but can go up to 100% (all cars in same lane).

Improve this answer
$\endgroup$
4
  • $\begingroup$ ^vote with a note: How is this different than the puzzle's "solution" # 2? $\endgroup$
    – humn
    Dec 13, 2016 at 6:10
  • $\begingroup$ This proves that the chances are highers than 25% for that tiny subset of probabilities relating to the case "360 cars" (4 possibilities out of 360X360X360X360). It won't prove that the total odds for 360 cars are over 25%. $\endgroup$
    – stack reader
    Dec 13, 2016 at 6:11
  • $\begingroup$ @humn, crap, after more careful re-reading I realised I just reworded his answer. I misunderstood it before that. Shame. $\endgroup$
    – Xenocacia
    Dec 13, 2016 at 6:16
  • $\begingroup$ @stackreader: sorry, I don't follow your question. I took an arbitrary number as an example but thought it would be pretty straightforward to see how the logic applied to any number. $\endgroup$
    – Xenocacia
    Dec 13, 2016 at 6:18
1
$\begingroup$

The average probability would be a tremendous pain to calculate, but it is safe to say that it will always be over 25%. The probability will vary based on the total number of cars and it is probably safe to assume that the higher the number of cars there is, the closer to 25% you will go.

1 car : 100%
2 cars : 62.5%(chance to be in leftmost if equal + chance to be in same)
3 cars : 46.875%(chance to be in leftmost if equal + chance to be in same)
9999999 cars : >25% With a high number of cars, the chance of any lane to have a number of cars in common is extremely low and the % will be very close to 25%

Improve this answer
$\endgroup$
1
$\begingroup$

Consider $5$ cars. The possibilities are lanes with $5, 41, 32, 311, 221, 2111$ cars in them. The respective probabilities of you being in the longest lane for each are $100, 80, 60, 60, 40, 40$. Sum is $380$, $6$ cases, so you have a $63.333...$ percent chance of being in the longest lane. This doesn't look easy for the case $n=100,000$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 5, 41, 32 etc are not equally likely. For instance, if number of cars was just three, 21 would have been three times as likely as 111, which in turn would be twice as likely as 3 $\endgroup$
    – Ishamael
    Dec 13, 2016 at 22:21
0
$\begingroup$

1 is wrong. While it is really 25% if none is empty (due to the symmetry between any given 4 cars on different lanes) otherwise you're guaranteed to be in a non-empty one, so your chance ends up being more than 25%. 1 relies on your 25% chance of being assigned to a certain lane, and in turn, that lane's 25% chance of being the longest on average under "normal" circumstances. However, the longest lane can only be determined at the end, not right after you've been assigned. For all we know, one or more lanes could be empty.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Let's say that after we assigned all the card, we observed that no line is empty. Are we in the longest line with 25 chance? (the answer is still no) $\endgroup$
    – Ishamael
    Dec 20, 2016 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.