20
$\begingroup$

The following is an interview question:

A certain highway has two lanes in my direction. Whenever traffic moves, if I'm in the left lane I switch to the right with probability 60%. If I'm in the right lane I switch back to the left lane with probability 80%, because it's supposed to be faster. Over the long term, what fraction of the time do I expect to spend in the left lane?

My thought process:

Let L denote being in left lane, then

$P(L) = P(L|R)P(R) + P(L|L)P(L) = 0.8\times 0.5 + 0.4\times 0.5 = 0.6$

Is this correct?

$\endgroup$
5
  • 4
    $\begingroup$ Note that you are inputting the value you are trying to solve for as a defined numerical value, but if you knew that, you wouldn't need to solve for anything in the first place. You input P(L)=0.5 into the equation, and then find that P(L)=0.6, which of course makes no sense. $\endgroup$ Aug 2, 2023 at 14:36
  • 1
    $\begingroup$ @NuclearHoagie, that can make sense as the first step of an iteration: if initially the cars are evenly split, then at the next stage they are split 60-40, etc. $\endgroup$
    – Matt F.
    Aug 2, 2023 at 15:08
  • 2
    $\begingroup$ ... and then the next iteration is 0.56-0.64, then 0.576-0.424 and eventually moving towards $\frac47-\frac37$ i.e. about 0.5714-0.4286 $\endgroup$
    – Henry
    Aug 3, 2023 at 11:58
  • 10
    $\begingroup$ I would maintain this question has no definite answer, because it depends on when and for how long "the traffic moves." For instance, if it moves for much longer periods when you are in the left lane, then you will spend almost all your time in the left lane. At a minimum, then, any correct answer must articulate the additional assumptions needed to justify it. The need to analyze an ill-defined or ill-posed question and the ability to identify implicit assumptions is usually what interview questions are probing -- not the ability to provide a textbook answer. $\endgroup$
    – whuber
    Aug 3, 2023 at 12:30
  • 4
    $\begingroup$ The seemingly innocuous precision "because it's supposed to be faster." appears to support @whuber 's comment. $\endgroup$
    – Stef
    Aug 3, 2023 at 14:36

6 Answers 6

36
$\begingroup$

You can express this is a two-state Markov chain and compute the steady state.

$P = \begin{pmatrix}0.4 & 0.6\\\ 0.8 & 0.2\end{pmatrix} = $ probability transition matrix.

$s = (s_L, s_R) = $ steady state vector.

$sP = s \rightarrow $

$(s_L, s_R)\begin{pmatrix}0.4 & 0.6\\\ 0.8 & 0.2\end{pmatrix}=(s_L, s_R) \rightarrow$

$(0.4s_L + 0.8s_R, 0.6s_L + 0.2s_R) = (s_L, s_R) \rightarrow$

$s_L = \frac{4}{3}s_R$

Together with the constraint that $s_L + s_R = 1$, we finish with

$s_L = \frac{4}{7}, s_R = \frac{3}{7}$.

$\endgroup$
2
  • 2
    $\begingroup$ Yup. Basically the same as the other answer but it extends more easily to more than two states :) $\endgroup$
    – hobbs
    Aug 3, 2023 at 2:41
  • 2
    $\begingroup$ You could consider each moment to have a probability $p$ of traffic moving, in which case you have ((0.4p+(1-p), 0.6p)(0.8p, 0.2p+(1-p))). It is instructive to consider why this doesn't change the answer. $\endgroup$ Aug 6, 2023 at 3:13
32
$\begingroup$

I would solve this as $$L=\frac25L + \frac45(1-L),$$ i.e. “the probability of being in the left lane on the next move is 2/5 the chance you were in the left lane on this move, plus 4/5 the chance you were in the right lane on this move.”

In that case $L=4/7$.

$\endgroup$
12
$\begingroup$

