Peak Fall in Riddler Nation
Probability, Calculus; Difficulty: medium
When Will the Fall Colors Peak?
This week’s Riddler Classic is a probability question that requires a bit of calculus for an accurate answer; but the problem can also be discretized for a reasonably accurate answer. The Classic reproduced:
It’s peak fall foliage season in Riddler Nation, where the trees change color in a rather particular way. Each tree independently begins changing color at a random time between the autumnal equinox and the winter solstice. Then, at a random later time for each tree — between when that tree’s leaves began changing color and the winter solstice — the leaves of that tree will all fall off at once.
At a certain time of year, the fraction of trees with changing leaves will peak. What is this maximal fraction?
*spoiler alert* solution and answer follow below
Solution
Let’s call the time interval between equinox and solstice 1 unit of time (without loss of generality). There are two uniform random distributions at play here: the first between 0 and 1 that determines the time say \(x\), when color change starts for a tree; The second, the time say \(y\) between \(x\) and 1 when the leaves fall off.
The density functions for the two are below but the key to note is that for a uniform random distribution, the probability of the event in a window is the ratio of the size of that window to the overall max possible window size.
\begin{align*}
f(x) &= 1 ,\ \ \ 0 \leq x \leq 1 \quad h(y) = \frac{1}{1-x}, \ \ \ x \leq y \leq 1 \\
\end{align*}
Let’s evaluate the probability \(P(t) \) that a single tree is in the midst of color change at a time \(t\) between 0 and 1.
For a tree to be changing color at time \(t\), the color change should have been initiated at time \(X\) prior to \(t\). Also the leaves falling off should occur at a time \(y\) after t. We can easily calculate the probability that \(X < t\) as equal to \(t\) : the fraction of the total time feasible for the color change. However the probability that \( y > t \) depends on the specific \(X\) when color change started. So we condition on the time \(X\) the color change started: we assume it to have been at time between \(x\) and \(x + dx \), an infinitesimal interval \(dx\) after \(x\). This is illustrated below:
Mathematically:
\begin{align*}
P(t) &= P(\ X<t \ \cap \ y > t \ ) \\
&= \int\limits_{x = 0}^{1}P(\ X<t \ \cap \ y > t \ | \ x \leq X \leq x + dx) \ . \ P(x \leq X \leq x + dx) \\
&= \int\limits_{x = 0}^{t} \underbrace{ P( y > t \ | \ x \leq X \leq x + dx)}_{\textit{(1-t) region is feasible out of (1-x)}} \ . \underbrace{\ P(x \leq X \leq x + dx)}_{\textit{this is just dx}} \\
&= \int\limits_{x = 0}^{t} \frac{1-t}{1-x} \ . \ dx \\
&= (1-t)\int_{x = 0}^{t}\frac{dx}{1-x} \ = \ (1-t) \biggr [ – \ln (1-x) \biggr ]_0^t \\
P(t) &= (t-1) \ \ln (1-t) \\
\end{align*}
This probability as a function of time is plotted below:
Determining the time \(t\) when \(P(t) \) is maximum is easily obtained by differentiating \(P(t)\) and setting it to zero.
\begin{align*}
P(t) &= (t-1) \ \ln (1-t) \\
P'(t) &= \ln (1-t) + 1 = 0 \\
&\Rightarrow t = 1 – \frac{1}{e} \approx 0.6321 \quad &&\textit{is an extremum} \\ \frac{}{}
P”(t) &= \frac{-1}{1-t} \quad &&\textit{always negative, implying extremum is a maximum} \\
P(t)_{max} &= P(1-\frac{1}{e}) = -\frac{1}{e}\ln\frac{1}{e} \\
P(t)_{max} &= \frac{1}{e} \approx \mathbf{{\color{Red} {0.3679}}}
\end{align*}
\(1/e\) or roughly 37% is the max probability that a single tree is changing color and it occurs at a time after equinox that is 63% of time between the equinox and solstice.
But that's one tree, what about the forest?
No, we’re not missing the forest for the trees, here. If you had a coin that showed heads 37% of the time and tossed it a large number of times, the law of large numbers (and intuition!) tells us that we’d get heads about 37% of the time. By the same token, since each tree maxes out at 37% at \(t = 0.63 \), and since trees change color independently, the maximum average number of trees in fall foliage in Riddler Nation is expected to be 37% (36.79% to be more accurate). This max is at 63% of the equinox–solstice time interval after the equinox.
Since Equinox this year was on 9/22 and Solstice is on 12/21, 63.21% of time between Solstice and Equinox ‘falls’ on 11/17.
If you’re planning a trip to Riddler Nation this year, Nov 17th is the date to see the max fraction of trees in fall foliage.
How close can we get to the answer if we used fixed time points of change?
The problem is easily discretized for an approximate but reasonably accurate solution. Let’s break down the time interval between Equinox and Solstice into \(N\) discrete time points 1 to \(N \). These could, for example ,just be the 91 days between equinox and solstice this year.
Similar to the approach above in the continuous time period solution, we will find the probability \(P(k) \) that a single tree is in the midst of color change at discrete time point \(k\).
Again, following the same approach as before (ref fig above):
\begin{align*}
P(k) &= P(X < k \ \cap \ y > k ) \\
&= \sum_{c=1}^{k-1}P(X < k \ \cap \ y > k \ | \ X = c)\cdot \underbrace{P(X = c)}_{\textit{1 in N chance}} \\
&= \sum_{c=1}^{k-1} \underbrace{ P( y > k \ | \ X = c)}_{\textit{N-k choices out of N-c}} \cdot \frac{1}{N}\\
&= \sum_{c=1}^{k-1}\frac{N-k}{N-c}\cdot \frac{1}{N} \\
&= \frac{N-k}{N} \sum_{c=1}^{k-1}\frac{1}{N-c}
\end{align*}
Picking \(N = 1000\) and plotting the probability vs. the time points results in the same shape curve as expected with a maximum of 0.3672 or 36.72% which is pretty close to the 36.79% we calculated earlier. Not bad at all.
