pith. sign in

arxiv: 2509.11384 · v2 · submitted 2025-09-14 · 🧮 math.PR · cs.DS· math.CO

The Horton-Strahler number of butterfly trees

John Peca-Medlin This is my paper

Pith reviewed 2026-05-18 16:16 UTC · model grok-4.3

classification 🧮 math.PR cs.DSmath.CO
keywords Horton-Strahler numberbutterfly treesMarkov chainlimit theoremsbinary treesrecursive mergingbranching complexityasymptotics
0
0 comments X

The pith

The Horton-Strahler number for simple butterfly trees is an additive functional of an eight-state Markov chain.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines the Horton-Strahler number for butterfly trees, which are binary trees built by recursive merging of blocks and appear in models of parallel computation. In the simple version where merges follow an n-bit string with each bit probability p, the number reduces to the total output of an 8-state Markov chain that updates as each bit is read. This gives an almost sure linear growth rate of pq over one minus pq together with a functional central limit theorem. Simulations for the general recursively merged version support a limiting ratio near 0.445, which sits between the simple-model value of one third and the one-half limit known for ordinary random binary trees. These limits matter for predicting the depth of recursion or the register needs in structured elimination algorithms that rely on butterfly networks.

Core claim

In the simple butterfly model the Horton-Strahler number admits an exact representation as an additive functional of an explicit 8-state Markov chain driven by iid bits x_j ~ Bern(p), yielding HS(T_n^B)/n → μ_p = pq/(1-pq) almost surely together with a functional CLT with variance σ_p² = pq(1 - 3pq - 2p²q²)/(1-pq)³. For general butterfly trees the increment depends on an expanding edge profile without a finite-state reduction, yet an O(N) algorithm computes the number from the (N-1)-bit encoding and Monte Carlo simulations up to n=25 support HS(T_n^B)/n → α ≈ 0.4450 in probability, placing the general model strictly between the simple limit 1/3 and the Catalan limit 1/2.

What carries the argument

An explicit 8-state Markov chain driven by the bits of the encoding string that tracks the current Horton-Strahler number and merging profile to produce the total as an additive functional.

If this is right

  • The normalized Horton-Strahler number converges almost surely to the explicit constant pq/(1-pq) in the simple model.
  • The fluctuations around this limit obey a functional central limit theorem with the given variance formula.
  • General butterfly trees exhibit a strictly larger limiting ratio than the simple model but smaller than ordinary Catalan trees.
  • Both models admit efficient algorithms for computing the Horton-Strahler number from the bit encoding.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The finite-state reduction may apply to other families of recursively defined trees that have a fixed number of merge types.
  • In applications to register allocation the linear growth would imply that the number of registers needed scales with the depth of the butterfly network.
  • The simulated constant near 0.445 could be tested further by exact enumeration for larger n or by deriving a closed form from the edge-profile dynamics.

Load-bearing premise

That the evolution of the Horton-Strahler number under successive merges in the simple model is fully captured by the transitions of a fixed finite set of states.

What would settle it

A sequence of explicit computations showing that the ratio of the Horton-Strahler number to n for simple butterfly trees with growing n fails to approach pq/(1-pq).

Figures

Figures reproduced from arXiv: 2509.11384 by John Peca-Medlin.