Assume that you spend an equal amount of time in either lane on average after switching before the traffic moves again. The fraction of time spent on each side is given by the ratio of the probabilities of switching from the other side to that one - in this case, 60%:80% or 3:4 right to left. So the fraction of time spent in the left lane is 4/7.

$\endgroup$
2
  • 5
    $\begingroup$ Hi. Could you please expand on your reasoning? I agree with the result of 4/7, but I don't understand how you arrive at this result. $\endgroup$
    – Stef
    Aug 3, 2023 at 11:37
  • 1
    $\begingroup$ This assumption re: equal amounts of time is important. The result is an expectation that depends upon an assumption. "Long Term" may mean years or minutes. FFT should not be a consideration even if movement is remotely periodic. $\endgroup$
    – mckenzm
    Aug 5, 2023 at 9:44
4
$\begingroup$

In a steady-state situation, the flow to the left lane equals the flow to the right lane, so $0.8 R = 0.6L$. It follows that $L = \frac{0.8}{0.8+0.6}=\frac 4 7$ and $R = \frac 3 7$.

$\endgroup$
3
$\begingroup$

When the traffic is not completely jammed but slowly moving, crazy drivers still tend to change lanes frequently. For such a process of driving, I would rather use a continuous-time Markov chain and specify transition rates (the probability of transition per unit time) or half-lifetimes (the time after which I'm still in the same lane with probability 1/2) instead of transition probabilities (which are for a process having discrete time steps). For example, I would say

If I'm in the left lane I switch to the right with a transition rate of 60% per minute.

A transition rate of $\lambda_L = 0.6 \; \mathrm{min}^{-1}$ means that if I'm in the left lane now ($\xi(t) = L$), the probability of changing lane in an infinitesimally small amount of time $dt$ is $$P\big[\xi(t+dt)=R\big|\xi(t)=L \big] = \lambda_L dt,$$ and the probability of not transiting and still staying in the same lane after say the first $t = 1 \; \mathrm{minute}$ is $$P\big[\xi(t)=L \mbox{ and not transiting back and forth meanwhile} \big| \xi(0)=0 \big] = e^{-λ_L t} \approx 0.549.$$ Then the probability of making the first transition between $t$ and $t+dt$ is the product of the two expressions above, so the expected time of first transition is the integral $$T_L = \int_0^\infty t \lambda_L e^{-λ_L t} \, dt = \frac{1}{\lambda_L} \approx 1.667 \; \mathrm{min}.$$

Once I have switched to the right lane, I expect to spend there an average of $T_R = 1/\lambda_R = 1.25 \mathrm{min}$. Thus, over the long term, the fraction of time I expect to spend in the left lane is

$R_L = \frac{T_L}{T_L+T_R} = \frac{1}{1 + \lambda_L / \lambda_R} = \frac{4}{7},$

which is exactly the same as for the case of discrete Markov chain.

$\endgroup$
1
$\begingroup$
80% of the time you switch to the left lane => 0.8
60% of the time you switch to the right lane => 0.6
Assumption: Traffic always moving, no time considered to be "inbetween" lanes.

Then:
Total time in either lane: 0.8 + 0.6 = 1.4

Then:
% of time in right lane: 0.6 / 1.4
==> 0.3 / 0.7 
==> 3 / 7

% of time in left lane: 0.8 / 1.4
==> 0.4 / 0.7 
==> 4 / 7
$\endgroup$
3
  • 1
    $\begingroup$ Where do the first two lines come from? They aren't asserted in the problem. $\endgroup$
    – whuber
    Aug 4, 2023 at 21:16
  • $\begingroup$ @whuber which part of the lines are you claiming is not asserted? The assumption is given based off the wording of the problem. Based off this assumption and the problem statement, we can deduce the effective result which is the first two lines. $\endgroup$
    – Jon
    Aug 7, 2023 at 16:32
  • $\begingroup$ @whuber I've tweaked the wording of the first two statements $\endgroup$
    – Jon
    Aug 7, 2023 at 16:35

Your Answer

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

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