rec.puzzles Archive

At dusk you want to turn on your headlights when half of the oncoming drivers have theirs on, judging only...

probability/headlights

Problem

At dusk you want to turn on your headlights when half of the oncoming
drivers have theirs on, judging only by runs of oncoming cars with
lights on; how long a run should be your trigger?

[ Editor: the title sentence above is a summary; the original posting
follows. ]

We're driving along a highway.  Lots of traffic coming the other
way, volume roughly constant.  It's getting toward dusk.  Pretty
soon, more and more of the oncoming cars have their lights on.
We want to turn *our* lights on just at the point when half of the
drivers have put their lights on.  To be difficult, we want to
guess when this point is by counting strings of oncoming cars
with their lights on, and switching ours on when we get
to N.  An oncoming car with lights off resets the count to zero.
What's the choice of N which gives the best chance of achieving
the 50% criteria?  Does N depend on the volume of oncoming
traffic?  (Surely yes.)

This is a fairly vague wording of the problem, I admit.  It's
possible to pin down what's meant by the 50% point a little better:
Start counting all cars (C), and cars with headlights on (H),
well before dusk, at time t=0.  At some time when it's getting
pretty dark, one will find a time t=T when H = C/2.  The 50% time,
in retrospect, was t=T/2.  We assume that the volume of oncoming
traffic was roughly constant throughout the interval.

The goal, then, is to define how many oncoming cars in a row, all
with headlights on, should be the trigger for me to turn on my
lights at a time which most closely estimates T/2.

-- D. F. Munro <{big machine}!aluxp!aluxa!dfm>
Show solution
The best N grows like the logarithm of the traffic volume, so yes, it
depends on the volume.  If M is the number of oncoming cars that pass
you while the fraction of lit cars rises from 0 to 1, a good choice is
the N with

  (N + 1) * 2^(N+1)  roughly equal to  1.4 M,

that is, N is about log2(M) - log2(log2(M)).  For a linear rise of the
lit fraction this gives N = 3 for M = 100, N = 6 for M = 1000, N = 9
for M = 10,000 and N = 12 for M = 100,000.

The model.  The original question is vague, so here is how I read it.
Cars come at a constant rate.  Car number k has its lights on with
probability p_k, independently of the others, where p_k rises from 0 to
1 over the M cars of dusk; the "50% point" is the car where p_k = 1/2.
You switch on at the end of the first run of N consecutive lit cars.
The trigger car K is random, and we want K/M close to the 50% point.

Exact computation.  The distribution of K can be computed exactly by a
dynamic program over the length of the current run (a C++ program;
the probabilities below are exact sums, not simulation).  For the
linear rise p_k = k/M, the 50% point is K/M = 0.5:

          best N   median K/M   rms error of K/M   P(|K/M - .5| < .1)
  M = 100    3       0.45          0.14               0.54
  M = 1000   6       0.51          0.09               0.73
  M = 10^4   9       0.52          0.07               0.88
  M = 10^5  12       0.51          0.05               0.96

One step either side of the best N is clearly worse; for example with
M = 10,000, N = 8 triggers at median 0.47 and N = 10 at 0.56, with
rms errors 0.076 and 0.082 against 0.066 for N = 9, and N = 7 or
N = 11 already have rms errors of 0.11.

Where the rule of thumb comes from.  An unlit car followed by N lit
cars begins at a given car with probability about (1 - p) p^N, so the
expected number of runs completed before the 50% point is about

  M * integral from 0 to 1/2 of x^N (1 - x) dx  ~  M / ((N+1) 2^(N+1)).

The trigger is at the 50% point in the median when this expected count
is about ln 2 = 0.69, which gives (N + 1) 2^(N+1) = 1.4 M.

The answer also depends on how the lit fraction rises, not only on the
volume.  If the rise is S-shaped (a logistic curve, steep in the middle
of dusk), short runs become rare until shortly before the 50% point and
the best N is smaller: with M = 1000 it is 5 (rms error 0.04) and with
M = 10,000 it is 7 or 8 (rms error 0.03).  In every case, though, a
tenfold increase in traffic adds about three to the best N, because at
p = 1/2 a run of N lit cars takes about 2^(N+1) cars to turn up.

The model also assumes drivers switch on independently.  If lit cars
come in bunches, long runs come earlier, which would argue for a
somewhat larger N; I have not modelled that.

-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the material collected earlier follows. ]

[ Editor: the only reply collected: ]

Imagine how convenient it would be if everyone had your gizmo.  Then it
wouldn't matter whether it worked or not.  Everyone would drive in the
dark.

-- Jim Potter <jp@lanl.arpa>