Bounded Discrete Bridges

Pierre Nicodeme

REVIEW 4 major objections 7 minor 13 references

Bounded Discrete Bridges

T0 review · 4 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves the Rayleigh limit law for the height of discrete bridges, correcting a flawed 2010 proof and extending the result to periodic walks.

desk verdict A genuine repair attempt with a new periodic case and useful expanded asymptotics, but the non-integer height proof has a branch-cut gap that blocks the main theorem as stated. read the letter →

arxiv 2506.02982 v2 pith:VHRFUT3B submitted 2025-06-03 math.PR cs.DM

Pierre Nicodeme This is my paper

classification math.PRcs.DM MSC 60F0560G5005A1505A16

keywords discretebridgesRayleighlimitlawperiodicwalkskernelmethodHankelintegralssemi-largepowersHermitepolynomialsLukasiewicz

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a limit law for the upper tail of the height of discrete bridges: for a directed lattice walk whose characteristic Laurent polynomial has no repeated factor, the probability that a bridge of length $n$ ever reaches above $x\sigma\sqrt{n}$ tends to $e^{-2x^2\rho/\tau^2}$ as $n\to\infty$, with error term $O(1/\sqrt{n})$. The target is to make rigorous a result announced in 2010, whose published proof used a root-domination property on a disk where the property can fail. The new argument applies the domination property only on a thin lens contour around the positive real axis, and for periodic walks around the $p$ rotated rays, then passes to Hankel contours at the dominant singularity. If the proof is right, the Rayleigh law is settled for both aperiodic and periodic walks, and the higher-order expansions for Lukasiewicz bridges acquire a systematic Hermite-polynomial structure.

What carries the argument

