April 30, 2026
We present two complementary proofs that, if the lengths of \(n\) sticks are sampled at random, then the probability that no \(p+1\) sticks can form a \((p+1)\)-sided polygon can be expressed as the product of the reciprocals of a series of terms involving the \(p\)-step Fibonacci numbers. The first proof uses matrix algebra to extend the method previously used by Sudbury et al. [1] to derive expressions for the probabilities of not being able to form triangles and quadrilaterals. The second alternative proof uses a different approach based on expressions for the minimum and maximum lengths of each stick that are compatible with the constraint of not being able to form a \((p+1)\)-sided polygon, and provides insights into the structure of the probability expressions and the underlying reason that they include the Fibonacci numbers. Furthermore, the approach is developed in a generalised way that can, in principle, be applied to sticks randomly sampled from any probability distribution.
Article type: research
The problem of random sticks is one of the classic problems in geometric probability with a long history, dating back to the "broken stick problem" posed by Lemoine in 1873 [2]: a stick of unit length is broken at two random points, and one asks for the probability that the three resulting segments can form a triangle. Since then, many generalisations of this basic formulation have been studied. D’Andrea and Gomez [3] extended the problem to the case of \(n\) pieces, proving that the probability that a stick broken randomly into \(n\) pieces can form an \(n\)-gon is \(1 - n/2^{n-1}\). More generally, Verreault [4], [5] and Mukerjee [6] systematically studied the \((p+1)\)-gon version: given a stick broken into \(n\) pieces, what is the probability that no, every or any random subset of \(p+1\) pieces can form a \((p+1)\)-gon? Remarkably, the probability formulas for no subset of \(p+1\) pieces forming a \((p+1)\)-gon are deeply connected with the \(p\)-step Fibonacci numbers.
In a different direction, Petersen and Tenner [7] introduced a model that is fundamentally different in its assumptions — the "pick-up sticks model". In this model, the random lengths of \(n\) sticks are drawn independently from a uniform distribution on \([0,1]\), and there is no constraint that they sum to one. They proved that the probability that \(n\) such sticks cannot form an \(n\)-gon is \(\frac{1}{(n-1)!}\) [7].
Within this framework, Sudbury et al. [1] show that the probability of not being able to form a triangle from any three of \(n\) sticks with independent random lengths selected from a uniform distribution on \([0,1]\) is \[{PN}_3^n=\;\prod_{i=1}^{n}\frac{1}{F_i}, \label{eq:no95triangle}\tag{1}\] where \(F_i\) are the (2-step) Fibonacci numbers defined by \(F_1=1,\) \(F_2=1,\) and \(F_i=F_{i-1}+F_{i-2}\) for \(i > 2\).
To prove this result they used the constraint that, after the sticks have been sorted in order of increasing length, the lengths of all consecutive triples must satisfy \(l_{i-2}+l_{i-1} \leq l_{i}\), which is a constraint that the minimum length, \(l_i^{\text{min}}\), of each stick (\(i>2\)) is the sum of the lengths of the next two shortest sticks. They then used the fact that the order statistics of a uniform \([0,1]\) sample has the same distribution as the normalised cumulative sums of exponential variables. On integrating over the \(n\) exponential variables, the Fibonacci numbers in (1 ) emerged in the exponents of the integrated exponentials.
They then used the same approach to prove that the probability of not being able to form a quadrilateral from any four of \(n\) sticks with independent uniformly distributed random lengths from \([0, 1]\) is \[{PN}_4^n=\frac{1}{T_n-\;T_{n-2}}\prod_{i=1}^{n-1}\frac{1}{T_i}, \label{eq:no954-gon}\tag{2}\] where \(T_i\) are the are the Tribonacci (3-step Fibonacci) numbers defined by \(T_1=1\), \(T_2=1\), \(T_3=2\), and \(T_i=\;T_{i-1}+T_{i-2}+T_{i-3}\;\) for \(i>3\).
The algebraic manipulations to prove this result were more involved and also made use of Tribonacci number recursion relationships to reformulate the exponents of the exponential probability distributions.
At the start of their paper, Sudbury at al. [1] suggested that the occurrence of the factorials of the Fibonacci and Tribonacci numbers in the above probability expressions was “surprising”. However, they concluded their paper by postulating that their results suggested a deeper underlying structure in the probability that no subset of \(n\) independently sampled random stick lengths can form a \((p+1)\)-gon (polygon with \(p+1\) sides). They invited the reader to extend their framework to find a closed form expression of \({PN}_{p+1}^n\) for higher values of \(p+1\), and also encouraged the reader to search for an alternative proof of the same Fibonorial law that would shed further light on the probabilistic structure they had uncovered. In this paper, we respond to both of these challenges by first extending the method of Sudbury et al. [1] by using matrix algebra to prove Theorem [theorem:32PN95123p43112594n].
thmMainIdentity If \(n\) sticks have independent, random lengths chosen from a uniform distribution on the unit interval \([0,1]\), the probability that no \((p+1)\) of them can form a \((p+1)\)-gon (a polygon with \(p+1\) sides) is \[{PN}_{p+1}^n= \prod_{i=1}^{n-p+2}\frac{1}{F_i^{p}} \prod_{i=n-p+3}^{n}\frac{1}{F_i^{p}- \sum_{j=1}^{i-n+p-2}{jF_{i-j-1}^{p}}}, \label{eq:main95result}\tag{3}\] where \(\{F_i^{p}\}^{\infty}_{i=-\infty}\) is the sequence of \(p\)-step Fibonacci numbers generated using the recurrence relationship \[F_i^p=\sum_{j=1}^{p}F_{i-j}^p\] and the initial conditions \(F_1^p=1\) and \(F_0^p=F_{-1}^p=\ldots=F_{-p+2}^p=0\).
We then go on to develop an alternative proof of this theorm, first for triangles and then for the general case of a \((p+1)\)-gon. This alternative approach provides the deeper insight sought by Sudbury et al. [1] by revealing how the geometric constraints on the minimum and maximum allowable lengths of each stick, that arise from the requirement that no \(p+1\) sticks can form a \((p+1)\)-gon, are the fundamental reason for the appearance of the Fibonacci numbers in the probability expression.
The paper is organized as follows. Section 2.1 reviews the necessary tools from order statistics and exponential spacings required for the matrix algebra proof of Theorem [theorem:32PN95123p43112594n], which is then presented in Section 2.2. Section 3 develops the alternative geometric proof based on extrema length constraints, starting in Section 3.1 with a preliminary proof for the simplest case of triangles. Section 3.2 then builds on this simplest case to prove the general case for a \((p+1)\)-gon. The geometric proof is developed in a way that can, in principle, be applied to sticks drawn randomly from any bounded probability distribution. Section 3.3 provides a further generalistaion of the method to unbounded probability distributions, and applies this to the particular case of an exponential distribution. Section 4 discusses the relationship between our results and the existing literature on both the broken stick and pick-up sticks problems. Section 5 offers concluding remarks and suggests directions for future research. Appendix 1 (Section 6) presents the derivation of an algorithm for calculating the explicit form of linear functions that appear in the expressions for the maximum stick lengths compatible with the constraint of not being able to form a (\(p+1\))-gon. Finally, Appendix 2 provides a third more concise, simple proof of our main result [theorem:32PN95123p43112594n], the development of which was informed by our geometric proof. The essence of this simple proof is consistent with a proof reported by Kern [8], which was developed from a proof of the triangles case of the pick-up sticks problem produced by the large language model ChatGBT. However, an important difference is that Kern’s [8] probability expression uses different \((k-1)-bonacci\) numbers (defined by using different initial terms) from the \(p\)-step Fibonacci numbers used here.
We first denote \[\begin{align} \label{matrix32A95p} \mathbf{A}_p=\begin{pmatrix} 1& 0&\dots&0&p-1\\ 1& 0&\dots&0&p-2\\ 0&1&\dots&0&p-3\\ \vdots&\vdots&&\vdots&\vdots\\ 0& 0&\dots&1&0 \end{pmatrix}\in \mathbb{R}^{p\times p}. \end{align}\tag{4}\]
Before proving Theorem [theorem:32PN95123p43112594n], we state a lemma that captures the algebraic relations generated by the integration process that will be used in devleoping the proof.
Lemma 1. Let matrix \(\mathbf{A}_p\), defined by (4 ), \(\mathbf{R}^1=(1,1,\dots,1)^T\in \mathbb{R}^p\), and \(\mathbf{R}^l=(R_1^l,R^l_2,\dots,R_p^l)^T\in\mathbb{R}^p\) satisfy \[\mathbf{R}^l=\mathbf{A}^{l-1}_p\mathbf{R}^{1},\;l=1,2,3,\dots\] Then \[R_p^l=F_l^p,R_{p-1}^l=F_{l+1}^p\] and \[\quad R_{i}^l=F_{l+p-i}^p-\sum_{j=1}^{p-i-1}(p-i-j)F^p_{l+j-1},i=1,2,\dots,p-2,\] where \(F^p_l\) \((l=1,2,3,\dots,)\) is the \(p\)-step Fibonacci numbers.
Proof. \(\mathbf{R}^{l}=\mathbf{A}^{l-1}_p\mathbf{R}^1\) tell us that \(\mathbf{R}^{l}=\mathbf{A}_p\mathbf{R}^{l-1}\), that is to say
\[\label{equations:1} \left\{ \begin{align} R_1^l&=R_1^{l-1}+(p-1)R_p^{l-1},\\ R_2^l&=R_1^{l-1}+(p-2)R_p^{l-1},\\ R_3^l&=R_2^{l-1}+(p-3)R_p^{l-1},\\ \cdots\\ R_p^l&=R_{p-1}^{l-1}. \end{align} \right.\tag{5}\] Therefore, \[\label{eq:preR94l95p} \begin{align} R^{l+1}_p&=R^{l}_{p-1},\\&=R_{p-2}^{l-1}+R_p^{l-1},\\ &=R^{l-2}_{p-3}+2R^{l-2}_p+R_p^{l-1},\\ &\vdots\\ &=R_{1}^{l-p+2}+\sum_{i=1}^{p-2} iR_p^{l-i}. \end{align}\tag{6}\] From the first two formulas in equations (5 ), \[R_2^l-R_1^l=-R_p^{l-1},\] which means \[R_1^l=R_p^{l-1}+R_2^l.\]
Substituting the above expression into equation (6 ) and successively applying the equations in system (5 ) from the second to the last, we obtain \[\begin{align} R_p^{l+1}&=R_1^{l-p+2}+\sum_{i=1}^{p-2}iR_p^{l-i}\\ &=R_p^{l+1-p}+R_2^{l-p+2}+(p-2)R^{l-p+2}_p+\sum_{i=1}^{p-3} iR_p^{l-i}\\ &=R_p^{l+1-p}+R_p^{l-p+2}+R_3^{l-p+3}+\sum_{i=1}^{p-3} iR_p^{l-i}\\ &\vdots\\ &=\sum_{i=1}^{p} R_p^{l+1-i} . \end{align}\] Let \(\mathbf{R}^{-p+2}=(1,0,0,\dots,0)^T\in \mathbb{R}^p\), then \[\mathbf{R}^{t+2-p}=\mathbf{A}^t_p \mathbf{ R}^{2-p}=(1,1,\dots,1,0,0,\dots,0)^T\in \mathbb{R}^p, \text{ for } t<{p-1}.\] The elements from the first to the (t+1)-th position of the vector are all one, and the remaining elements are zero, and \[\mathbf{R}^{1}=\mathbf{A}_p^{p-1}\mathbf{R}^{2-p}.\] \(\mathbf{A}_p\) is invertible, which show that \(R_p^{-p+2}=\cdots=R_p^{0}=0\). Then this proves that \(R_p^l\) \((l=1,2,\dots)\) is precisely the \(p\)-step Fibonacci-type recurrence by definition. That’s to say, \(R_p^l=F_p^l\) \((l=1,2,\dots)\).
Now we use \(R_p^{m}\) \((m=1,2,\dots)\) to present \(R_i^{l}\). Come back to the relationship (5 ),
The last two equations imply that \[R_{p-1}^l=R_p^{l+1}=F^p_{l+1},\] and
\[R_{p-2}^l=R_{p-1}^{l+1}-R_{p}^l=R_p^{l+2}-R_p^l.\] Substituting this into the third last equation (which represents \(R^l_{p-3}\)), we obtain \[R_{p-3}^l=R^{l+1}_{p-2}-2R_p^l=R_p^{l+3}-R^{l+1}_p-2R_p^l,\] Since \[R_{i}^l=R_{i+1}^{l+1}-(p-i-1)R_{p}^l, \text{ for }i\leq p-1.\] By induction, we obtain \[\begin{align} R_{i}^l&=R^{l+p-i}_p-\sum_{j=1}^{p-i-1}(p-i-j)R_p^{l+j-1}\\ &=F_{l+p-i}^p-\sum_{j=1}^{p-i-1}(p-i-j)F^p_{l+j-1}, \text{ for }i\leq p-2. \qedhere \end{align}\] ◻
Proof of Theorem [theorem:32PN95123p43112594n]. Let \(U_{(1)}\le U_{(2)}\le\dots\le U_{(n)}\) be the order statistics of \(U_1,\dots,U_n\). The condition that no \(p+1\) lengths can form a \((p+1)\)-gon is equivalent to \[\begin{align} \label{first32f} \sum_{i=l}^{l+p-1} U_{(i)}\leq U_{(l+p)},\qquad \text{for all } 1\leq l\leq n-p. \end{align}\tag{7}\] It is well established (see,for example, Johnson et al. [9]) that the order statistics of a uniform sample can be represented via normalized sums of independent exponential variables, if \(x_1,\dots,x_{n+1}\stackrel{\mathrm{i.i.d.}}{\sim}\operatorname{Exp}(1)\) with density \(f(x)=e^{-x}\) and \(S=x_1+\dots+x_{n+1}\), therefore, \[U_{(i)}\stackrel{d}{=}\frac{x_1+\dots+x_i}{S},\qquad i=1,\dots,n .\] Substituting this into (7 ) yields
\[\begin{align} \sum_{l=0}^{p-1}\frac{x_{1}+\cdots+x_{i+l}}{S}&\leq\frac{x_{1}+\cdots+x_{i+p}}{S}, \\ (p-1)\sum_{ l=1}^ix_l+(p-2)&x_{i+1}+\dots +x_{i+p-2}\leq x_{i+p}, \end{align}\] where \(1\leq i\leq n-p\). With \(x_{l}\) \((l=1,2,\dots,p)\) being unbounded between zero and infinity.
The successive inequalities define a nested region in \(\mathbb{R}^{n}\), and the required probability corresponds to the volume of this region under the exponential density. To evaluate it, we integrate successively from \(x_{n}\) down to \(x_{1}\), each step producing a factor determined by the recurrence relation that will lead to the \(p\)-step Fibonacci pattern.
To make the subsequent formulas more concise, we introduce the notation \(L_j\), that \[\begin{align} \label{simplnotations} L_{j}= (p-1)\sum_{ l=1}^{j-p}x_l+(p-2)x_{j-p+1}+\dots +x_{j-2}, \end{align}\tag{8}\] for \(j=p+1,p+2,\dots,n\). With \(L_j=0\) for \(j=1,2,\dots,p\).
The probability we need to calculate is \[\begin{align} PN^n_{p+1}=\int_{L_1}^\infty \int_{L_2}^\infty&\dots\int_{L_n}^\infty e^{-\sum_{i=1}^n x_i}dx_n\dots dx_2dx_1\\ =\int_{L_1}^\infty\int_{L_2}^\infty&\cdots \int^\infty_{L_{n-1}} e^{-p\sum_{ l=1}^{n-p} x_l-(p-1)x_{n-p+1}-\dots -2x_{n-2}-x_{n-1}}dx_{n-1}\dots dx_2dx_1. \end{align}\] For convenience, we introduce the vector \(\mathbf{R}^1,\mathbf{R}^2\in \mathbb{R}^p\) to rewrite this integral, \[\begin{align} PN^n_{p+1}=\int_{L_1}^\infty \int_{L_2}^\infty&\dots\int_{L_n}^\infty e^{-R_1^1\sum_{l=1}^{n-p+1} x_l-R_2^1x_{n-p+2}-\dots -R_p^1x_n}dx_n\dots dx_2dx_1\\ =\int_{L_1}^\infty\int_{L_2}^\infty&\cdots \int^\infty_{L_{n-1}} e^{-R_1^2\sum_{ l=1}^{n-p} x_{l}-R_2^2x_{n-p+1}-\dots -R_{p-1}^2x_{n-2}-R_p^2x_{n-1}}dx_{n-1}\dots dx_2dx_1. \end{align}\]
Here, the last term \(x_{n-p}\) in the \(\sum\)-summation has been taken out separately to compensate for the missing integrated \(x_n\). Let the integral obtained after \(j\) integrations be denoted \(I_j^{p}\), for example, \[\begin{align} I_1^{p}=&\int_{L_n}^\infty e^{-R_1^1(\sum_{t=1}^{n-p} x_t+x_{n-p+1})-R_2^1x_{n-k+2}-\dots -R_p^1x_n}dx_n \\=&\frac{1}{R_p^1}e^{-R_1^2\sum_{ t=1}^{n-p} x_{t}-R_2^2x_{n-p+1}-\dots -R_{p-1}^2x_{n-2}-R_p^2x_{n-1}}, \end{align}\] where \(L_n\) is given by (8 ) and \[\begin{align} R_1^2&=R_1^1+(p-1)R_p^1,\\ R^2_i&=R_{i-1}^1+(p-i)R_p^1,\quad i=2,\dots,p. \end{align}\] Now extend the relationship between \(\mathbf{R}^1\) and \(\mathbf{R} ^2\) to the general case, i.e., the properties that \(\mathbf{R}^l\) possesses after \(l\) integrations. By induction, \[\begin{align} I_l^{p}&=\prod_{t=1}^{l-1}\frac{1}{R^t_p}\int_{L_{n-l+1}}^\infty e^{-R_1^{l}(\sum_{t=1}^{n-l-p+1} x_t+x_{n-l-p+2})-R_2^{l}x_{n-l-p+3}-\dots -R_p^{l}x_{n-l+1}}dx_{n-l+1} \\&=\prod_{t=1}^l\frac{1}{R_p^t}e^{-R_1^{l+1}\sum_{ t=1}^{n-l-p+1} x_{t}-R_2^{l+1}x_{n-l-p+2}-\dots -R_{p-1}^{l+1}x_{n-l-1}-R_p^{l+1}x_{n-l}}. \end{align}\] In the \(\Sigma\)-summation term of the second integrand, a factor is extracted outside, ensuring that the exponent always contains \(p\) terms. Then \[\begin{align} R_1^{l+1}\sum_{ t=1}^{n-l-p+1} x_{t}&+R_2^{l+1}x_{n-l-p+2}+\dots +R_{p-1}^{l+1}x_{n-l-1}+R_p^{l+1}x_{n-l}\\&=R^l_p\times L_{n-l+1}+R_1^{l}(\sum_{t=1}^{n-l-p+1} x_t+x_{n-l-p+2})+R_2^{l}x_{n-l-p+3}+\dots +R_{p-1}^{l}x_{n-l}. \end{align}\] By observing the relationship between the expression of \(L_{n-l+1}\) and the exponential term, we can obtain that \(\mathbf{R}^l\) satisfies the following recurrence relation, \[\begin{align} R_1^{l+1}&=R_1^{l}+(p-1)R_p^{l},\\ R_i^{l+1}&=R_{i-1}^{l}+(p-i)R_p^{l},\quad i=2,\dots,p.\\ \end{align}\] The transformation matrix \(\mathbf{A}_p\) we obtained here is identical to the matrix in (4 ).
Denote \(\mathbf{R}^l=(R_1^l,R_2^l,\dots,R_p^l)^T\), we have \[\mathbf{R}^{l+1}=\mathbf{A}_p\mathbf{R}^l=\mathbf{A}^l_p\mathbf{R}^1.\] This relationship is the same as the condition stated in Lemma 1. After \(n-p\) integrations, we are left with
\[\begin{align} I_{n-p}^{p}=\prod _{l=1}^{n-p}\frac{1}{R_p^l}e^{{-R_1^{n-p+1} x_{1}-R_2^{n-p+1}x_{2}-\dots -R_{p-1}^{n-p+1}x_{p-1}-R_p^{n-p+1}x_{p}}}. \end{align}\] Then, by integrating successively with respect to \(x_{n-p},x_{n-1},\dots, x_2\), and \(x_1\), we obtain \[PN^n_{p+1}=\prod_{l=1}^{n-p}\frac{1}{R^l_p} \prod_{i=1}^p\frac{1}{R^{n-p+1}_i}.\] Note that in the second product, the terms involving \(R^{n-p+1}_p\) and \(R^{n-p+1}_{p-1} = R^{n-p+2}_p\) can be incorporated into the first product. Applying Lemma 1, together with the change of indices \(i' = n - i + 1\) and \(j' = p - i - j\) (renaming \(i', j'\) as \(i, j\)), completes the proof. ◻
Theorem 1 (Sudbury et al. [1]). If \(n\) sticks have independent, random lengths chosen from a uniform distribution on the unit interval \([0,1]\), the probability that no three of them can form a triangle is \[\prod_{i=1}^{n}\frac{1}{F_i},\] where \(F_i\) are the Fibonacci numbers defined by \(F_1=1,\) \(F_2=1,\) and \(F_i=F_{i-1}+F_{i-2}\) for \(i > 2\).
Before providing our alternative proof of Theorem 1, we state a lemma that is needed.
Lemma 2. Let \(x_1, x_2, \dots, x_n\) be independent and identically distributed random variables defined on a probability space \((\Omega, \mathcal{F}, \mathbb{P})\) that represent the lengths of \(n\) sticks. We assume that \(x_i\) follows an absolutely continuous distribution with a probability density function \(p(x)\) supported on the bounded interval \((0, M)\). If \(l_1, \dots, l_n\) denote the order statistics of \(x_1, \dots, x_n\), satisfying \(l_1 \le l_2 \le \dots \le l_n\), then the probability that these lengths are compatible with a given requirement, R, is given by \[PS=n!\int_{R} \int\ldots \int\int{p(l_n){dl}_np(l_{n-1}){dl}_{n-1}{\ldots p(l_2)dl}_{2}p(l_1)dl}_1, \label{eq:NP95p94n}\qquad{(1)}\] where R represents the domain of integration (i.e. the ranges of stick lengths) compatible with the stated requirement.
Proof of Theorem 1. In order to satisfy the condition of not being able to form a triangle, our alternative geometric proof uses the same constraint as Sudbury et al. [1]: after the sticks have been sorted in order of increasing length, the lengths of all consecutive triples must satisfy \(l_{i-2}+l_{i-1} \leq l_{i}\). This constraint sets the limits on the minimum lengths of each stick compatible with the condition that it is not possible to form a triangle. Consequently, making the assignment \(l_0=0\), \[\begin{align} l_1^{\text{min}} &=0, \\ l_i^{\text{min}} &=l_{i-1}+l_{i-2}, \label{eq:32p61344l95i95min} \end{align}\tag{9}\] for \(i \geq 2\).
In addition, we use the fact that the above limits on minimum stick lengths also place a constraint on the maximum length of each stick that is dependent on the length of the next shortest stick. If the \((i-1)\)-th and \(i\)-th sticks have lengths \(l_{i-1}\) and \(l_i\), then the lengths of all subsequent sticks must satisfy the following conditions \[\begin{align} &l_{i+1} \ge {l_{i-1}+ l_i},\\ &l_{i+2} \ge l_{i-1}+\;{2l}_i, \\ & l_{i+3} \ge 2l_{i-1}+\;{3l}_i, \\ \vdots \\ &l_n \ge F_{n-i}l_{i-1}+\;{F_{n-i+1}l}_i. \end{align}\] However, for sticks drawn from a uniform distribution on \([0,1],\) \(l_n\leq l_n^{\text{max}}\) and \(l_n^{\text{max}}=1\) and therefore, for a given value of \(l_{i-1}\), the maximum length of the \(i\)th stick (\(i \leq n-1\)) is given by \[l_i^{\text{max}}=\frac{1-F_{n-i}l_{i-1}}{F_{n-i+1}}. \label{eq:max95stick3}\tag{10}\] For \(i \leq (n-1)\), this equation gives the maximum length of each stick in terms of the length of its next shortest stick and the Fibonacci numbers. The expression reveals the reason why the Fibonacci numbers appear in (1 ) – it is because they arise in the determination of the maximum stick lengths compatible with the requirement for it not to be possible to form a triangle.
The \(l_i^{\text{min}}\) and \(l_i^{\text{max}}\) values given by (9 ) (10 ) define the Lemma (2 domain of integration compatible with our requirement that no three sticks out of \(n\) can form a triangle. We now proceed to calculate the associated probability, \(PN_3^n\), by evaluating the integrals in (?? ) over this domain and using \(p(l)=1\) for a uniform distribution on \([0,1]\). Evaluating the first (innermost) integral and then using \(F_1=F_2=1\), \[\begin{gather} \int_{l_{n-2}+l_{n-1}}^1 dl_n = 1-l_{n-2}-l_{n-1} = \frac{1}{F_1}(1-F_1 l_{n-2} - F_2 l_{n-1}) \\ =\frac{1}{F_1}(F_2 l_{n-1}^{\text{max}} - F_2 l_{n-1}). \end{gather}\] The second integral then becomes \[\begin{gather} \frac{1}{F_1}\int_{l_{n-3}+l_{n-2}}^{l_{n-1}^{\text{max}}}{\left(F_2l_{n-1}^{\text{max}}- F_2l_{n-1}\right){dl}_{n-1 }} = \frac{1}{{2F}_1F_2}\left(1- F_1l_{n-2}- F_2l_{n-2}- F_2l_{n-3}\right)^2 \\ =\frac{1}{{2F}_1F_2}\left(F_3l_{n-2}^{\text{max}}- F_3l_{n-2}\right)^2. \end{gather}\] Continuing in this manner to progressively evaluate all but the final integral in (?? ) gives, \[PN_3^n = \frac{n!}{\left(n-1\right)!F_1\ldots F_{n-1}}\int_{0}^{l_1^{\text{max}}}{\left( F_nl_1^{\text{max}}- F_nl_1\right)^{n-1}{dl}_{1}}.\] Evaluating the final integral using \(l_1^{\text{max}}=1/F_n\), we find \[PN_3^n = \prod_{i=1}^{n}\frac{1}{F_i}. \qedhere\] ◻
Proof of Lemma 2. For \(n\) sticks with lengths drawn randomly from a probability density function \(p(x)\), the probability that any one stick of the \(n\) sticks has a length between \(l_n\) and \(l_n+{dl}_n\) and all other \(n-1\) sticks are shorter than \(l_n\) is \[np(l_n)dl_n\left\{P(x\le l_n)\right\}^{n-1}\] where \(P(x\le l_n) = \int_0^xp(x)dx.\) In this case, the \(n-1\) shortest sticks have lengths \(\le l_n\), drawn from a renormalised probability density function given by \({p(x)}\text{/}{P(\le l_n)}\), and the probability that the second longest stick has a length between \(l_{n-1}\) and \(l_{n-1}+dl_{n-1}\) and all the other sticks are shorter than \(l_{n-1}\) is \[(n-1)\left(\frac{p(l_{n-1})}{(P(x\le l_n)}\right)dl_{n-1}\left(\frac{(P(x\le l_{n-1})}{(P(x\le l_n)}\right)^{n-2}.\] Continuing this process, we see that the probability that the \(n\) sticks have lengths between \(l_{i}\) and \(dl_i\), for \(1 \leq i \leq n\), in order of increasing length is \[n!p(l_1){dl}_1\dots \;p(l_n){dl}_n. \label{eq:32prob95li95dli}\tag{11}\]
To find the probability that the lengths of the sticks satisfy some requirement, \(R\), we simply integrate (11 ) over the ranges of stick lengths compatible that requirement to give \[PS=n!\int_{R} \int\ldots \int\int{p(l_n){dl}_np(l_{n-1}){dl}_{n-1}{\ldots p(l_2)dl}_{2}p(l_1)dl}_1,\] where R represents the domain of integration (i.e. the ranges of stick lengths) compatible with the stated requirement. ◻
Our alternative geometric proof of Theorem [theorem:32PN95123p43112594n] is based on Lemma 2 plus the following sequence of lemmas, each building on the previous one.
Lemma 3. The minimum lengths for each stick compatible with the condition of not being able to form a \((p+1)\)-gon are given by \[l_i^{\text{min}} = \begin{dcases} 0 & \text{for } i=1, \\ l_{i-1} & \text{for } 1 < i < p+1, \\ \sum_{j=1}^{p} l_{i-j} & \text{for } i \ge p+1. \end{dcases} \label{eq:32p-gon95li95min}\qquad{(2)}\]
Lemma 4. The maximum lengths for each stick compatible with the condition of not being able to form a \((p+1)\)-gon are given by \[l_i^{\text{max}}= \begin{dcases} \frac{1}{m_1} & \text{for } i=1, \\ \frac{1}{m_i}-\frac{f_i\left(l_1,\ldots,l_{i-1}\right)}{m_i} & \text{for } 1<i\leq n-1, \\ \frac{1}{m_n} & \text{for } i=n, \end{dcases} \label{eq:32p-gon95li95max}\qquad{(3)}\] where the \(f_i\)’s are linear functions of the \(l_i\)’s with integer coefficients (which in some cases are equal to zero) and \(m_1\) and the \(m_i\)’s are positive (non-zero) integer constants with \(m_n\)=1.
Lemma 5. The constants \(m_i\) are given by \[m_i= \begin{dcases} F_{n-i+1}^p-\sum_{j=1}^{p-i-1}{jF_{n-i-j}^p} & \text{for } 1\le i\;\le p-2, \\ F_{n-i+1}^p & \text{for } p-1 \leq i \leq n. \\ \end{dcases}\]
Lemma 6. For \(i\geq2\), \[m_i\left(l_i^{\text{max}}-l_i^{\text{min}}\right)=m_{i-1}\left(l_{i-1}^{\text{max}}-l_i\right).\]
Lemma 7. The probability of not being able to form a \((p+1)\)-gon from any \(p+1\) out of \(n\) sticks is given by \[{PN}_{p+1}^n=\prod_{i=1}^{n}{\frac{1}{m_i}.}\]
Proof of Theorem [theorem:32PN95123p43112594n]. Using Lemmas 7 and 5 leads directly to \[{PN}_{p+1}^n=\prod_{i=p-1}^{n}\frac{1}{F_{n-i+1}^p}\prod_{i=1}^{p-2}\frac{1}{F_{n-i+1}^p-\sum_{j=1}^{p-i-1}{jF_{n-i-j}^p}}.\] Finally, making the transformation \(i \rightarrow n-i+1\) in both products gives \[{PN}_{p+1}^n=\prod_{i=1}^{n-p+2}\frac{1}{F_i^{p}}\prod_{i=n-p+3}^{n}\frac{1}{F_i^{p}-\sum_{j=1}^{i-n+p-2}{jF_{i-j-1}^{p}}}. \qedhere\] ◻
Proof of Lemma 3. Once the sticks have been sorted in order of increasing length, the requirement of not being able to form a \((p+1)\)-gon results in the constraint that the lengths of all consecutive \((p+1)\)-tuples must satisfy \[l_{i-p}+l_{i-p+1}+l_{i-p+2}+\ldots+l_{i-1} \leq l_{i}.\] Using this constraint and also the fact that the sticks are sorted in order of length, we identify the following minimum lengths for each stick compatible with the requirement of not being able to form a \((p+1)\)-gon \[l_i^{\text{min}} = \begin{dcases} 0 & \text{for } i=1, \\ l_{i-1} & \text{for } 1 < i < p+1, \\ \sum_{j=1}^{p} l_{i-j} & \text{for } i \ge p+1. \end{dcases} \qedhere\] ◻
Proof of Lemma 4. Adopting the same approach as for our alternative proof of Theorem 1, if the \(i\) shortest sticks have lengths \(l_1,l_2,\ldots,l_i\), then using Lemma 3 the lengths of the subsequent sticks must satisfy the following conditions \[\begin{align} &l_{i+1} \ge f(l_1,\ldots,l_i), \\ &l_{i+2} \ge f\left(l_1,\ldots,l_i,l_{i+1}\right)=f(l_1,\ldots,l_i), \\ &\vdots \\ &l_n \ge f\left(l_1,\ldots,l_i,l_{n-1}\right)=f\left(l_1,\ldots,l_i\right)=f_i\left(l_1,\ldots,l_{i-1}\right)+m_il_i, \end{align}\] where the \(f\)’s and \(f_i\) are linear functions of the \(l_i\)’s with integer coefficients (which in some cases are equal to zero) and \(m_i\) is a non-zero integer constant. Now, \(l_n \leq l_n^{\text{max}}=1\) for stick lengths drawn from a uniform probability distribution on \({[0,1]}\), therefore \[l_i^{\text{max}}= \begin{dcases} \frac{1}{m_1} & \text{for } i=1, \\ \frac{1}{m_i}-\frac{f_i\left(l_1,\ldots,l_{i-1}\right)}{m_i} & \text{for } 1<i\leq n-1, \\ \frac{1}{m_n} & \text{for } i=n, \end{dcases}\] where \(m_n=1.\) ◻
Note, an algorithm for determining the explicit form of the functions \(f_i\) is derived in the appendix, though this is not required for our proof of Theorem [theorem:32PN95123p43112594n].
Proof of Lemma 5. For stick lengths drawn from a uniform distribution on \([0,1],\) by definition \[m_n=1=F_1^{p}. \label{eq:32m95n}\tag{12}\]
Using the \(l_i^{\text{min}}\) values given by Lemma 3 and the same approach that was used in the proof of Lemma 4, for \(p+1 \leq i \leq n-1\), it is straightforward to see that \[m_i=F_{n-i+1}^p. \label{eq:32m95i}\tag{13}\]
For \(i<p+1\), we use the same approach to calculate \(l_i^{\text{max}}=l_{p-q+1}^{\text{max}}\). With the sticks arranged in order of increasing length, we have \[\begin{align} \begin{aligned} &l_1 = l_1, \\ &\vdots \\ &l_{p-q+1} = l_{p-q+1}, \\ &l_{p-q+2} \ge l_{p-q+1}, \\ &\vdots \\ &l_{p} \ge l_{p-q+1}, \\ &l_{p+1} \ge l_1+l_2+\ldots+l_{p-q}+ql_{p-q+1}, \\ &l_{p+2} \ge f_{p+2}(l_1,l_2,\ldots l_{p-q})+2ql_{p-q+1}, \\ &\vdots \\ &l_n \ge f_n(l_1,l_2,\ldots l_{p-q})+m_{p-q+1}l_{p-q+1}. \end{aligned} \label{eq:32l95mins} \end{align}\tag{14}\] However, we would like to express \(m_{p-q+1}\) in terms of the \(p\)-step Fibonacci numbers, \(F_i^{p}\).
To achieve this we need to transform the column of \(q\) lots of \(l_{p-q+1}\) above the row for \(l_{p+1}\) in (14 ) into \(l_{p-q+1}\) multiplied by the sum of a number of \(F_{i}^{p}\) sequences, each starting at \(F_{1}^{p}\).
We first note that we can transform a sequence of \(q\) 1’s as follows \[\begin{pmatrix} 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ \vdots \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \end{pmatrix} \rightarrow \begin{pmatrix} F_1^{p} \\ F_2^{p} \\ F_3^{p} \\ F_4^{p} \\ \vdots \\ F_{q-1}^{p} \\ F_q^{p} \end{pmatrix} -F_2^{p} \begin{pmatrix} 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ \vdots \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \end{pmatrix} -F_3^{p} \begin{pmatrix} 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \\ \vdots \\ 1 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \end{pmatrix} - \ldots - F_{q-1}^{p} \begin{pmatrix} 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ 0 \vphantom{F_1^{p}} \\ \vdots \\ 0 \vphantom{F_1^{p}} \\ 1 \vphantom{F_1^{p}} \end{pmatrix}.\] Using \({S}_{j,q-j}(1)\) \(\in \mathbb{R}^q\)to represent a sequence of \(j\) leading 0’s followed by \((q-j)\) 1’s, and \({S}_{j,q-j}\left(F_i^{p}\right)\) to represent a sequence of \(j\) leading 0’s followed by the first \((q-j) \;F_i^{p}\) numbers (starting at \(F_1^{p}\)), the above transformation can be written as \[{S}_{0,q}(1)={S}_{0,q}(F_i^{p})-F_2^{p}{S}_{2,q-2}(1)-F_3^{p}{S}_{3,q-3}(1) - \ldots\;- F_{q-1}^{p}{S}_{q-1,1}(1) \label{eq:32C195qq}\tag{15}\] and using the same approach, we also have \[{S}_{1,q-1}(1)={S}_{1,q-1}(F_i^{p})-F_2^{p}{S}_{3,q-3}(1)-F_3^{p}{S}_{4,q-4}(1) - \ldots - F_{q-2}^{p}{S}_{q-1,1}(1). \label{eq:32C195qq-1}\tag{16}\] We now note that we are only interested in transforming sequences containing a maximum number of \(q \leq p\) numbers. Hence, for the \(F_i^{p}\) numbers multiplying the \({S}_{j,k}(1)\) sequences in (15 ) and (16 ), \(2 \leq i \leq p-1\) and, therefore, we have the recurrence relationship \[F_{i+1}^{p} = 2F_i^{p}. \label{eq:32rec95rel}\tag{17}\]
Using (17 ) and subtracting (16 ) multiplied by two from (15 ) gives \[{S}_{0,q}(1)={S}_{0,q}(F_i^{p})-F_2^{p}{S}_{2,q-2}(1)+2({S}_{1,q-1}(1)-{S}_{1,q-1}(F_i^{p})),\] which using \(F_2^{p}=1\), can be expressed as \[{\big({S_{0,q}\left(1\right)}- {S_{1,q-1}\left(1\right)}\big)}=\big({S}_{1,q-1}(1)- {S}_{2,q-2}(1)\big)+S_{0,q}(F_i^{p})-2{S}_{1,q-1}(F_i^{p}). \label{eq:32rec95rel16}\tag{18}\] Now, by definition \[{S}_{q-1,1}(1)=S_{q-1,1}(F_i^{p}) \label{eq:32C195q1}\tag{19}\] and \[{{S}_{q-2,2}(1)=S}_{q-2,2}(F_i^{p}) \label{eq:32C195q2}\tag{20}\] i.e., \[{S}_{q-2,2}(1)-{S}_{q-1,1}(1)={S}_{q-2,2}(F_i^{p})-{S}_{q-1,1}(F_i^{p}).\] Using this starting value of \({S}_{q-2,2}(1)-{S}_{q-1,1}(1)\) and making the repeated application of the recurrence relationship given by (18 ), for \(q \geq 3\), we find \[{S}_{0,q}(1)= {S}_{1,q-1}(1)+\sum_{j=1}^{q-1}{S}_{q-j,j}(F_i^{p}). \label{eq:32simpler95rec95rel}\tag{21}\] Finally, starting with \({S}_{q-2,2}(1){=S}_{q-2,2}(F_i^{p})\) and making the repeated application of (21 ), for \(q \geq 3\), we find \[{S}_{0,q}(1)= {S}_{0,q}(F_i^{p})-\sum_{j=1}^{q-2}{jS}_{j+1,q-j-1}(F_i^{p}). \label{eq:32C195qq95express}\tag{22}\] For \(q=1,2\) or \(q>2\), we can now use (19 ), (20 ) and (22 ), respectively, to replace the sequence of \(q\) lots of \(l_{p-q+1}\) above the row for \(l_{p+1}\) in (14 ) by \(l_{p-q+1}\) multiplied by sequences of ascending \(F_i^{p}\) numbers.
Continuing these sequences of ascending \(F_i^{p}\) numbers down to the row for \(l_n\) in (14 ) gives \[m_{p-q+1} = \begin{cases} F_{n-p+q}^{p}, & \text{for } q=1, 2, \\ F_{n-p+q}^{p}-\sum_{j=1}^{q-2}{jF_{n-p+q-j-1}^{p}}, & \text{for } 3 \leq q \leq p. \end{cases} \label{eq:32X95q32q9512}\tag{23}\]
Finally, making the transformation \(p-q+1 \rightarrow i\) gives \[m_i= \begin{dcases} F_{n-i+1}^p-\sum_{j=1}^{p-i-1}{jF_{n-i-j}^p} & \text{for } 1\le i\;\le p-2, \\ F_{n-i+1}^p & \text{for } p-1 \leq i \leq n. \\ \end{dcases} \qedhere\] ◻
Proof of Lemma 6. We first note that (?? ) and (?? ) tell us that the \(l_i^{\text{min}}\)’s and \(l_i^{\text{max}}\)’s can each be expressed as a linear function of the \(l_i\)’s with integer coefficients. We then consider the following two sequences of stick lengths (arranged in order of increasing length).
Let \(l_1,l_2, \ldots, l_{i-1},l_i^{\text{max}},l_{i+1}^{\text{min}},l_{i+2}^{\text{min}},\ldots,l_{n-1}^{\text{min}},l_n^{\text{min}}\) be a sequence of stick lengths, which we will call Sequence 1. In this sequence, sticks \(\left(i+1\right)\) through to \(n\) take their minimum permissible lengths and stick \(i\) takes its maximum permissible length, which occurs when \(l_n^{\text{min}}=1\).
Let \(l_1,l_2,\ldots,l_{i-1}^{\text{max}},l_i^{\text{min}},l_{i+1}^{\text{min}},\ldots,l_{n-1}^{\text{min}}, l_n^{\text{min}}\) be a sequence of stick lengths, which we will call Sequence 2. In this sequence, sticks \(i\) through to \(n\) take their minimum permissible lengths, and stick \((i-1)\) takes on its maximum permissible length, which occurs when \(l_n^{\text{min}}=1\).
Using the same approach as for the proof of Lemma 4, from Sequence 1 we find \[1=m_il_i^{\text{max}}+m_{i-1}l_{i-1}+f_i(l_1,\ldots,l_{i-2}), \label{eq:32seq195mi}\tag{24}\] and from Sequence 2, \[1=m_il_i^{\text{min}}+m_{i-1}l_{i-1}^{\text{max}}+f_i(l_1,\ldots,l_{i-2}), \label{eq:32seq295mi}\tag{25}\] where \(f_i(l_1,\ldots,l_{i-2})\) is the same linear function of \(l_1,\ldots,l_{i-2}\) in both (24 ) and (25 ).
Equating the right-hand sides of (24 ) and (25 ) gives \[m_i{(l}_i^{\text{max}}-l_i^{\text{min}})=m_{i-1}{(l}_{i-1}^{\text{max}}-l_{i-1}) \text{ for } i \leq n-1.\] Also using the same approach as for the proof of Lemma 4 \[l_{n-1}^{max} = 1 -\sum_{j=2}^pl_{n-j}\] which gives \[l_{n-1}^{max} - l_{n-1} = 1 -\sum_{j=1}^pl_{n-j}= l_n^{max} - l_n^{min}\] Form Lemma 5, \(m_n=F_1^p=1\) and \(m_{n-1}=F_2^p=1\), and we therefore have \[m_n{(l}_n^{\text{max}}-l_n^{\text{min}})=m_{n-1}{(l}_{n-1}^{\text{max}}-l_{n-1}) .\] ◻
It is noted that, in our alternative proof of Theorem 1 (i.e. for \(\left(p+1\right)\)=3), the equivalence given by Lemma 6 was established after performing each integral using the Fibonacci number recurrence relationships.
Proof of Lemma 7. Noting that, for stick lengths randomly drawn from a uniform distribution on \([0,1]\), \(p(l)=1\), we use the minimum and maximum stick lengths given by Lemmas 3.4 and 3.6 to evaluate the integrals in the probability expression given by Lemma 3.2 subject to the condition of not being able to form a \((p+1)\)-gon from any \(p+1\) of \(n\) sticks. The result of the innermost integral in (?? ) contributes a factor to \(PN_{p+1}^n\) which can be written as \[\left(\frac{1}{(n-n+1)m_n}\right) m_n\left(l_n^{max}-\;l_n^{min}\right). \label{eq:32PN95p94nInnermost}\tag{26}\] Using Lemma 6, (26 ) can be rewritten as \[\left(\frac{1}{\left(n-n+1\right)m_n}\right)m_{n-1}\left(l_{n-1}^{\text{max}}-l_{n-1}\right).\] We now use this expression for the integral over \(l_n\) as the integrand for the second integral in (?? ), which becomes \[\begin{align} \frac{1}{m_n}\int_{l_{n-1}^{\text{min}}}^{l_{n-1}^{\text{max}}}{m_{n-1}}(l_{n-1}^{\text{max}}-l_{n-1}){dl}_{n-1}=\frac{1}{2m_{n}m_{n-1}}\Big(m_{n-1}\left(l_{n-1}^{\text{max}}-l_{n-1}^{\text{min}}\right)\Big)^2. \end{align}\] Using Lemma 6 again, this can be rewritten as \[\frac{1}{2m_{n}m_{n-1}}\Big(m_{n-2}\left(l_{n-2}^{\text{max}}-l_{n-2}\right)\Big)^2.\] We continue to apply the same process to progressively evaluate all but the final integral in (?? ), to give \[\label{integral:m951} {PN}_{p+1}^n=\frac{n!}{\left(n-1\right)!m_{n}m_{n-1}m_{n-2}\ldots m_2}\int_{l_1^{\text{min}}=0}^{l_1^{\text{max}}}\left(m_{1}l_1^{\text{max}}-m_{1}l_1\right)^{n-1}{dl}_{1}\tag{27}\] which, using \(l_1^{\text{max}}=1/m_1\), integrates to \[{PN}_{p+1}^n=\prod_{i=1}^{n}\frac{1}{m_i}. \qedhere\] ◻
It is interesting to note that, by construction, the expression that results from performing the innermost integrals in equation (?? ) over \(l_n\) through to, say, \(l_j\) represents the probability that the lengths of sticks \(j\) through to \(n\) all lie between their minimum and maximum values. After using Lemma 6 to re-express the result of these innermost integrals, we find that the revised expression always goes to zero when \(l_{j-1}\) is set to \(l_{j-1}^{\text{max}}\). This behaviour arises because, when \(l_{j-1}\) is set equal to \(l_{j-1}^{\text{max}}\), this fixes the lengths of sticks \(j\) to \(n\) to a specific combination of exact lengths that culminate in \(l_n\) being exactly equal to one (see proof of Lemma 4). Consequently, the ranges of integration for sticks \(j\) to \(n\) in (?? ) are reduced to zero and, hence, the probability for this exact combination of lengths (for sticks \(j\) through to \(n\)) goes to zero. The same behaviour was found in the evaluation of the integrals in our alternative proof of Theorem 1 (i.e. for \(p+1=3\)), where we used the Fibonacci number recurrence relationships rather than Lemma 6 to re-express the result of each integral.
We also note that in the the case of a bounded probability distribution, taking the sample space as \([0, M]\) is essentially equivalent to taking it as \([0, 1]\). Specifically, for a sample \(x\) defined on \([0, M]\) with uniform probability density function \(p(x) = 1/M\), the scaling transformation \(y = x / M\) maps the sample space onto \([0, 1]\), and the corresponding probability density function becomes \(M p(M y)\). This transformation does not affect whether sticks drawn from the distribution can form a given polygon. Hence, for bounded probability distributions, without loss of generality, we may assume the upper bound to be \(1\).
Furthermore, with the exception of Lemma 7 (which gives the result of performing the integrals in the Lemma 2 probability expression), all of the other lemmas used in our proof (and the algorithm given in the appendix for determining the explicit form of the functions \(f_i\) that appear in the Lemma 4 expressions for \(l_i^{\text{max}}\) are independent of the probability distribution that the sticks are assumed to be drawn from. Therefore, in principle, our geometric approach can be applied to the pick-up sticks problem where the stick lengths are randomly drawn from any bounded probability distribution on \([0,M]\), provided that a suitable iterative (or other) procedure can be identified for evaluating the integrals resulting from the application of Lemma 2.
However, Lemma 3 is affected by a change in the support for the probability density function from \([0,M]\), denoted \(\operatorname{supp}(p) = \{x \in \mathbb{R}^+ : p(x) > 0\}\), to \(\operatorname{supp}(p) = [aM, M]\), with \(0 < a < 1\): this change results in \(l_1^{\text{min}}\) increasing from zero to \(aM\). For the case of a uniform probability distribution on \([aM,M]\) with \(p(x) = 1/M(1-a)\) for \(x \in [aM,M]\), if \(aM \leq M/m_1\) (i.e. is less than or equal to the value of \(l_1^{\text{max}}\) compatible with the requirement of not forming a \((p+1)\)-gon), then we can obtain a modified value of \(PN_{p+1}^n\) by adding a factor of \([1/M(1-a)]^n\) for the modified probability distribution, a scale factor of \(M^{n-1}\) for the lengths os sticks \(2\) to \(n\), and re-evaluating the integral in (27 ) with \(l_1^{\text{min}}\) equal to \(aM\) and \(l_1^{\text{max}}\) equal to \(M/m_1\) to give \[\frac{(1-m_1a)^n}{(1-a)^n}\cdot\frac{1}{\prod_{i=1}^n m_i}, \text{ for } a\leq 1/m_1 \label {eq: trunctaed}\]
As we would expect, as \(l_1^{\text{min}} = aM\) approaches \(M/m_1 =l_1^{\text{max}}\) this modified probability of not being able to form a \((p+1)\)-gon falls to zero. When \(a\) exceeds \(1/m_1\), the requirement for not being able to form a \((p+1)\)-gon is necessarily violated and \(PN_{p+1}^n =0\).
We also note that equation ([eq: trunctaed]) maintains invariance with respect to the scale factor M. However, if the uniform probability distribution is expressed in the form \(p(x) = 1/(M-b)\) for \(x \in [b,M]\), then equation ([eq: trunctaed]) becomes \[\frac{(M-m_1b)^n}{(M-b)^n}\cdot\frac{1}{\prod_{i=1}^n m_i}, \text{ for } b\leq M/m_1\] and the scale invariance is "hidden".
We now consider the case where the probability density function, \(p(l)\), is unbounded. In this case, if we introduce a truncation bound \(M\), the probability that all stick lengths are at most \(M\) is \(\mathbb{P}\{l_i\leq M:i=1,2,\dots,n\}\). Then, the probability that they cannot form a (p+1)-gon is obtained as \[\begin{align} \mathbb{P}\{l_i\leq M:i=1,2,\dots,n\}\times n!\int_{l_1^{\text{min}}}^{l_1^{M,\text{max}}}\cdots\int_{l_n^{\text{min}}}^{l_n^{M,\text{max}}}\prod_{i=1}^n p(l_i)\mathrm{d}l_n\dots \mathrm{d}l_1, \end{align}\] where the \(l_i^{\text{min}}\) values are given by Lemma (3) and \(l^{M,\text{max}}_i\) are obtained from Lemma (4) by replacing the upper bound \(1\) with \(M\).
Since \(p(x)\) is a probability density function, by the Lebesgue dominated convergence theorem, taking the limit as \(M\to\infty\) yields the desired probability \[\begin{align}PN^n_{p+1}=n!\int_{l_1^{\text{min}}}^{+\infty}\cdots\int_{l_n^{\text{min}}}^{+\infty}\prod_{i=1}^n p(l_i)\mathrm{d}l_n\dots \mathrm{d}l_1, \end{align} \label{eq:32Unbonded32Int}\tag{28}\]
Hence, it can be seen that Lemma (2) remains valid for unbounded probability distributions. In this case, there is no constraint in the \(l^{\text{max}}\) values, which we simply set equal to \({+\infty}\).
A particular example is the exponential distribution with parameter \(1\), i.e., a probability density function given by \(p(x) = e^{-x}\) for \(x > 0\). In this case, we obtain \[\begin{align}PN^n_{p+1}=n!\int_{l_1^{\text{min}}}^{+\infty}\cdots\int_{l_n^{\text{min}}}^{+\infty}\prod_{i=1}^n e^{-l_i}\mathrm{d}l_n\dots \mathrm{d}l_1. \end{align} \label{eq:32PN95p43194nUnbonded32Int}\tag{29}\] This integral was obtained by Mukerjee [6] when solving the broken stick problem. By successive integration, the explicit expression for arbitrary \(p\) and \(n\) shown below can be derived inductively \[\begin{align}PN^n_{p+1}=n!\prod_{k=1}^{n-p+2}\frac{1}{t^{(p)}_k}\prod_{k=n-p+3}^{n}\frac{1}{t^{(p)}_k-\sum_{j=1}^{p+k-n-2}jt^{(p)}_{k-j-1}}, \end{align} \label{eq:32PN95p43194nUnbounded}\tag{30}\]
where the sequence \(\{t_k^{(p)}\}\) satisfies \(t_1^{(p)} = 1\), \(t_k^{(p)} = 0\) for \(k=0,-1,\dots,2-p\), and \[t^{(p)}_k=1+\sum_{j=1}^pt^{(p)}_{k-j}, \text{ k} \geq 2.\] This expression is strikingly similar to the case of a bounded uniform distribution. If we define \(T_k=t^{(p)}_k-t^{(p)}_{k-1}\), it is straightforward to verify that \(T_k\) is governed by the recurrence relation \(T_k=\sum_{j=1}^pT_{k-j}\), subject to the initial conditions \(T_2=2\), \(T_1=1\), and \(T_{i-p}=0,i=3,\dots,p\). This identifies \(T_k\) as the \(p\) -step Fibonacci sequence. Consequently, we know that \(t^{(p)}_k\) can also be expressed in terms of the \(p\)-step Fibonacci sequence as follows \[t_k^{(p)}=\sum_{j=1}^kF_j^{p},\] and, with \(t_k^{(p)}\) expressed in this form, the similarity with the case of the bounded uniform distribution is further enhanced.
Given our earlier finding that the appearance of the Fibonacci numbers results from the form of the expressions for \(l_i^{\text{max}}\) when stick lengths are randomly drawn from a bounded probability distribution, it is a little surprising that (30 ) still involves \(p\)-step Fibonacci numbers even though the \(l_i^{\text{max}}\) values are infinite in this case. It is also remarkable that the pick-up sticks probability of not being able to form a \((p+1)\)-gon when the sticks are drawn from an unbounded exponential probability distribution is exactly the same as that for the broken stick problem (see equation (34 )).
A special case of (30 ) is when \(p=2\), for which it is easy to verify that the Fibonacci sequence satisfies the following identity \(\sum_{j=1}^kF_j=F_{k+2}-1\), which means \(t^{(2)}_k=F_{k+2}-1\). Then \[\begin{align}PN^n_3=n!\prod_{k=1}^n\frac{1}{F_{k+2}-1}. \end{align}\] As for the case of a bounded uniform probability distribution, we note that (30 ) remains valid if a "length" scale factor, \(a\), is introduced into the exponential probability distribution to give a normalised probability density function \(p(x) = ae^{-ax}\) for \(x > 0\). In this case, the two factors of \(a\) appearing in the normalised probability density function cancel on evaluation of each integral in (29 ).
If we change the support for the exponential probability distribution to \(\operatorname{supp}(p) = [b, \infty]\), with \(0 < b < \infty\), then we have \(p(x) = e^{-x}/e^b\) for \(b \le x \le \infty\) and \(l_1^{min}=b\). The modified probability distribution introduces a factor \(exp(-nb)\) into equation (30 ). The change in \(l_1^{min}\) only affects the lower limit of the outermost integral in equation (29 ), resulting in a second additional factor in equation (30 ) of \(exp[-(t^{(p)}_n-\sum_{j=1}^{p-2}jt^{(p)}_{n-j-1})]\). The overall result is that equation (30 ) is modified to \[\begin{align} PN^n_{p+1}=n!exp[-(nb+t^{(p)}_n-\sum_{j=1}^{p-2}jt^{(p)}_{n-j-1})]\prod_{k=1}^{n-p+2}\frac{1}{t^{(p)}_k}\prod_{k=n-p+3}^{n}\frac{1}{t^{(p)}_k-\sum_{j=1}^{p+k-n-2}jt^{(p)}_{k-j-1}}. \end{align}\]
Lastly we note that, as for the case of bounded probability distributions, (28 ) is valid for any unbounded probability distribution provided that a suitable iterative (or other) procedure for evaluating the integrals in (28 ) can be identified.
We can reproduce the result of Petersen and Tenner [7] that the probability of \(n\) sticks drawn randomly from \([0,1]\) cannot form an \(n\)-gon by setting \(\left(p+1\right)=n\) in (3 ), which gives \[{PN}_n^n=\prod_{i=1}^{3}\frac{1}{F_i^{n-1}} \prod_{i=4}^{n}\frac{1}{F_i^{n-1}-\sum_{j=1}^{i-3}{jF_{i-j-1}^{n-1}}}. \label{eq:Petersen2020}\tag{31}\] Now \(F_1^{n-1}=1\), \(F_2^{n-1}=1\) and \(F_3^{n-1}=2\). Also, summing the sequences of numbers in (22 ) gives \[{q=F}_{q+1}^p-\sum_{j=1}^{q-2}jF_{q-j}^p,\] i.e., \[i-1=F_{i}^{n-1}-\sum_{j=1}^{i-3}jF_{i-j-1}^{n-1}.\] Hence, (31 ) reduces to \[{PN}_n^n=\frac{1}{\left(n-1\right)!}.\] For a stick of unit length broken at \(\left(n-1\right)\) random positions to form \(n\) random length pieces – the “broken stick problem" – the existing literature actually address three different problems (see, for example, Mukerjee [6]).
Problem 1. What is the probability, \({PN}_{p+1}^n\), that no \(p+1\) pieces out of \(n\) can form a \(\left(p+1\right)\)-gon?
Problem 2. What is the probability, \({PA}_{p+1}^n\), that every combination of \(p+1\) pieces out of \(n\) can form a \(\left(p+1\right)\)-gon?
Problem 3. If \(p+1\) pieces are chosen at random out of the \(n\) pieces, with all such choices being equally probable, what is the probability, \({PR}_{p+1}^n\), that the chosen pieces can form a \(\left(p+1\right)\)-gon?
For a stick of unit length broken at \(\left(n-1\right)\) random positions to form \(n\) random length pieces, Mukerjee [6] proves that no \(p+1\) pieces out of \(n\) can form a \(\left(p+1\right)\)-gon is given by \[{PN}_{p+1}^n=n!\prod_{r=1}^{n}\beta_r, \label{eq:problem1}\tag{32}\] where the \(\beta_r\) factors are defined by the following algorithm. Let \(e_1,\ldots,e_n\) in \(\mathbb{R}^n\) be unit vectors, then define vectors \(b_1,\ldots,b_n\) recursively as follows: \(b_1=e_1, \;b_r=e_r+b_{r-1}\) for \(r=2,\ldots , k\), and \(b_r=e_r+\sum_{u=1}^{k}b_{r-u}\) for \(r=k+1,\ldots, n\). Finally, \({(\beta_1,\ldots,\beta_{n)}}^T=\sum_{r=1}^{n}b_r\).
With some minor adaptations, the geometric proof of Theorem [theorem:32PN95123p43112594n] set out in Section 3.2 can also be applied to provide an alternative proof of (32 ) expressed as follows.
Theorem 2. If a stick of unit length is broken at \(\left(n-1\right)\) random positions to form \(n\) random length pieces, the probability of not being able to form a \((p+1)\)-gon from any combination of \(\left(p+1\right)\) of these pieces is given by \[{PN}_{p+1}^n=n!\prod_{i=1}^{n-p+2}\frac{1}{{SF}_i^p} \prod_{i=n-p+3}^{n}\frac{1}{{SF}_i^p-\sum_{j=1}^{i-n+p-2}{j{SF}_{i-j-1}^p}}.\] where \({SF}_i^p = \sum_{j=1}^{i}F_i^p\), and \(\left\{F_i^p\right\}_{i=-\infty}^\infty\) is the sequence of \(p\)-step Fibonacci numbers.
Our alternative proof uses the equivalent sequence of lemmas to those used for the proof of Theorem [theorem:32PN95123p43112594n] in Section 3.2 with appropriate modifications for the broken stick model. In the main, these differences arise because of the constraint on the length of the final stick piece once they have been arranged in order of increasing length, i.e. \[l_n=1-\sum_{j=1}^{n-1}{l_j}. \label{eq:p195ln}\tag{33}\]
Lemma 8. If a stick of unit length is broken at \(\left(n-1\right)\) random positions to form \(n\) random length pieces, the probability of not being able to form a \((p+1)\)-gon from any combination of \(p+1\) of these pieces can be expressed as \[{PN}_{p+1}^n=n!\left(n-1\right)!\int_{l_1^{\text{min}}}^{l_1^{\text{max}}}\;\int_{l_2^{\text{min}}}^{l_2^{\text{max}}} \ldots \int_{l_{n-1}^{\text{min}}}^{l_{n-1}^{\text{max}}}{dl_{n-1} \ldots dl_2 dl_1}, \label{eq:32p195integral}\qquad{(4)}\] where the limits of integration represent the minimum and maximum lengths of the stick pieces in order of increasing length that are compatible with the requirement of not being able to for a \((p+1)\)-gon.
Lemma 9. The minimum lengths of the broken stick pieces compatible with the requirement of not being able to for a (p+1)-gon are \[l_i^{\text{min}} = \begin{dcases} 0 & \text{for } i=1, \\ l_{i-1} & \text{for } 1 < i < p, \\ \sum_{j=1}^pl_{i-j} & \text{for } i \geq p. \end{dcases}\]
Lemma 10. The maximum lengths of the broken stick pieces compatible with the requirement of not being able to form a \((p+1)\)-gon are \[l_i^{\text{max}}= \begin{dcases} \frac{1}{s_1} & \text{for } i=1, \\ \frac{1}{s_i}-\frac{g_i\left(l_1,\ldots, l_{i-1}\right)}{s_i} & \text{for } 1<i\leq n-1, \\ \frac{1}{s_n} & \text{for } i=n, \end{dcases} \label{eq:p195li95max}\qquad{(5)}\] where the \(g_i\)’s are linear functions of the \(l_i\)’s with integer coefficients (which in some cases are equal to zero) and the \(s_i\)’s are positive (non-zero) integer constants with \(s_n=1\).
Lemma 11. The integer constants \(s_i\) take the following values \[s_i= \begin{dcases} {SF}_{n-i+1}^p-\sum_{k=1}^{p-i-1}k{SF}_{n-i-k}^p & \text{for } 1 \leq i \leq p-2, \\ {SF}_{n-i+1}^p & \text{for } p-1 \leq i \leq n-1. \end{dcases} \label{eq:integer95consts}\qquad{(6)}\]
Lemma 12. For \(i\geq2\), \[s_i\left(l_i^{\text{max}}-l_i^{\text{min}}\right)=s_{i-1}\left(l_{i-1}^{\text{max}}-l_i\right).\]
Lemma 13. The probability of not being able to form a \((p+1)\)-gon from any \((p+1)\) out of \(n\) pieces is given by \[{PN}_{p+1}^n=n!\prod_{i=1}^{n-1}{\frac{1}{s_i}}.\]
Proof of Theorem 2. Lemmas 13 and 11 lead directly to \[{PN}_{p+1}^n=\;n!\prod_{i=p-1}^{n}\frac{1}{{SF}_{n-i+1}^p}\;\;\prod_{i=1}^{p-2}\frac{1}{{SF}_{n-i+1}^p-\;\sum_{j=1}^{p-i-1}{j{FS}_{n-i-j}^p}},\] where we have chosen to include an extra factor (equal to one) for \(i=n\) in the first product for consistency with the equivalent expression for pick-up sticks case. Finally, making the transformation \(i\rightarrow n-i+1\) in both products gives \[{PN}_{p+1}^n=\;n!\prod_{i=1}^{n-p+2}\frac{1}{{SF}_i^p}\;\;\prod_{i=n-p+3}^{n}\frac{1}{{SF}_i^p-\;\sum_{j=1}^{i-n+p-2}{j{SF}_{i-j-1}^p}}. \qedhere \label{eq:32p195our95result}\tag{34}\] ◻
The equivalence of (34 ) and (32 ) can be seen by comparing the derivation of the \(s_{i}\) values in the proof of Lemma 11 below with Mukerjee’s recursive algorithm [6]for the calculation of his \(\beta_i\) factors. It is relatively straightforward to see that the two sets of factors are exactly equivalent, i.e. \(s_{i}=\beta_i\).
Mukerjee’s paper [6] includes an appendix that demonstrates his expression for \({PN}_{p+1}^n\) is equivalent to that proved by Verreault [5] which, although it involves the reciprocals of summated sequences of Fibonacci numbers and looks somewhat similar, is also different from (34 ).
The form given in (34 ) has the advantage of having a pleasing symmetry with the equivalent expression derived in Section 3.2 for the pick-up sticks case. This symmetry emphasises the close fundamental relationship between the two cases, with the only difference between the two probability expressions being an additional combinatorial factor of \(n!\) in (34 ), and the replacement of all \(F_i^p\) terms by \(\sum_{j=1}^{i}F_i^p\) as a result of the different constraints on the length of the longest stick/stick piece for the two cases.
Also note that setting \(\left(p+1\right)=n\) in (34 ) gives \[{PN}_n^n=\;n!\prod_{i=1}^{3}\frac{1}{{SF}_i^{n-1}}\;\;\prod_{i=4}^{n}\frac{1}{{SF}_i^{n-1}-\;\sum_{j=1}^{i-3}{j{SF}_{i-j-1}^{n-1}}}. \label{eq:32p195p61n}\tag{35}\] Because the series of \(F_i^{n-1}\) numbers (all starting at \(F_1^{n-1}\)) in (35 ) go no higher than \(F_n^{n-1}\), with the exception of \({SF}_1^{n-1}\) which is equal to one, for all other series we have \({SF}_i^{n-1}=2SF_i^{n-1}\) and, therefore, by comparison with (31 ) we have \[{PN}_n^n=\;\frac{n!}{\left(n-1\right)!2^{n-1}}=\frac{n}{2^{n-1}},\] which is in agreement with the long established expression noted by Verreault [4] and for which an alternative proof was provided by Andrea and Gomez [3].
Proof of Lemma 8. To begin, we note that there are \(\left(n-1\right)!\) permutations of the order in which \(\left(n-1\right)\) breaks can be introduced into the stick at the same \(\left(n-1\right)\) positions along its length. In addition, there are \(n!\) combinations of positions at which \(\left(n-1\right)\) breaks can be introduced into the stick that all give the same combination of lengths for the resulting stick pieces (or, equivalently, there are \(n!\) permutations of the resulting orders a given combination of the lengths of the resulting stick pieces can occur in). There are, therefore, a total combination of \(n!(n-1)!\) ways in which the stick can be broken at \(\left(n-1\right)\) random positions that all give the same combination of lengths for the resulting stick pieces.
We also note that, when we arrange the resulting pieces in some defined order (in particular, in order of increasing length) and consider variations in the lengths of the individual pieces, then we only have \(\left(n-1\right)\) degrees of freedom since, once lengths have been assigned to the first \(\left(n-1\right)\) pieces, then the length of the \(n\)th piece is fixed by the constraint given in (33 ).
Finally, we note that the random position of the breaks means that the lengths of the resulting pieces have a uniform random distribution.
(?? ) follows directly from the above observations. ◻
Proof of Lemma 10. The proof is the same as that for Lemma 4 in Section 3.2 except that in the last step we use (33 ) to set \(l_n=1-\sum_{j=1}^{n-1}l_{j}\) rather than using the constraint \(l_n \leq 1\). The resulting expressions for the \(l_i^{\text{max}}\) values have exactly the same form, however we have used \(g_i\) and \(s_i\) rather than \(f_i\) and \(m_i\) to represent the linear functions and integer constants in (?? ) to emphasise that these functions and constants are different from the ones in the pick-up sticks case. ◻
Proof of Lemma 11. We first consider the case where \(p+1 \leq i \leq n-1\). Using the \(l_i^{\text{min}}\) values given by Lemma 9 and using the same approach as for the proof of Lemma 4, we can calculate \(l_i^{\text{max}}\) as follows. With the stick pieces arranged in order of increasing length, we have \[\begin{align} &l_1 = l_1, \\ &\vdots \\ &l_{i-1}=l_{i-1}, \\ &l_i=F_1^pl_i , \\ &\vdots \\ &l_{i+1} \ge F_2^pl_i+g_{i+1}(l_{i-1},l_{i-2},\ldots, l_{i-p+1}), \\ &l_{i+2} \ge F_3^pl_i+g_{i+2}(l_{i-1},l_{i-2},\ldots, l_{i-p+1}), \\ &\vdots \\ &l_n \ge F_{n-i+1}^pl_i+g_n(l_{i-1},l_{i-2},\ldots, l_{i-p+1}). \end{align}\]
Applying the constraint \(l_n \leq 1\) used in the proof of Lemma 5 gave \(m_i=F_{n-i+1}^p\) for \(p+1\leq i\leq n-1\). However, as previously noted, for the broken sticks case we instead use (33 ) to set \(l_n=1-\sum_{j=1}^{n-1}l_j\), which results in \[s_i=\sum_{j=1}^{n-i+1}F_j^p, \label{eq:32si1}\tag{36}\] for \(p+1 \leq i \leq n-1\).
The determination of the \(m_i\) values for \(i \leq p+1\) in Section 3.2 involved the identification of a number of ascending sequences of \(F_i^p\) numbers (each starting at \(F_1^p\)) extending down to the final, \(l_n\), row in (14 ). The final step was application of the constraint \(l_n \leq 1\), which resulted in the \(m_i\) values being identified as the sum of the final \(F_i^p\) numbers in each of these sequences. As set out above for the calculation of the \(s_i\) values for \(p+1 \leq i \leq n-1\), the determination of the broken stick \(s_i\) values for \(i \leq p+1\) also follows the same process as in Section 3.2 except that at the last step use (33 ) to set \(l_n=1-\sum_{j=1}^{n-1}l_j\). By comparison with the calculation above, it is clear that this results in the \(s_i\) values being identified as the sum of the sums of the sequences of \(F_i^p\) numbers identified in the Section 3.2. calculation of the equivalent \(m_i\) values, i.e. \[s_{p-q+1}= \begin{dcases} \sum_{j=1}^{n-p+q}F_j^p & \text{for } q=1,\;2, \\ \sum_{j=1}^{n-p+q}F_j^p -\sum_{k=1}^{q-2}k \sum_{j=1}^{n-p+q-k-1}F_j^p & \text{for } 3 \leq q \leq p-1. \end{dcases} \label{eq:32si2}\tag{37}\] Finally, making the transformation \(p-q+1\rightarrow i\) and using \({SF}_i^p\) to represent \(\sum_{j=1}^{i}F_i^p\), by combining (36 ) and (37 ) we have \[s_i= \begin{dcases} {SF}_{n-i+1}^p-\sum_{k=1}^{p-i-1}k{SF}_{n-i-k}^p & \text{for } 1 \leq i \leq p-2, \\ {SF}_{n-i+1}^p & \text{for } p-1 \leq i \leq n-1. \qedhere\; \end{dcases}\] ◻
Proof of Lemma 12. The proof is identical to that for Lemma 6 in Section 3.2 but with \(s_i\)’s replacing \(m_i\)’s. ◻
Proof of Lemma 13. This lemma is essentially the same as Lemma 7 in Section 3.2; the only differences are that there are now only \(\left(n-1\right)\) integrals that contribute to the probability expression and the \(s_i\) are different integer constants from the \(m_i\) that applied in the case of Lemma 7. In all other respects, the proof is the same as that for Lemma 7. ◻
Note, in this Section 4.2 we will use \(\Sigma^i\) as shorthand to denote \(\sum_{j=1}^{i}l_j\) (where the sticks are arranged in order of non-decreasing length).
For smaller values of \(p+1\), it is relatively straightforward to derive expressions for the probability that every choice of \(p+1\) from \(n\) random length sticks drawn from \([0,1]\) will form a \((p+1)\)-gon by using Lemma 3.2 but noting that there are now several separate regions to the domain of integration that is compatible with the requirement that all choices of \(p+1\) sticks will form a \((p+1)\)-gon, \({PA}_{p+1}^n.\)
We start by noting that the requirement for all choices of \(p+1\) sticks forming a \((p+1)\)-gon would be met if all \(n\) sticks had equal lengths very close to zero. Hence, the only lower bound limits on stick lengths are those that result from the sticks being arranged in order of increasing length, i.e. \[\begin{align} & l_1^{min}=0,\\ &l_i^{min}=l_{i-1} & \text{for } i \geq 2.\;\\ \end{align} \label{eq:32minimum95lengths}\tag{38}\] We then note that any set of stick length ranges compatible with the requirement for any choice of \(p+1\) sticks forming a \((p+1)\)-gon must satisfy one of two following conditions:
either \[\Sigma^p < 1 \text{ and }l_i^{\text{max}} \leq \Sigma^p\; \text{ for } p+1\leq i\leq n\; \label{eq:32condition95one}\tag{39}\]
or \[\Sigma^p\;> 1.\; \label{eq:32condition95two}\tag{40}\] In the case of the second of these conditions, the only constraint on the maximum lengths of sticks \(p+1\) to \(n\) is \(l_i^{\text{max}}=1\).
The lower bound limits on minimum stick lengths given by (38 ) mean that (39 ) can only be satisfied if the maximum lengths of sticks 1 to \(p\) are all constrained as follows \[l_i^{\text{max}A}=\frac{1 - \Sigma^{i-1}}{p+1-i}\; \text{ for } i\leq p.\; \label{eq:32maxA}\tag{41}\] If \(l_1\) exceeds the maximum length given by (41 ), then the lower bound limits on the minimum lengths of sticks 2 to \(p\) given by (38 ) mean that \(\Sigma^p\)will necessarily be \(> 1\). If \(l_1\) is less than the maximum length given by (41 ) but \(l_2\) exceeds the maximum length given by (41 ), then the lower bound limits on the minimum lengths of sticks 3 to p given by (38 ) mean that \(\Sigma^p\)will necessarily be \(> 1\), and so on up to and including the length of stick \(p\) exceeding the maximum given by (41 ).
The above considerations give rise to \(p+1\) separate regions of the domain of integration compatible with the requirement that all choices of \(p+1\) sticks will form a \((p+1)\)-gon and, hence, we have \[\begin{align} {PA}_{p+1}^n&=n!\int_{0}^{l_1^{\text{max}A}} \ldots\int_{l_{p-2}}^{l_{p-1}^{\text{max}A}}\int_{l_{p-1}}^{l_p^{\text{max}A}}\int_{l_p}^{\Sigma^p} \ldots\int_{l_{n-1}}^{\Sigma^p}{dl}_n \ldots {dl}_{p+1} {dl}_p {dl}_{p-1} \ldots {dl}_1 \\ &+n!\int_{l_1^{\text{maxA}}}^{1}\int_{l_1}^{1} \ldots\int_{l_{n-1}}^{1}{{dl}_n{{\ldots dl}_{2}dl}_1}\\ &+n!\int_{0}^{l_1^{\text{max}A}}\int_{l_2^{\text{max}A}}^{1} \int_{l_2}^{l_1} \ldots\int_{l_{n-1}}^{1} {dl}_n \ldots\;{dl}_3 {dl}_{2} {dl}_1 \\ &\vdots \\ &+n!\int_{0}^{l_1^{\text{max}A}} \ldots\int_{l_{p-2}}^{l_{p-1}^{\text{max}A}}\int_{l_{p-1}}^{1} \ldots\int_{l_{n-1}}^{1}{dl}_n \ldots {dl}_p {dl}_{p-1} \ldots {dl}_1. \end{align} \label{eq:32Full95PA95Integral}\tag{42}\] For the simplest case of \(p+1=3\), (42 ) reduces to \[\begin{align} {PA}_{3}^n&=n!\int_{0}^{\frac{1}{2}} \int_{l_1}^{1-{l_1}}\int_{l_2}^{l_1+l_2} \;\ldots\int_{l_{n-1}}^{l_1+l_2}{dl}_n\;\ldots\; {dl}_3 {dl}_2\; {dl}_1\;\\ &+n!\int_{\frac{1}{2}}^{1}\int_{l_1}^{1} \;\ldots\int_{l_{n-1}}^{1}{{dl}_n{{\ldots dl}_{2}dl}_1}\\ &+n!\int_{0}^{\frac{1}{2}}\int_{1-l_1}^{1} \int_{l_2}^{1} \;\ldots\int_{l_{n-1}}^{1}\;{dl}_n\; \ldots\;{dl}_3\;{dl}_{2}\;{dl}_1. \end{align} \label{eq:32Integral95PAA3N}\tag{43}\] It is relatively straightforward to evaluate all three integrals in (43 ) giving \[{PA}_3^n=\frac{1}{2^{n-2}}. \label{eq:32PAA3N}\tag{44}\] Applying (42 ) in the same way for the case of \(p+1=4\) results in
\[{PA}_4^n=2 \left\{ {{\left(\frac{2}{3}\right)}^{n-3}-{\left(\frac{1}{2}\right)}^{n-2}}\right\}. \label{eq:32PAA4N}\tag{45}\] The probability expressions given by (44 ) and (45 ) are much simpler than the relatively complex general expressions proved by Verreault [5] and Mukerjee [6] (which are different but equivalent) for the probability that every choice of \(p+1\) pieces of a stick broken into \(n\) parts will form a \((p+1)\)-gon. Consequently, there is no obvious relationship between the probability expressions for the broken stick and pick-up sticks models. Moreover, (42 ) for the pick-up sticks case involves \(p+1\) \(n\)-dimensional integral contributions to \(PA_{p+1}^n\), and the evaluation of each of these \(n\)-dimensional integrals is progressively more complex with increasing values of \(p+1\). Therefore, it is unclear whether (42 ) provides a basis for deriving a general expression for \(PA_{p+1}^n\) in the case of the pick-up sticks model.
Mukerjee [6] proves a theorem (Theorem 3) that the probability of \(p+1\) pieces chosen at random out of the \(n\) pieces of a broken stick, with all such choices being equally probable, do not form a \((p+1)\)-gon is equal to \(PN_{p+1}^{p+1}\), i.e. the probability of not being able to (p+1)-gon when a stick is broken into \(p+1\) pieces. This proof is based on a demonstration that the distribution of piece lengths resulting a random selection of \(p+1\) pieces from the \(n\) random length pieces of broken stick results in the same probability of not forming a \((p+1)\)-gon as the random piece length distribution from a stick broken into \(p+1\) pieces. As such, it is not dependent on the fact that the random length pieces come from broken sticks, and is equally applicable to the pick-up sticks problem where the stick lengths are randomly selected from \([0,1]\).
Applying Mukerjee’s Theorem 3 [6] to the pick-up sticks problem, we find that if \(p+1\) sticks are chosen at random out of the \(n\) sticks drawn from \([0,1]\), with all such choices equally probable, then the probability that the chosen pieces can form a \((p+1)\)-gon is given by \[PR_{p+1}^n = (1 - PN_{p+1}^{p+1}) = 1 - \frac{1}{p!}. \label{eq:Mukerjee2024}\tag{46}\]
As encouraged by Sudbury et al. [1], we have extended their method by using matrix algebra to derive a generalised expression for the probability of not being able to form a \((p+1)\)-gon from any \(p+1\) of \(n\) sticks with independent random lengths selected from a uniform distribution on \([0, 1]\).
We have also developed an alternative proof for this probability expression based on the minimum and maximum lengths of each stick compatible with the requirement of not being able to from a \((p+1)\)-gon. This alternative proof reveals that it is the geometrical constraints on the minimum and maximum stick lengths that are the underlying reason for the appearance of the Fibonacci numbers in the probability expression. The alternative geometric proof has been developed in such a way that it can, in principle, be applied to sticks drawn randomly from any (bounded or unbounded) probability distribution, provided that a suitable iterative (or other) procedure can be identified for evaluating the integrals resulting from the application of Lemma 2.
In this paper, we have applied the approach to the particular cases of sticks randomly drawn from a bounded uniform probability distribution and an unbounded exponential distribution. Remarkably, the case of sticks drawn randomly from an unbounded exponential distribution results in exactly the same expression for the probability of not being a form a \((p+1)\)-gon as for the broken stick problem. Identifying other stick length probability distributions where our geometric approach can be applied is suggested as an area for further research. In the Appendix, we provide an algorithm that can be used to generate the explicit form of the linear functions in the expressions for \(l_i^{\text{max}}\) that may be useful in any such future research.
We have also used our geometric approach to prove an alternative expression (to those previously derived by Verreault [5] and Mukerjee [6]) for the probability of not being able to form a \((p+1)\)-gon from any \(p+1\) of the \(n\) pieces formed when a stick of unit length is broken at \((n-1)\) positions. This alternative expression for the broken sticks probability has the advantage of having a pleasing symmetry with the expression we have derived for the pick-up sticks probability, thus emphasising the close fundamental relationship between the two cases. Finally, for the pick-up sticks case, we have used our geometric approach to derive the probability of all combinations of \(p+1\) of \(n\) sticks forming a \((p+1)\)-gon for the two lowest values of \(p+1\), 3 for triangles and 4 for quadrilaterals. Finding a generalised expression for this probability for any value of \(p+1\) is an outstanding problem that also merits further research.
No conflict of interests was reported by the authors.
In this appendix, we derive an algorithm that can be used to generate the explicit form of the linear functions in the expressions for \(l_i^{\text{max}}\) in the case of sticks randomly drawn from a probability distribution with an upper bound of \(1\). For a fixed \(p\geq 2\). Firstly, for \(i>p-1\), we define \(e^{(p)}_{2-k}=(0,\dots,0,1,0,\dots,0)^T\in \mathbb{R}^p\), the vector whose \(k\)-th entry is \(1\) and all other entries are \(0\) for \(k=1,\dots,p\). Subsequently, we define \(e^{(p)}_k(k\geq 2)\), via an iterative relation analogous to that of the \(p\)-order Fibonacci sequence. \[e^{(p)}_k=\sum_{j=1}^pe^{(p)}_{k-j},\quad k\geq2.\] It is easy to see that the first element of the vector \(e_k^{(p)}\) corresponds to the \(k\)-th \(p\)-order Fibonacci number \(F_k^{(p)}\). From Lemma 3, we know that for \(i\geq p\) any \(k\geq 1\), \[l_{i+k}\geq \sum_{j=1}^pl_{i+k-j}.\] Denote \(L_i=(l_i,\dots,l_{i-p+1})^T\in\mathbb{R}^p\). Then we know that \[l_{i+k}\geq e^{(p)}_{k+1}\cdot L_i,\quad k\geq 2-p.\] We denote by \(e^{(p,-1)}_k\in\mathbb{R}^{p-1}\) the vector obtained by removing first element from \(e^{(p)}_k\). For instance, \(e^{(p,-1)}_1=\mathbf{0}\). And \(L_i^{-1}=(l_{i-1},\dots,l_{i-p+1})^T\in\mathbb{R}^{p-1}\). When \(k=n-i\), we get \[l_i\leq (l_n-e^{(p,-1)}_{n-i+1}\cdot L_i^{(-1)})/F^{(p)}_{n-i+1},\] which implies \[l_i^{\text{max}}=(1-e^{(p,-1)}_{n-i+1}\cdot L_i^{(-1)})/F^{(p)}_{n-i+1}, \;i=p,p+1,\dots,n-1.\]
When \(1\le i\leq p-1\), correspondingly, we also define associated vectors \(e^{(i)}_{2-k}=(0,\dots,0,1,0,\dots,0)\in \mathbb{R}^{i}\), whose \(k\)-th entry is \(1\) and all other entries are \(0\) for \(k=1,\dots,i\). Also denote \(e^{(i)}_k=(1,0,\dots,0)^T\in \mathbb{R}^i,\) for \(k=2,\dots ,p+1-i\), since \(l_{k+i-1}\) are order statistics. Similarly, we can compute \(e^{(i)}_{k}(k> p+1-i)\) using the iterative relation \[e^{(i)}_k=\sum_{j=1}^pe^{(i)}_{k-j},\quad k> p+1-i,\] and we obtain \[l_{i+k}\geq e^{(i)}_{k+1}\cdot L_i,\quad k\geq 1,\] where \(L_i=(l_i,\dots,l_1)\in \mathbb{R}^i\), Then \[l^{\text{max}}_i=(1-e^{(i,-1)}_{n-k+1}\cdot L_i^{(-1)})/m_i.\] for \(i=1,\dots,p-1\), where \(L_i^{(-1)}=(l_{i-1},\dots,l_1)^T\in \mathbb{R}^{i-1}\), and \(m_i\) are the positive integer constants in the expressions for \(l_i^{\text{max}}\) given by Lemma 4. When \(i=1\), \(e^{(i,-1)}_{n-k+1}\) is empty, which is treated as zero in computations.
Let \(x_1, x_2, \dots, x_n\) be independent and identically distributed random variables with sample space \((0,1)\) that represent the length of \(n\) sticks, and let their probability density function be denoted by \(p(x)\). Denote by \(l_1 \le l_2 \le \dots \le l_n\leq 1\) their order statistics. The condition that these sticks cannot form a \(p+1\)-gon is that, for any \(p+1\) sticks, the sum of the lengths of the \(p\) shortest sticks is not greater than the length of the longest stick. That is \((l_1,\dots,l_n)\) should belong to the set
\[S=\{(l_1,\dots,l_n):0\leq l_1\leq \dots\leq l_n\leq 1,l_{p+i+1}\geq \sum_{j=1}^pl_{i+j},i=1,\dots,n-p-1\}.\] Therefore, the probability that no \(p+1\) sticks can be selected from them to form a \(p+1\)-gon is given by \[PN_n^{p+1}=n!\int_S\prod_{i=1}^n p(l_i)dl_n\dots dl_1.\] or \[PN_n^{p+1}=n!\int_{l_1^{min}}^1\int_{l_2^{min}}^1\dots \int_{l_n^{min} }^1\prod_{i=1}^n p(l_i)dl_n\dots dl_1.\] where \(l_i^{min}=l_{i-1},i=1,2,\dots,p\) and \(l_{i}^{min}=\sum_{j=1}^pl_{i-j},i=p+1,\dots,n\). Here, we consider the case of a uniform distribution, i.e., the probability density function is \(p(x) = 1\) for \(0 < x < 1\). Under this condition, the desired integral is precisely the volume of the region \(S\).
We perform the change of variables \(y_i = l_i - l_{i}^{min}\geq0\) for \(i = 1, 2, \dots, n\). Take \(\vec{y}=(y_1,\dots,y_n)^T\in\mathbb{R}^n\) and \(\vec{l}=(l_1,\dots,l_n)^T\in\mathbb{R}^n\). Under this change of variables, we obtain the transformation matrix \(J\in \mathbb{R}^{n\times n}\)(i.e., the Jacobian matrix). It can be seen that the entries of the matrix \(J\) satisfy: \(J_{ij} = 1\) when \(i = j\); for \(2 \le i \le p\) and \(j = i-1\), \(J_{i,i-1} = -1\); for \(p+1 \le i \le n\) and \(i-p \le j \le i-1\), \(J_{ij} = -1\); and all other entries are \(0\). As all diagonal entries \(J_{ii} = 1\) and all entries above the diagonal are zero, the determinant of \(J\) is \(1\). This means that the volume of \(S^*=JS=\{J\vec{l}:\vec{l}\in S\}\) is equal to the volume of \(S\). To compute the volume of \(S^*\), the key is to determine the upper bounds of the variables \(y_i\). Using the relation \(\vec{l}= J^{-1} \vec{y}\) together with the condition \(l_n < 1\), these upper bounds can be obtained. We know \(l_i=y_i+l_i^{\min}\). Therefore, \(l_1=y_1\), \(l_2=y_2+y_1\). Denote by \(J_i\) the \(i\)-th row vector of \(J^{-1}\), for \(i = 1, 2, \dots, n\). Thus \(l_i=J_i\cdot y\). It can be easily deduced by induction that for \(i \le p\), \(J_i\) is the row vector whose first \(i\) components are \(1\) and the remaining components are \(0\). For the remaining \(J_i\) with \(i > p\), they satisfy \[J_i=\sum_{j=1}^pJ_{i-j}+e_i.\] Where \(e_i \in \mathbb{R}^n\) denote the unit vector whose \(i\)-th component is \(1\) and all other components are \(0\). For example, \(J_{p+1}=(p,p-1,p-2,\dots,2,1,1,0,\dots,0)\). Denote \(J_n=(m_1,\dots,m_n)\). Then \(l_n=J_n\cdot \vec{y}\leq 1\). Thus, we have obtained a complete characterization of \(S^*\), namely \[S^*=\{y_1\geq0,\dots,y_n\geq0, \sum_{i=1}^nm_iy_i\leq1\}.\] Take \(z_i=m_iy_i\), its Jacobian determinant is \(\left(\prod_{i=1}^n m_i\right)\), and the integration region is defined by \(z_i \ge 0\), \(\sum z_i \le 1\), whose volume is known to be \(\frac{1}{n!}\). Therefore, we obtain the value of the original integral as \(\frac{1}{n!\prod_{i=1}^n m_i}\). Consequently, we obtain \[PN_n^{p+1}=\prod_{i=1}^n\frac{1}{m_i}.\] It is easy to see that the \(m_i\) here are exactly the same as those in Lemma (4), and their specific values are given in Lemma (5). To keep the proof in the appendix self‑contained and logically consistent, we present an alternative proof of Lemma5 here. It is easy to see that when \(i \geq p-2\), we have \(m_i = F^p_{n+1-i}\). The key point lies in the case \(i < p-2\). Before proceeding, we first prove a lemma. We need to prove the following identity.
Lemma 14. For any natural number \(t\), we have \[2^{t+1}-\sum_{j=1}^{t}j2^{t-j}-t-1=1.\]
Proof. When \(t = 0\), the summation is taken as \(0\), and a simple calculation shows that the equality holds; when \(t \geq 1\), For the summation part, we have \(\sum_{j=1}^tj2^{t-j}=2^t{\sum_{j=1}^t}j2^{-j}\). On the other hand, we can get \[\begin{align} \sum_{j=1}^tjx^{j}=x\big(\sum_{j=0}^tx^j\big)' =x\big(\frac{1-x^{t+1}}{1-x}\big)' =\frac{x-x^{t+2}}{(1-x)^2}-\frac{(t+1)x^{t+1}}{1-x}. \end{align}\] Let \(x=\frac{1}{2}\), then \[\sum_{j=1}^tj2^{t-j}=2^t\big(\frac{2^{t+1}-1}{2^t}-(t+1)\frac{1}{2^t}\big)=2^{t+1}-1-(t+1).\] Substituting, we obtain the desired identity. ◻
Fix \(i\). We know that \(m_i\) is given by the \(n\)-th term of a recurrence sequence \(\{T_j\}_{j\geq 1}\), with initial conditions \(T_1 = \dots = T_{i-1} = 0\), \(T_i = \dots = T_p = 1\). And \(T_k=\sum_{j=1}^pT_{k-j}\) for \(k> p\). Let \[T'_k=F^p_{k-i+1}-\sum_{j=1}^{p-1-i}jF^p_{k-i-j},\] note that the right-hand side clearly satisfies the recurrence relation for \(F^p_k\). Since the sequence is uniquely determined by its initial values and recurrence, it suffices to verify that the sequence \(T_k'\) meets the initial conditions of \(T_k\). First, for \(1 \leq k < i\), all of the subscript indices on the \(F_l^p\) numbers in the expression for \(T_k'\) are \(\leq 0\), and the smallest subscript value in the summation is \(k-p+1\), which occurs when \(j=p-1-i\). However, because we have \(k \geq 1\), this smallest subscript value is \(\geq 2-p\) and, therefore, all of the \(F_l^p\) numbers and, hence, \(T'_k\) are equal to zero. For \(k=i\), \(T'_k=F^p_1=1\); When \(p \geq k > i\), we have the following result \[\begin{align} T'_k&=F^p_{k-i+1}-\sum_{j=1}^{k-1-i}jF^p_{k-j-i}+\sum_{j=k-i}^{p-1-i}jF^p_{k-j-i}\\ &=2^{k-i-1}-\sum_{j=1}^{k-2-i}j2^{k-j-i-2}-(k-i-1), \end{align}\] Set \(t = k - i - 2\). Then by the lemma, we obtain \(T'_k=1\). Thus we have \(T_k=T'_k\) for all \(k\). Setting \(k=n\), we obtain \[m_i=T_n=F^p_{n-i+1}-\sum_{j=1}^{p-1-i}jF^p_{n-i-j}.\]
We may also discuss the case of a uniform distribution supported on \((a, 1)\), where \(0 < a < 1\). It suffices to perform the translation \(y_1 = l_1 - a\), and the rest of the procedure remains exactly the same as before. In this case, the region whose volume we need becomes \[S^{*}(a)=\{y_1\geq0,\dots,y_n\geq0,m_1(y_1+a)+\sum_{i=2}^nm_iy_i\leq 1\}.\] The inequality \(m_1(y_1+a)+\sum_{i=2}^nm_iy_i\leq 1\) tells us that \(a < 1/m_1\); otherwise, \(S^*(a)\) is the empty set, meaning the corresponding probability is zero. Let \(Z(a)=\{0\leq y_1\leq a,y_2\geq 0,\dots,y_n\geq 0, \sum_{i=1}^nm_iy_i\leq 1\}\), then \[|S^*(a)|=|S^*|-|Z(a)|,\] Here, \(|\cdot|\) denotes the volume. Let \(Z' = \{y_2\geq 0,\dots,y_n\geq 0, \sum_{i=1}^nm_iy_i\leq 1-m_1y_1\}\); then the volume of \(Z'\) can be found to be \((1-m_1y_1)^{n-1}\big((n-1)!\prod_{i=2}^nm_i\big)^{-1}\). Thus \[|Z|=\int_0^a\frac{(1-m_1y_1)^{n-1}}{(n-1)!\prod_{i=2}^nm_i}dy_1=\frac{1-(1-m_1a)^n}{n!\prod_{i=1}^nm_i}.\] Subtracting this from the volume of \(S^*\), we obtain that the volume of \(S^*(a)\) is \((1-m_1a)^{n}\big(n!\prod_{i=1}^nm_i\big)^{-1}\). Together with the fact that \(\prod_{i=1}^n p(l_i)\) is identically equal to \(1/(1-a)^n\), we obtain that the final probability is \[\frac{(1-m_1a)^n}{(1-a)^n}\cdot\frac{1}{\prod_{i=1}^n m_i}, \text{ for } a\leq 1/m_1.\]
MSC2020: 11B39, 33C05