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?

$\endgroup$
  • 3
    $\begingroup$ Are you that Ishamael? [readies balefire] $\endgroup$ – Rand al'Thor Dec 12 '16 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 '16 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 '16 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 '16 at 14:44
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%.

$\endgroup$
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).

$\endgroup$
  • $\begingroup$ ^vote with a note: How is this different than the puzzle's "solution" # 2? $\endgroup$ – humn Dec 13 '16 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 '16 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 '16 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 '16 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%

$\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$.

$\endgroup$
  • 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 '16 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.

$\endgroup$
  • $\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 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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