The machine is the kernel equation $1-zP(u)=0$ with $d$ large roots $v_k(z)$ and $c$ small roots $u_j(z)$. The generating function of bridges above height $h$ is expressed as $$B_h(z)=z\sum_{j=1}^{c}\sum_{k=1}^{d}\left(\frac{u_j(z)}{v_k(z)}\right)^h\frac{Q_k(u_j(z))}{Q_k(v_k(z))}\frac{u'_j(z)}{v_k(z)},$$ and the load is to extract $[z^n]B_h(z)$. The device that repairs the earlier proof is a contour shaped like a thin lens around the interval $]0,\rho[$ (and, in the periodic case, around the $p$ rotated copies), so that the domination inequalities $|u_j(z)|<u_1(z)<v_1(z)<|v_k(z)|$ hold on the integration paths by continuity even though they fail on the full disk $|z|<\rho$. The contour is then shrunk, the contributions away from the real axis are shown to be $o(r^n)$, and the dominant piece is evaluated by a Hankel contour at $z=\rho$ with the semi-large-powers scale $h=x\sigma\sqrt n$; the resulting Gamma integral evaluates to $e^{-2x^2\rho/\tau^2}$.

What would settle it

One concrete check: for a reduced periodic walk such as $P(u)=u^9+u^3+u^{-3}$, evaluate $|1/P(u)|$ numerically on the circle $|u|=\tau$; any maximum point other than $\kappa_\ell\tau=\tau e^{2\pi i\ell/p}$ refutes Lemma 4 and with it Theorem 6. A second check targets the aperiodic contour: for the paper's own counter-example $P(u)=u+3/u+1/u^2$, compute the integral of $B_h(z)/z^{n+1}$ along the small arc $\Gamma_r$; if it is not $o(r^n)$ as $r\to0$ with $s=o(r^{3n})$, the key asymptotic simplification does not hold.

Watch

Extended reading notes

Core claim

The paper's central claim, stated as Theorems 3 and 6, is that under Assumption 1 the bridge-height tail satisfies $$\$beta_n^{{>x\sigma\sqrt{n}}$} = \frac{$b_n^{{>h}}$}{$b_n^{{<\infty}}$} = $e^{{-2x^2\rho/\tau^2}}$\left(1+O\left(\frac1{\sqrt n}\right)\right), \qquad x>0,$$ where $\tau$ is the unique positive solution of $P'(\tau)=0$, $\rho=1/P(\tau)$, and $\sigma=\sqrt{P''(\tau)}$. For walks with fundamental period $p$, bridges of length $n$ exist only when $p$ divides $n$, and the same ratio holds: the $p$ symmetric saddle-point contributions multiply both numerator and denominator by $p$ and cancel. The law is independent of the walk's drift and of $\sigma$, so in the zero-drift probabilistic case $P(1)=1$, $P'(1)=0$ it reduces to the familiar $e^{-2x^2}$ Rayleigh tail.

Load-bearing premise

The load-bearing premise is that the root-domination inequalities survive on the thin contour around the positive real axis and, in the periodic case, that $|1/P(u)|$ peaks on the circle $|u|=\tau$ only at the $p$ points $\kappa_\ell\tau$; if this fails, the asymptotic simplifications collapse and the Rayleigh theorem does not follow.

Editorial extensions

If this is right

The Rayleigh limit $e^{-2x^2\rho/\tau^2}$ is established for the height of aperiodic directed-lattice bridges, with explicit error $O(1/\sqrt n)$, closing the gap left by the 2010 proof.
Periodic walks, not treated in 2010, obey the same law: only lengths $n=mp$ contribute, the $p$ saddle points multiply both numerator and denominator, and the ratio still converges to $e^{-2x^2\rho/\tau^2}$.
Because the limit is independent of drift and of $\sigma$, all aperiodic walks with the same ratio $\rho/\tau^2$ share the same Brownian tail; zero-drift walks with $P(1)=1$ have limit simply $e^{-2x^2}$.
For Lukasiewicz bridges the method yields explicit higher-order corrections whose coefficients are probabilists' Hermite polynomials $\mathrm{He}_i(4x)$; the numerical test against the reflection principle for the $\pm1$ walk agrees to about $2\times10^{-8}$ at $n=64$, $h=9$.
The $O(1/\sqrt n)$ proximity between discrete and Brownian first-passage points supports the paper's conjecture that the highest and lowest points of long positive and negative arches of discrete bridges are tight to the Brownian limit.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The square-free Assumption 1 looks like a proof artefact rather than a property of the limit: powers such as $P(u)=((u+1/u)/2)^k$ have repeated factors but correspond to reducible periodic walks, and a natural stress test is whether a modified saddle argument yields the same $e^{-2x^2\rho/\tau^2}$ tail for them.
Since the limit depends only on $\rho/\tau^2$, walks with identical $\tau$ and $\rho$ but different jump sets are predicted to be indistinguishable at leading order; the Hermite correction terms give a concrete $1/\sqrt n$ observable that would separate them, which could be checked by simulation.
Lemma 4 is the compressed point of the periodic proof; replacing it by a direct trigonometric argument based on the period-$p$ structure would make the periodic theorem checkable without continuity heuristics and could extend the method to repeated-factor characteristic polynomials.
The tightness conjecture for arch extrema could be probed on Duchon-style walks $P(u)=u^d+u^{-c}$ by simulating bridges and comparing the distribution of the maximum of positive arches with the Brownian-excursion extreme, expecting the same $O(1/\sqrt n)$ coupling error.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper is worth taking seriously. It openly corrects the known flaw in Banderier-Nicodeme 2010, replaces the invalid disk-wide domination argument with a thin contour around the real segment, and adds a periodic-case Rayleigh theorem and higher-order Lukasiewicz expansions with Hermite polynomials. Those are real contributions, and the numerical check against the Andre reflection principle is a legitimate sanity check. The author is honest about what is inherited and what is new.

The soft spots are concentrated in the proof of Lemma 2 for non-integer h. The claim that the Gamma_r integral of z^{-n+h} z^alpha is o(r^n) does not survive the almost-closed contour: for generic non-integer h, the two endpoints of the gap differ by the phase e^{2pi i h}, and the integral is of order r^{1-n+h+alpha}, which is not smaller than r^n. The proof's replacement of (1-t/n)^{-n} by e^t and integration as if the integrand were entire hides exactly this branch issue. Since the theorem states x in (0,infty), non-integer h is the generic case; pointing to the integer-h proof in Section 4.5.1 does not cover it. The periodic non-integer case is explicitly left unfinished, so Lemma 6 inherits the same problem.

Smaller issues are easy to list: Equation (54) is missing the 1/tau factor, the KMT inequality in Theorem 5 has the direction reversed, and Lemma 4 is compressed enough that the maximum claim on the circle |u|=tau needs a fuller proof. None of these are fatal by themselves, but together with the Lemma 2 gap they mean the manuscript is not yet a complete rigorous proof of the stated theorems.

For whom is this useful? Specialists in lattice path asymptotics will want to know about the periodic treatment and the Hermite structure, and the paper is a good map of where the 2010 proof went wrong. I would not cite the current version for the main theorem until the non-integer h argument is fixed or the theorem is narrowed to integer h. I would still send it to a serious referee: the question is important, the author is engaging the right difficulties, and the periodic and expansion results deserve a careful check.

Referee Report

4 major / 7 minor

Summary. The paper claims to give a rigorous proof, for aperiodic and for periodic directed lattice walks whose characteristic polynomial has no repeated factor, that the probability that a bridge of length n exceeds height h = xσ√n converges to the Rayleigh tail e^{-2x^2ρ/τ^2} with an explicit O(1/√n) error. The proof strategy is to avoid the invalid disk-wide root-domination estimate used by Banderier and Nicodème by integrating on a thin contour around the positive real segment, then applying singularity analysis and Hankel integrals. The paper also gives higher-order expansions for Łukasiewicz bridges involving Hermite polynomials, a numerical check against the André reflection principle for Dyck bridges, and a conjecture on tightness of arch extrema.

Significance. If the main theorems were established, the paper would correct a genuine gap in the 2010 proof of Banderier and Nicodème, extend the result to periodic walks, and provide a useful, checkable expansion machinery for Łukasiewicz bridges. The numerical verification against the exact André formula for Dyck bridges is a definite strength, as is the careful identification of the Wallner counterexample to disk-wide domination. However, the central proof as written fails for non-integer heights: the key estimate Lemma 2 is false in the stated generality, and the periodic non-integer case is explicitly left unfinished. The Rayleigh law itself is a known result, so the paper's contribution is the analytic proof and its refinements, not the discovery of the limit law.

major comments (4)

[§3.4, Lemma 2 and Eqs (37)–(42)] For non-integer h, the estimate Jjk = o(r^n) is false. Since h = xσ√n is not an integer for generic x, the integrand z^{-n+h+α} has a branch point at z = 0. As the gap in Γr closes, ∫_{Γr} z^{-n+h+α} dz tends to (e^{2π i h} - 1)/(i(-n+h+α+1)) r^{1-n+h+α}, which is not o(r^n); because h ∼ √n, the right-hand side is much larger than r^n as r → 0. The manipulations in Eqs (38)–(41) integrate the truncated expansion (1 - t/n)^h as if it were a single-valued entire function on the whole contour, which is only legitimate when h is an integer. Consequently Lemma 2 and Eq (42) do not hold in the stated generality, and Theorem 3 is not proved for all x ∈ (0,∞).
[§4.5.2] The non-integer periodic case is not proved: the text states "We omit the end of the proof that follows the same steps as in the aperiodic case." Because the aperiodic steps fail for non-integer h (see previous comment), this omission cannot be repaired by copying them. The same branch-point obstruction applies to each arc Γr,ℓ in Lemma 6. Hence Theorem 6 is not established for x ∈ (0,∞).
[§3.5, Eq (54)] Equation (54) is missing a factor 1/τ. Theorem 1 gives V_n = ρ^{-n}/(τ σ √(2πρ n)) (1 + O(1/n)), not ρ^{-n}/(σ √(2πρ n)). With the displayed formula, the ratio I0 / b_n^{<∞} in Eqs (56)–(58) would acquire an extra factor τ and would not equal e^{-2x^2ρ/τ^2}. The authors should correct Eq (54) and recheck the subsequent ratio computation.
[§4.1, Lemma 4] The proof of Lemma 4 is too compressed to be verifiable. In the rational case y = g + x/p, the assertions "There exists an integer k and m = kx ≤ δ such that P(χ_m) = τ" and "This implies that q is a period of P(u)" are not justified, and the step from a finite set K to a smallest argument 2π/q with q > p needs a clearer argument. Since Lemma 4 underpins the periodic saddle-point analysis and the claim that no other singularities lie in |z| ≤ ρ, the periodic theorem requires a complete proof of this lemma.

minor comments (7)

[§3.6, Eq (61)] The inequality in Theorem 5 is reversed: the KMT theorem bounds the probability that the maximum deviation exceeds C log n + x, so the left-hand side should be Pr(max |S_k - B_k| > C log n + x).
[§3.4, Eq (24)] The error term O(Â^n) should be O(Â^h) (or O(e^{-c h})) since h = Θ(√n); as written, the claim is stronger than what the domination bound actually gives.
[Figure 3 caption] The caption writes "s = o(r^4 r)", which appears to be a typo; Lemma 2 uses s = o(r^{3n}) and Eq (44) uses s = o(r^{4n}).
[§4.5.2 and Lemma 6] The notation alternates between B(z) and B_h(z) without consistency (e.g., Eq (45) defines B_h(z) while Lemma 6 integrates B(z)); please unify the notation.
[§5.2.2, Eq (107)] The notation He'1_k is undefined and appears to be a typo for He1_k; the recurrence and the projection-to-1 notation should be clarified.
[Figure 5] The Maple worksheet output is raw and hard to read; consider presenting the numerical comparison in a table and moving the worksheet to supplementary material.
[References] Reference [13] is a personal communication; since the Wallner counterexample motivates the paper, it would help to describe it in the text with explicit numerical parameters.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the Rayleigh limit law is derived from the kernel method and singularity analysis, with acknowledged corrections to the author's earlier work; self-citations are not load-bearing.

full rationale

The paper's central claim (Theorems 3 and 6) is extracted by computing the generating function B_h(z) via the kernel method, justifying a contour on which the relevant root domination holds, and then applying singularity analysis / Hankel integrals to obtain e^{-2x^2 rho / tau^2}. The target exponential appears at the end of the computation (Eqs. 52-58), not as an input or fitted parameter. No parameter is fitted to a subset of data and then renamed as a prediction; the normalization b^{<infinity}_n is taken from the external benchmark Banderier-Flajolet [1], not from a self-referential construction. The author's earlier work [3] is explicitly criticized for an invalid asymptotic simplification and is corrected by a new contour argument (Lemma 2, Figure 3), so the reliance on [3] is not load-bearing. The periodic case is developed in-paper (Lemmas 3-7) with a proof sketch of Lemma 4; its compression and the omitted details in Section 4.5.2 are correctness/rigor concerns, not circularity. The numerical check in Section 5.2 uses the independent Désiré André reflection formula, providing an external benchmark. The Brownian-limit discussion in Section 3.6 is speculative and not used to prove the main theorems. Overall, the derivation is self-contained and no circular step reducing to the claimed result was identified.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No data-fitting parameters. The constants tau, rho, sigma are structural roots of the characteristic polynomial P. The 'projection to 1' in Section 5.2.2 is an exploratory ansatz for identifying Hermite polynomials, not a fitted parameter. The central theorem rests on the domain restriction of Assumption 1 and on the inherited domination lemma from Banderier-Flajolet.

assumptions (4)

domain assumption Assumption 1: no common root of P' and P'' (described in words as 'no repeated factor')
Invoked throughout; ensures all singular points of the kernel are of order one so secondary Hankel integrals are negligible (Section 3.5). The wording is imprecise: for Dyck^2 the displayed condition actually holds.
standard math Domination of kernel roots on the positive real segment (Lemma 1 of [1]) and its extension by continuity to a thin strip around the segment
Used in Section 3.4.1 to reduce B_h(z) to the dominant term (u1/v1)^h. Proven in [1] for aperiodic walks; the paper relies on the extension to the strip.
domain assumption Lemma 4: for a periodic walk, |P(u)| attains its maximum on |u| = tau only at kappa_l tau
New lemma for the periodic case, proved sketchily in Section 4.1; it carries the periodic extension.
standard math Standard singularity analysis, Hankel contour representations, and saddle-point estimates from [7,8]
Used for coefficient extraction and for the Gamma function identities in Section 3.5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bounded Discrete Bridges." pith.science (2026). https://pith.science/paper/VHRFUT3B

@misc{pith2026250602982,
  author       = {Pith},
  title        = {Pith review of: Bounded Discrete Bridges},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VHRFUT3B}},
  note         = {Machine review of arXiv:2506.02982}
}