Figure 1
Figure 1. Figure 1: T (54728136) presented with BST insert key labels and HS labels random BSTs, with weights proportional to the number of permutations that generate the same BST.) For example, the permutations 213 and 231 yield the same BST, T (213) = T (231), and are equiprobable with the identity permutation 123 in this model. For this consideration, of note is binary trees with n nodes can be enumerated precisely by the … view at source ↗
Figure 2
Figure 2. Figure 2: T1 ⊕ T2 and T1 ⊖ T2 formed using T1 = T (3142) and T2 = T (213) with dotted gluing edge. Updated HS labels on the merged tree highlight nodes that can have updated HS labels, with an addi￾tional light blue shade indicating a node that has HS label exceed its associated prior HS label. Theorem 1. Let T1, T2 be independent EBTs with m nodes. Then the merged tree T1 ⊕ T2 has the same support for HS, and match… view at source ↗
Figure 3
Figure 3. Figure 3: T1, T2, and their gluing T1 ⊕ T2 showing the cascading increase in HS. T1 ⊕ T2 contains a perfect binary tree of height k. Similarly, n and m can decompose 2k − 1 in a way such that T1 and T2 can be formed by removing an edge along the top right or left edge of a perfect binary tree. So one can form a composite tree with HS k using a tree with HS k − 1 and one with HS j for any 0 ≤ j ≤ k − 1 (see [PITH_FU… view at source ↗
Figure 4
Figure 4. Figure 4: Simple butterfly trees with minimal height, [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Intermediate simple butterfly trees T (10), T (100), T (1001) in building T (1001100101) Proposition 3. Let T B = T B n be a butterfly tree with N = 2n nodes. Then HS(T B) ≤ ⌊log4 N⌋. This inequality is sharp. Proof. We use induction on n. Note we will prove a further result that a butterfly with maximal HS can only have a multiplicity of nodes with this maximal HS if 4 ∤ N. This is trivial for n = 0, 1 si… view at source ↗
Figure 6
Figure 6. Figure 6: Nonsimple butterfly tree, T B(1011000010010110001011110101010), with HS labels, 32 nodes 3.1 Simple butterfly trees Simple butterfly trees are formed using gluing operations on identical copies of the previous level tree, resulting in a fractal tree structure. Of particular note, then the simple butterfly trees necessarily fill out a rectangular lattice, where the height is achieved by the node at the bott… view at source ↗
Figure 7
Figure 7. Figure 7: Histogram of normalized HSs for simple butterfly trees with 2 [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Interlacing roots of Gn(x) for successive levels Before going forward with the proof, we first state a useful theorem that captures when real-rootedness and interlacing are preserved under linear combinations. This is found as Theorem 2.1 in [LW07]: Theorem 5 (Liu-Wang, [LW07]). Let F, f, g be three real polynomials that satisfy: 1. F(x) = a(x)f(x) + b(x)g(x), such that a(x) and b(x) are real polynomials, … view at source ↗
Figure 9
Figure 9. Figure 9: Simple butterfly tree T (x) with x = 1011000011 and HS(T B(x)) = 3, along with the HS invariant butterfly trees formed using the inputs 1 − x = 0100111100 and rev(x) = 110000110 • Case 2 (last flip at xn): after removing the 2k bits used by flips, the remaining n − 2k bits are distributed among the k gaps before each flip. This yields n−k−1 k−1  possibilities. Adding the two cases gives 2 k ·  2  n − k … view at source ↗
Figure 10
Figure 10. Figure 10: Plot of µp, σ2 p We now refine this limit theorem by establishing a third proof for the CLT Corollary 2. For additive functionals of finite, irreducible, aperiodic Markov chains, the asymptotic variance can be characterized through the Poisson equation (I − P)g = h, (22) where P is the transition matrix, f is the observable and h = f − µp1 is the centered functional. (See [MT09] or [JH04] for further disc… view at source ↗
Figure 11
Figure 11. Figure 11: 60 sampled paths of Wn( 1 2 , t) with n = 10,000, shown alongside the 95% confidence envelope bounded by ±2σ1/2 √ t = ± q 8 27 t over t ∈ [0, 1]. Proposition 11 (Functional CLT). Define the process HS(T B)(p, t) = ⌊ Xnt⌋ j=1 Xj , t ∈ [0, 1] for Xj the dependent Bernoulli increments from Proposition 9. Then Wn(p, t) := √ n  1 n HS(T B)(p, t) − tµp  d −−−−→ n→∞ σpB(t), where B(t) is a standard Brownian mo… view at source ↗
Figure 12
Figure 12. Figure 12: Histogram of HS for nonsimple butterfly trees ( [PITH_FULL_IMAGE:figures/full_fig_p023_12.png] view at source ↗
read the original abstract

The Horton-Strahler (HS) number, a classical measure of branching complexity arising in hydrology and register allocation, is studied for butterfly trees, a recursive family of binary trees generated by block-merging operations. These trees arise as binary search trees of butterfly permutations, which form the $2$-Sylow subgroup of the symmetric group on $N = 2^n$ elements and appear in models of parallel computation and structured Gaussian elimination. For a single merging step applied to two independent Catalan trees with $m$ nodes, we show that HS$(\mathcal T_1 \oplus \mathcal T_2)/\log_2(2m) \to 1/2$ in probability, so the classical Catalan scaling is preserved under this restricted construction. In the simple butterfly model, where each level is formed from identical copies and encoded by an $n$-bit string $\mathbf{x}$, the HS number admits an exact representation as an additive functional of an explicit $8$-state Markov chain driven by iid bits $x_j \sim \mathrm{Bern}(p)$, and can be computed in $\mathcal O(n)$ time from $\mathbf{x}$. This yields a complete limit theory, including a strong law HS$(\mathcal T_n^B)/n \to \mu_p = pq/(1-pq)$ almost surely and a functional central limit theorem with variance $\sigma_p^2 = pq(1 - 3pq - 2p^2q^2)/(1-pq)^3$. For general butterfly trees, obtained by recursively merging independent subtrees, the increment depends on an expanding edge profile, and the process does not admit a finite-state reduction. We give an $\mathcal O(N)$ algorithm to compute the HS number directly from the $(N-1)$-bit encoding, characterize the zero-HS class, and combine exact enumeration for small $n$ with Monte Carlo simulations up to $n=25$, supporting HS$(\mathcal T_n^B)/n \to \alpha \approx 0.4450$ in probability for uniform butterfly trees, placing the general model strictly between the simple butterfly limit $1/3$ and the Catalan limit $1/2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies the Horton-Strahler (HS) number on butterfly trees arising from block-merging constructions. For a single merge of two independent Catalan trees of size m it proves HS(T1 ⊕ T2)/log2(2m) → 1/2 in probability. In the simple butterfly model driven by an n-bit string with bias p it represents the HS number as an additive functional of an explicit 8-state Markov chain, yielding the strong law HS(T_n^B)/n → μ_p = pq/(1-pq) a.s. together with an explicit functional CLT. For the general uniform butterfly model it supplies an O(N) algorithm, characterizes the zero-HS class, and combines exact enumeration with Monte Carlo runs up to n=25 to support the claim that HS(T_n^B)/n → α ≈ 0.4450 in probability, placing the constant strictly between the simple-model value 1/3 and the Catalan value 1/2.

Significance. If the simulation-supported limit holds, the work supplies a new explicit constant for branching complexity in a recursively structured family of trees that appears in parallel computation and structured linear algebra. The exact Markov-chain analysis and closed-form limits for the simple model constitute a clear technical contribution; the O(N) algorithm is also a practical strength.

major comments (2)
  1. [General butterfly trees] General-model section: the numerical support for HS(T_n^B)/n → α ≈ 0.4450 in probability rests on Monte Carlo simulations whose largest size is n=25. Because the HS process on the general model depends on an expanding edge profile and admits no finite-state reduction, the rate of convergence is not controlled by the simple-model theory; without reported standard errors, effective sample sizes, or diagnostic plots of HS/n versus n, it is unclear whether the observed value at n=25 has stabilized to the claimed three-decimal accuracy.
  2. [Single merging step] Single-merge proposition: the statement that HS(T1 ⊕ T2)/log2(2m) → 1/2 in probability is used to argue that Catalan scaling is preserved under the restricted construction. The argument relies on the specific block-merging rule; a short explicit bound on the probability of deviation (or a reference to the underlying concentration tool) would make the claim fully self-contained.
minor comments (2)
  1. [Notation] The notation T_n^B is used both for the simple model (bit-string driven) and the general recursive model; a brief clarifying sentence or subscript distinction would prevent reader confusion.
  2. [Simple-model CLT] The variance formula σ_p^2 = pq(1 - 3pq - 2p^2 q^2)/(1-pq)^3 is stated without derivation; a one-line sketch of the quadratic-form computation from the 8-state chain would be helpful.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We appreciate the recognition of the exact Markov-chain analysis for the simple model, the O(N) algorithm, and the overall contribution. We respond point-by-point to the major comments below and will make the indicated revisions to strengthen the presentation.

read point-by-point responses

  1. Referee: [General butterfly trees] General-model section: the numerical support for HS(T_n^B)/n → α ≈ 0.4450 in probability rests on Monte Carlo simulations whose largest size is n=25. Because the HS process on the general model depends on an expanding edge profile and admits no finite-state reduction, the rate of convergence is not controlled by the simple-model theory; without reported standard errors, effective sample sizes, or diagnostic plots of HS/n versus n, it is unclear whether the observed value at n=25 has stabilized to the claimed three-decimal accuracy.

    Authors: We thank the referee for this observation. The manuscript explicitly notes that the general model lacks a finite-state reduction, so the simple-model convergence theory does not apply. To address the concern, the revision will add: (i) standard errors computed from 10,000 independent Monte Carlo runs at each n, (ii) a diagnostic plot of the sample mean HS/n versus n together with error bars, and (iii) a brief discussion of effective sample size. These additions will better document the observed stabilization near 0.445 while preserving the original claim that the simulations support a limit strictly between 1/3 and 1/2. The raw data will be made available as supplementary material. revision: yes

  2. Referee: [Single merging step] Single-merge proposition: the statement that HS(T1 ⊕ T2)/log2(2m) → 1/2 in probability is used to argue that Catalan scaling is preserved under the restricted construction. The argument relies on the specific block-merging rule; a short explicit bound on the probability of deviation (or a reference to the underlying concentration tool) would make the claim fully self-contained.

    Authors: We agree that an explicit deviation bound would render the single-merge result more self-contained. In the revision we will insert a short paragraph immediately after the proposition stating that, for any ε > 0, there exist C, δ > 0 such that P(|HS(T1 ⊕ T2)/log_2(2m) − 1/2| > ε) ≤ C m^{−δ}. This polynomial bound follows directly from the sub-Gaussian tail estimates for the Horton-Strahler number on random Catalan trees that are already used in the proof (and referenced in the manuscript). The addition clarifies the argument without changing the statement or its proof. revision: yes

Circularity Check

0 steps flagged

No circularity: limits derived from standard Markov theory and external simulations

full rationale

The simple-model limit follows from applying standard Markov-chain ergodic theory to an explicitly constructed 8-state chain driven by iid bits; the functional is additive by definition of the HS process on the bit string, but the chain itself is derived from the tree recursion rather than presupposing the limit. The general-model claim is an empirical estimate obtained from exact enumeration on small n plus Monte Carlo up to n=25; this is presented as supporting evidence for convergence in probability, not as a fitted parameter renamed as a prediction. No self-citations, uniqueness theorems, or ansatzes imported from prior author work appear in the derivation chain. The paper is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The paper relies on standard probabilistic convergence results and the definitional properties of the butterfly merging construction; the only empirical element is the simulation estimate of alpha, which is not introduced as an axiom but reported as observed.

free parameters (2)
  • p
    Bernoulli probability governing the iid bits in the simple butterfly model encoding.
  • alpha
    Approximate limiting constant for general uniform butterfly trees, obtained from Monte Carlo simulations up to n=25.
axioms (2)
  • standard math Standard strong law and functional central limit theorems apply to additive functionals of finite-state Markov chains
    Invoked to obtain the almost-sure limit and CLT once the HS process is represented as such a functional.
  • domain assumption Butterfly trees are generated by the stated recursive block-merging process from Catalan trees or identical copies
    Defines both the simple and general models throughout the abstract.

pith-pipeline@v0.9.0 · 5934 in / 1532 out tokens · 68450 ms · 2026-05-18T16:16:18.833950+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages · 1 internal anchor

  1. [1]

    Refined H orton-- S trahler numbers I : a discrete bijection

    Louigi Addario-Berry, Marie Albenque, Serte Donderwinkel, and Robin Khanfir. Refined H orton-- S trahler numbers I : a discrete bijection. arXiv preprint arXiv:2406.03025 , 2024

    work page arXiv 2024

  2. [2]

    Dimension and randomness in groups acting on rooted trees

    Miklós Abért and Bálint Virág. Dimension and randomness in groups acting on rooted trees. Journal of the American Mathematical Society , 18(1):157–192, 2005

    work page 2005

  3. [3]

    The Brownian limit of separable permutations

    Fr \'e d \'e rique Bassino, Mathilde Bouvel, Valentin F \'e ray, Lucas Gerin, and Adeline Pierrot. The Brownian limit of separable permutations. The Annals of Probability , 46(4):2134--2189, 2018

    work page 2018

  4. [4]

    Scaling limits of permutation classes with a finite specification: a dichotomy

    Fr \'e d \'e rique Bassino, M \'e lanie Bouvel, Valentin F \'e ray, Lucas Gerin, Mustazee Maazoun, and Adrien Pierrot. Scaling limits of permutation classes with a finite specification: a dichotomy. Advances in Mathematics , 405:108513, 2022

    work page 2022

  5. [5]

    The H orton– S trahler number of conditioned G alton– W atson trees

    Anna Brandenberger, Luc Devroye, and Tommy Reddad. The H orton– S trahler number of conditioned G alton– W atson trees. Electronic Journal of Probability , 26:1--29, 2021

    work page 2021

  6. [6]

    Blelloch, Daniel Ferizovic, and Yihan Sun

    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. Just join for parallel ordered sets. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , pages 253--264, 2016

    work page 2016

  7. [7]

    Permutons, meanders, and SLE -decorated L iouville quantum gravity

    Jacopo Borga, Ewain Gwynne, and Xin Sun. Permutons, meanders, and SLE -decorated L iouville quantum gravity. Journal of the European Mathematical Society , 2025. Published online 12 June 2025, to appear

    work page 2025

  8. [8]

    Baxter permuton and L iouville quantum gravity

    Jacopo Borga, Nina Holden, Xin Sun, and Pu Yu. Baxter permuton and L iouville quantum gravity. Probability Theory and Related Fields , 186(3–4):1225--1273, 2023

    work page 2023

  9. [9]

    Baboulin, X.S

    M. Baboulin, X.S. Li, and F. Rouet. Using random butterfly transformations to avoid pivoting in sparse direct methods. In: Proc. of Int. Con. on Vector and Par. Proc. , 2014

    work page 2014

  10. [10]

    A note on the height of binary search trees

    Luc Devroye. A note on the height of binary search trees. Journal of the ACM (JACM) , 33(3):489--498, 1986

    work page 1986

  11. [11]

    A note on the H orton- S trahler number for random trees

    Luc Devroye and Paul Kruszewski. A note on the H orton- S trahler number for random trees. Information Processing Letters , 56(2):95--99, 1995

    work page 1995

  12. [12]

    Horton-- S trahler number of a tree

    Philippe Flajolet. Horton-- S trahler number of a tree. Discrete Mathematics , 20(3):247--259, 1977

    work page 1977

  13. [13]

    The average height of binary trees and other simple trees

    Philippe Flajolet and Andrew Odlyzko. The average height of binary trees and other simple trees. Journal of Computer and System Sciences , 25(2):171--213, 1982

    work page 1982

  14. [14]

    Vuillemin

    Philippe Flajolet, Jean-Claude Raoult, and Jean E. Vuillemin. The number of registers required for evaluating arithmetic expressions. Theoretical Computer Science , 9(1):99--125, 1979

    work page 1979

  15. [15]

    L. H. Harper. Stirling behaviour is asymptotically normal. Annals of Mathematical Statistics , 38:410--414, 1967

    work page 1967

  16. [16]

    Parallel binary search tree construction inspired by thread-level speculation

    Hiroaki Hirata and Atsushi Nunome. Parallel binary search tree construction inspired by thread-level speculation. In 2022 23rd ACIS International Summer Virtual Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD-Summer) , pages 74--81, 2022

    work page 2022

  17. [17]

    Robert E. Horton. Erosional development of streams and their drainage basins: Hydrophysical approach to quantitative morphology. Geological Society of America Bulletin , 56(3):275--370, 1945

    work page 1945

  18. [18]

    On the number of heaps and the cost of heap construction

    Hsien-Kuei Hwang and Jean-Marc Steyaert. On the number of heaps and the cost of heap construction. In Brigitte Chauvin, Philippe Flajolet, Danièle Gardy, and Abdelkader Mokkadem, editors, Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities , Trends in Mathematics, pages 294--310. Birkhäuser, Basel, 2002

    work page 2002

  19. [19]

    H.-K. Hwang. On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics , 19(3):329--343, 1998

    work page 1998

  20. [20]

    Jones and James P

    Galin L. Jones and James P. Hobert. Markov chain M onte C arlo: convergence and practical implementation. The American Statistician , 58(4):235--244, 2004

    work page 2004

  21. [21]

    The expected H orton-- S trahler number of a random tree

    Robert Kemp. The expected H orton-- S trahler number of a random tree. Discrete Mathematics , 23(1):37--52, 1978

    work page 1978

  22. [22]

    Fluctuations of the H orton– S trahler number of stable G alton– W atson trees

    Robin Khanfir. Fluctuations of the H orton– S trahler number of stable G alton– W atson trees. Annals of Probability , to appear. arXiv preprint arXiv:2401.13771

    work page arXiv

  23. [23]

    The H orton– S trahler number of G alton– W atson trees with possibly infinite variance

    Robin Khanfir. The H orton– S trahler number of G alton– W atson trees with possibly infinite variance. Annals of Applied Probability , to appear. arXiv preprint arXiv:2307.05983

    work page arXiv

  24. [24]

    Sur certaines martingales de B eno \^i t M andelbrot

    Jean-Pierre Kahane and Jacques Peyri \`e re. Sur certaines martingales de B eno \^i t M andelbrot. Advances in Mathematics , 22(2):131--145, 1976

    work page 1976

  25. [25]

    A note on the H orton- S trahler number for random binary search trees

    Paul Kruszewski. A note on the H orton- S trahler number for random binary search trees. Information Processing Letters , 69(1):47--51, 1999

    work page 1999

  26. [26]

    Integrability of L iouville theory: Proof of the DOZZ formula

    Antti Kupiainen, R \'e mi Rhodes, and Vincent Vargas. Integrability of L iouville theory: Proof of the DOZZ formula. Annals of Mathematics , 191(1):81--166, 2020

    work page 2020

  27. [27]

    Generalizing random butterfly transforms to arbitrary matrix sizes

    Neil Lindquist, Piotr Luszczek, and Jack Dongarra. Generalizing random butterfly transforms to arbitrary matrix sizes. ACM Transactions on Mathematical Software , 50(4):1--23, 2024

    work page 2024

  28. [28]

    Liu and Yi Wang

    Lily L. Liu and Yi Wang. A unified approach to polynomial sequences with only real zeros. Advances in Applied Mathematics , 38(4):542--560, 2007

    work page 2007

  29. [29]

    On the B rownian separable permuton

    Mustazee Maazoun. On the B rownian separable permuton. Combinatorics, Probability and Computing , 29(2):241--266, 2020

    work page 2020

  30. [30]

    Multiplications al \'e atoires it \'e r \'e es et distributions invariantes par moyenne pond \'e r \'e e al \'e atoire

    Beno \^i t Mandelbrot. Multiplications al \'e atoires it \'e r \'e es et distributions invariantes par moyenne pond \'e r \'e e al \'e atoire. Comptes Rendus de l'Acad \'e mie des Sciences de Paris, S \'e rie A , 278:289--292, 1974

    work page 1974

  31. [31]

    Multiplications al \'e atoires it \'e r \'e es et distributions invariantes par moyenne pond \'e r \'e e al \'e atoire: quelques extensions

    Beno \^i t Mandelbrot. Multiplications al \'e atoires it \'e r \'e es et distributions invariantes par moyenne pond \'e r \'e e al \'e atoire: quelques extensions. Comptes Rendus de l'Acad \'e mie des Sciences de Paris, S \'e rie A , 278:355--358, 1974

    work page 1974

  32. [32]

    Mandelbrot

    Beno \^i t B. Mandelbrot. Intermittent turbulence in self-similar cascades: divergence of high moments and dimension of the carrier. Journal of Fluid Mechanics , 62:331--358, 1974

    work page 1974

  33. [33]

    Amram Meir and John W. Moon. On H orton-- S trahler numbers for random trees. Journal of the ACM , 27(2):384--392, 1980

    work page 1980

  34. [34]

    Meyn and Richard L

    Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability . Cambridge Mathematical Library. Cambridge University Press, 2nd edition, 2009

    work page 2009

  35. [35]

    Stott Parker

    D. Stott Parker. Random butterfly transformations with applications in computational linear algebra. Tech. rep., UCLA , 1995

    work page 1995

  36. [36]

    Numerical, spectral, and group properties of random butterfly matrices

    John Peca-Medlin. Numerical, spectral, and group properties of random butterfly matrices . PhD thesis, University of California, Irvine, 2021. ProQuest ID: PecaMedlin\_uci\_0030D\_17221. Merritt ID: ark:\/13030\/m5ck4tnm

    work page 2021

  37. [37]

    Complete pivoting growth of butterfly matrices and butterfly Hadamard matrices

    John Peca-Medlin. Complete pivoting growth of butterfly matrices and butterfly H adamard matrices. arXiv preprint arXiv:2410.06477 , 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  38. [38]

    Distribution of the number of pivots needed using G aussian elimination with partial pivoting on random matrices

    John Peca-Medlin. Distribution of the number of pivots needed using G aussian elimination with partial pivoting on random matrices. Ann. Appl. Probab. , 34(2):2294--2325, 2024

    work page 2024

  39. [39]

    Growth factors of random butterfly matrices and the stability of avoiding pivoting

    John Peca-Medlin and Thomas Trogdon. Growth factors of random butterfly matrices and the stability of avoiding pivoting. SIAM J. Matrix Anal. Appl. , 44(3):945--970, 2023

    work page 2023

  40. [40]

    On the longest increasing subsequence and number of cycles of butterfly permutations

    John Peca-Medlin and Chenyang Zhong. On the longest increasing subsequence and number of cycles of butterfly permutations. arXiv preprint arXiv:2410.20952 , 2024

    work page arXiv 2024

  41. [41]

    Heights of butterfly trees

    John Peca-Medlin and Chenyang Zhong. Heights of butterfly trees. arXiv preprint arXiv:2507.04505 , 2025

    work page arXiv 2025

  42. [42]

    Robin Pemantle and Mark C. Wilson. Analytic Combinatorics in Several Variables , volume 140 of Cambridge Studies in Advanced Mathematics . Cambridge University Press, 2013

    work page 2013

  43. [43]

    Gaussian multiplicative chaos and applications: A review

    R \'e mi Rhodes and Vincent Vargas. Gaussian multiplicative chaos and applications: A review. Probability Surveys , 11:315--392, 2014

    work page 2014

  44. [44]

    Richard P. Stanley. Catalan Numbers , volume no. 153 of Cambridge Studies in Advanced Mathematics . Cambridge University Press, 2015. Contains 214 combinatorial interpretations of the Catalan numbers and additional exercises

    work page 2015

  45. [45]

    Strahler

    Arthur N. Strahler. Hypsometric (area-altitude) analysis of erosional topography. Geological Society of America Bulletin , 63(11):1117--1142, 1952

    work page 1952

  46. [46]

    Orthogonal Polynomials , volume 23 of American Mathematical Society Colloquium Publications

    G \'a bor Szeg o . Orthogonal Polynomials , volume 23 of American Mathematical Society Colloquium Publications . American Mathematical Society, Providence, RI, 4 edition, 1975

    work page 1975