Another proof of Fibonacci sequence in classic probability puzzle
Recently Scientific American reported that Fibonacci sequence appears as an answer to the following problem:
If I have n sticks with random lengths between 0 and 1, what is the probability that no three of those sticks can form a triangle?
The answer to this puzzle is \( \Pi_{i=1}^n \frac{1}{F_i} = \frac{1}{1} \frac{1}{1} \frac{1}{2} \dots \frac{1}{F_n} \) where \( F_i \) is the i-th Fibonacci number. This is the Arxiv link for the paper which contains a proof of it. Someone posted a novel proof of this puzzle which is more linear algebraic in nature. I made a small modification on top of this proof which is what I present here. Most of the credit to this proof goes to the Reddit user.
0. Outline of the proof
Here is the overall idea - sort the lengths \( l_i \) from shortest to longest. The vector of sorted lengths can be shown to be a linear combination of a certain basis. Once we get this basis, we use it express the longest length \( l_n \) in terms of it. Finally we use the condition that \( \text{longest length} \le 1 \) to get a simplex.
These steps are implemented below:
1. Steps 1 and 2 - Expressing sorted stick lengths as a matrix-vector product
We do this for two cases - the case where the lengths can not form a triangle and the general case (the lengths may or may not form a triangle).
1.1 Lengths which cannot form a triangle
Given the shortest length is \( l_1 = ε_1 \), we have that \( l_2 = l_1 + ε_2 \).
Note that \( l_3 \) has to be bigger than \( l_1 + l_2 = 2l_1 + ε_2 \). We can assume that \( l_3 = 2l_1 + ε_2 + ε_3 \).
Using the same argument, the next three lengths can be written down as:
Note that \( l_3 \) has to be bigger than \( l_1 + l_2 = 2l_1 + ε_2 \). We can assume that \( l_3 = 2l_1 + ε_2 + ε_3 \).
Using the same argument, the next three lengths can be written down as:
\( l_4 = 3l_1 + 2ε_2 + ε_3 + ε_4 \)
\( l_5 = 5l_1 + 3ε_2 + 2ε_3 + ε_4 + ε_5 \)
\( l_6 = 8l_1 + 5ε_2 + 3ε_3 + 2ε_4 + ε_4 + ε_6 \)
\( \cdots \)
\( l_n = F_nl_1 + F_{n-1}ε_1 + F_{n-2}ε_2 + \cdots + ε_{n-1} \)
Thus the vector of sorted lengths can be written down as:
\( l = \)\(
\begin{bmatrix}
1 & 0 & 0 & ... & 0 & 0 \\ 1 & 1 & 0 & ... & 0 & 0 \\ 2 & 1 & 1 & ... & 0 & 0 \\ 3 & 2 & 1 & ... & ... & ... \\ ... & ... & ... & ... & 1 & 0 \\ F_n & F_{n-1} & F_{n-2} & ... & 1 & 1
\end{bmatrix}
\)\(
\begin{bmatrix}
ε_1 \\ ε_2 \\ ε_3 \\ ... \\ ε_n
\end{bmatrix}
\)
1.2 Any arbitrary vector of lengths
This case is much simpler. As before, start with \( l_1 = ε_1 \). Then since \( l_2 \\ge l_1 \), we have that \( l_2 = l_1 + ε_2 \) and so on. For sake of completion, the remaining lengths look something like:
\( l_3 = l_1 + ε_2 + ε_3 \)
\( l_4 = l_1 + ε_2 + ε_3 + ε_4 \)
\( \cdots \)
\( l_n = l_1 + ε_2 + ε_3 + \cdots + ε_n \)
In this case, the vector of sorted lengths can be written down as:
\( l = \)\(
\begin{bmatrix}
1 & 0 & 0 & ... & 0 & 0 \\ 1 & 1 & 0 & ... & 0 & 0 \\ 1 & 1 & 1 & ... & 0 & 0 \\ 1 & 1 & 1 & ... & ... & ... \\ ... & ... & ... & ... & 1 & 0 \\ 1 & 1 & 1 & ... & 1 & 1
\end{bmatrix}
\)\(
\begin{bmatrix}
ε_1 \\ ε_2 \\ ε_3 \\ ... \\ ε_n
\end{bmatrix}
\)
2. Step 3 - largest length in each case
2.1 First case
In this case, the largest length is:
\( \sum_{i=1}^n \amber{F_i}y_i \) for positive coefficients \( y_i \).
2.2 Second case
In this case, the largest length is:
\( \sum_{i=1}^n x_i \) for positive coefficients \( x_i \).
3. Step 4 - obtain simplexes for each case
Since these lengths are sampled from the interval \( [0,1] \), they have to be less than or equal to one. Applying this condition to each of the largest lengths above we get:
i) \( \sum_{i=1}^n \amber{F_i} y_i \le 1 \): the points that satisfy this condition lie form a volume \( V_1 \). This is the volume of the simplex formed by origin and vectors \( \underbrace{F_i \amber{e_i}}_{\text{standard basis vector scaled by} \ F_i} \) for \( i \) from 1 to n.
ii) \( \sum_{i=1}^n x_i \le 1 \): this is the standard simplex and has a volume \( V_2 \) of \( n! \). The exact area is not needed for the proof though.
4. Final step
The probability is given by \( \frac{V_1}{V_2} \). How do we find \( V_2 \) in terms of \( V_1 \)? By defining a map \( y_i = x_i / F_i \). It is easy to see that the determinant of Jacobian of this map is \( |J| = \Pi_i \frac{1}{F_i} \). Thus the volume \( V_1 = |J|V_1 \). This gives us the probability to be:
\( \Pi_{i=1}^n \frac{1}{F_i} \)