abstract

In 2010 Banderier and Nicodeme consider the height of bounded discrete bridges and conclude to a limiting Rayleigh distribution. This result is correct although their proof is partly erroneous. They make asymptotic simplifications based upon dominance properties of the roots of the kernel of the walk within a disk centered at the origin, but these dominance properties apply only upon a positive real segment. However the very good agreement of simulations with their asymptotic expansion of the probability distribution in case of {\L}ukasiewicz bridges let us think that their proof could be corrected. This is the scope of the present article which provides a proof using the dominance property only in its domain of validity. We also consider the case of periodic walks, a topic not considered in Banderier-Nicodeme2010. We limit ourselves to walks whose characteristic polynomial decomposes over $\bC$ without repeated factors.

Figures

Figures reproduced from arXiv: 2506.02982 by the authors.

**Figure 2.** (1-Left) Stokes phenomenon on the truncated series of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** The asymptotic simplifications (see Lemma 2) [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Integration contour for the Duchon walk P(u) = u 2 + 1 u 3 with period 5. 4.3 Preliminary Cauchy contour for the periodic case In the periodic case, the preliminary Cauchy contour is star-shape and later deformed by the usual method of singularity analysis to p dominan…

**Figure 5.** Figure 5: Maple worksheet 40 [PITH_FULL_IMAGE:figures/full_fig_p040_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Basic analytic combinatorics of directed lattice paths

Banderier, C., and Flajolet, P. Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science 281, Issue 1-2(2002), 37–80. (Special volume dedicated to M. Nivat). 38

work page 2002
[2]

Random maps, coalescing saddles, singularity analysis, and Airy phenomena.Random Struct

Banderier, C., Flajolet, P., Schaeffer, G., and Soria, M. Random maps, coalescing saddles, singularity analysis, and Airy phenomena.Random Struct. Algo- rithms 19, 3-4 (2001), 194–246

work page 2001
[3]

Boundeddiscretewalks

Banderier, C., and Nicodème, P. Boundeddiscretewalks. Discrete Mathematics and Computer Science(2010), 35–48. Proceedings of AofA2010, 21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Vienna, June 28-July 2

work page 2010
[4]

Algorithmes Efficaces en Calcul Formel

Bostan, A., Chyzak, F., Giusti, M., Lebreton, R., Lecerf, G., Sal vy, B., and Schost, E. Algorithmes Efficaces en Calcul Formel. Frédéric Chyzak (auto- édit.), Palaiseau, Sept. 2017. 686 pages. Imprimé par CreateSpace. Aussi disponible en version électronique

work page 2017
[5]

A new approach to strong embeddings.Probab

Chatterjee, S. A new approach to strong embeddings.Probab. Theory and Related Fields, 152 (2012), 231–24

work page 2012
[6]

An Introduction to Probability Theory and Its Applications, third ed., vol

Feller, W. An Introduction to Probability Theory and Its Applications, third ed., vol. 1. John Wiley and Sons, 1950

work page 1950
[7]

Analytic combinatorics

Flajolet, P., and Sedgewick, R. Analytic combinatorics. Cambridge University Press, 2009. 810 pages

work page 2009
[8]

H., and Knuth, D

Greene, D. H., and Knuth, D. E. Mathematics for the Analysis of Algorithms. Birkhäuser, 1981

work page 1981

Show all 13 references

[9]

An approximation of partial sums of independant RV’s and the sample DF

Komlós, J., Major, P., and Tusnády, G. An approximation of partial sums of independant RV’s and the sample DF. II.Wahrscheinlichkeittheorie und Verw. Gebiete, 32 (1976), 111–131

1976
[10]

Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable.ACM Transactions on Mathe- matical Software, 2 (1994), 163–177

Sal vy, B., and Zimmermann, P. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable.ACM Transactions on Mathe- matical Software, 2 (1994), 163–177

1994
[11]

Stanley, R. P. Differentiably Finite Power Series.European Journal of Combina- torics, 1 (1980), 175–188

1980
[12]

Average Case Analysis of Algorithms on Sequences

Szpankowski, W. Average Case Analysis of Algorithms on Sequences. Series in Discrete Mathematics and Optimization. Wiley-Interscience, 2001. 453 pages

2001
[13]

https://lipn.univ-paris13.fr/~nicodeme/Publications/heightofbridge.mpl

W allner, M. Domination of kernel-roots does not hold within a disk centered at the origin. Personal communication, 2016. 39 > > (2)(2) (1)(1) > > (4)(4) > > > > > > > > > > > > (3)(3) restart: with(gfun): readlib(equivalent):Outputs of heightofbridge.mpl: - Output[1]=formula ...

2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Basic analytic combinatorics of directed lattice paths

Banderier, C., and Flajolet, P. Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science 281, Issue 1-2(2002), 37–80. (Special volume dedicated to M. Nivat). 38

work page 2002

[2] [2]

Random maps, coalescing saddles, singularity analysis, and Airy phenomena.Random Struct

Banderier, C., Flajolet, P., Schaeffer, G., and Soria, M. Random maps, coalescing saddles, singularity analysis, and Airy phenomena.Random Struct. Algo- rithms 19, 3-4 (2001), 194–246

work page 2001

[3] [3]

Boundeddiscretewalks

Banderier, C., and Nicodème, P. Boundeddiscretewalks. Discrete Mathematics and Computer Science(2010), 35–48. Proceedings of AofA2010, 21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Vienna, June 28-July 2

work page 2010

[4] [4]

Algorithmes Efficaces en Calcul Formel

Bostan, A., Chyzak, F., Giusti, M., Lebreton, R., Lecerf, G., Sal vy, B., and Schost, E. Algorithmes Efficaces en Calcul Formel. Frédéric Chyzak (auto- édit.), Palaiseau, Sept. 2017. 686 pages. Imprimé par CreateSpace. Aussi disponible en version électronique

work page 2017

[5] [5]

A new approach to strong embeddings.Probab

Chatterjee, S. A new approach to strong embeddings.Probab. Theory and Related Fields, 152 (2012), 231–24

work page 2012

[6] [6]

An Introduction to Probability Theory and Its Applications, third ed., vol

Feller, W. An Introduction to Probability Theory and Its Applications, third ed., vol. 1. John Wiley and Sons, 1950

work page 1950

[7] [7]

Analytic combinatorics

Flajolet, P., and Sedgewick, R. Analytic combinatorics. Cambridge University Press, 2009. 810 pages

work page 2009

[8] [8]

H., and Knuth, D

Greene, D. H., and Knuth, D. E. Mathematics for the Analysis of Algorithms. Birkhäuser, 1981

work page 1981