This week’s Classic asks us to consider an extension to a traffic Riddler problem from the way-back times. The original solution found that the expected number of groups that would form with N cars would be Eg(N) = H(N), where H is the harmonic function.

Here we add an exit to another lane with a one-time only access option, and the problem asks for the expected number of traffic groups in equilibrium in both lanes after the drivers decide to switch or not.

We make the following claims:

• If there are g groups in the first lane, then after the switching there will still be g groups since there is no reason for the lead drivers in the original groups to change anything. They are driving as fast as they can. Therefore the expected number of groups in the first lane is Eg1(N)= H(N) both before and after switching.
• All other drivers except for the lead drivers will switch lanes. They are all speed constrained and will do better by switching, with the worst case being they will end up being stuck behind a faster driver.
• If there were N cars and g groups in lane 1 before switching, then after switching there will be g cars and g groups in the first lane and N-g cars in the second lane.

For interest (not necessary to solve the problem) we will calculate a pdf for the number of groups in the first lane. This can be tricky, but we notice that for a particular ordering of the speeds of the cars like [1,3,4,2,5,6] (where 1 is fastest) that the number of groups is equal to the number of dips to a lower speed in the sequence +1. The groups formed there are { [1], [3], [4,2], [5], [6] } where each time the velocity dips a new group is formed. If we define C(N,k) as the number of ways to form k groups delimited by dips out of the N! permutations of N ordered numbers there is a somewhat well known recursive result that is very helpful:

[You can convince yourself of the above result by writing out the possibilities for N=2,3,4 by hand and seeing how it works! For an explanation involving the original Riddler problem see here.]

Bootstrapping up from C(2,1) = 1 and C(2,2) = 1 we can rapidly calculate the possible ways to make groups of a specific size, Here is a view of C(N,k) for the first few rows of N, and columns of k:

Note that the total number of ways to form groups in each row is N! and so we calculate the function pdf(N,k) by dividing each row by N!:

Here are pdfs of expected number of groups in lane 1 for n=10, 50, 100:

The expected number of groups in both the first and second lanes is (using an elegant result from Josh Silverman here ) :

And as mentioned above Eg1(N) = H(N) as all the intial lead drivers stay in lane 1 so:

Here is a graph of Eg1(N) and Eg2(N) for N= [2,100]. As Josh shows in his post eventually the total number of groups in lanes 1 and 2 will approach e*H(N) for large N, with a limiting expectation of H(N) for lane 1 and (e-1)*H(N) for lane 2.

As mentioned above all the initial group leaders all stay in lane 1 (according to the rules of the problem they only switch lanes if they can increase their speed) and all the rest of the cars move to lane 2: