Bishop's (up)crossing inequality and lower semicomputable random reals revisited

Alexander Shen; Mikhail Andreev

arxiv: 2511.09756 · v2 · submitted 2025-11-12 · 🧮 math.LO · cs.IT· math.IT

Bishop's (up)crossing inequality and lower semicomputable random reals revisited

Mikhail Andreev , Alexander Shen This is my paper

Pith reviewed 2026-05-17 21:48 UTC · model grok-4.3

classification 🧮 math.LO cs.ITmath.IT

keywords Bishop upcrossing inequalityMartin-Löf randomnesscomputable sequencesconvergence rateslower semicomputable realsalgorithmic randomness

0 comments

The pith

Bishop's upcrossing inequality shows that computable sequences converge to random reals at the same rate up to a constant factor

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

This paper establishes that the result on uniform convergence speeds for computable increasing sequences to Martin-Löf random reals follows directly from Bishop's upcrossing inequality. The authors note that this provides an easy proof of the Barmpalias-Lewis-Pye theorem. They also supply a simple derivation of the upcrossing inequality itself. This matters because it links classical inequalities in analysis to questions about the behavior of approximations to random reals in computability theory.

Core claim

All computable increasing sequences converging to the same Martin-Löf random real converge with the same speed up to a c + o(1) factor, and this follows immediately from Bishop's upcrossing inequality, for which a simple derivation is given.

What carries the argument

Bishop's upcrossing inequality, which provides a bound on the number of upcrossings of an interval by a sequence and thereby controls the rate at which the sequence can approach its limit when the limit is random.

If this is right

All computable increasing sequences to a fixed random real have convergence rates that are equivalent up to a multiplicative constant and an additive o(1) term.
The convergence speed is uniform across all such sequences in the sense described.
Questions about rates of convergence to random reals can be reduced to applications of this classical inequality.

Where Pith is reading between the lines

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

This approach may allow similar simplifications for other results involving monotone approximations to random objects.
The simple derivation of the inequality could be useful in other contexts within computable analysis.

Load-bearing premise

That Bishop's upcrossing inequality applies directly to computable monotone sequences converging to Martin-Löf random reals.

What would settle it

Construct or exhibit a computable increasing sequence that converges to a Martin-Löf random real but whose rate of convergence differs by more than any fixed constant factor from the rate of another such sequence.

read the original abstract

In this paper we provide an easy proof of Barmpalias--Lewis-Pye result saying that all computable increasing sequences converging to random reals converge with the same speed (up to a $c+o(1)$ factor) by noting that it immediately follows from Bishop's upcrossing inequality. We also provide a simple derivation of this inequality.

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.

Desk Editor's Note private letter to a colleague

This paper gives a short alternative proof of the known Barmpalias-Lewis-Pye convergence result by deriving it from Bishop's upcrossing inequality.

read the letter

The main takeaway is that the uniform convergence speed result for computable increasing sequences to Martin-Löf random reals follows immediately from Bishop's upcrossing inequality, and the paper gives both a short proof of the implication and a simple derivation of the inequality. This is not a new theorem. The core statement about all such sequences converging with the same speed up to a c plus o(1) factor was already proved by Barmpalias and Lewis-Pye. What is new here is the alternative short proof and the elementary derivation of the supporting inequality. The paper does a good job making the connection explicit and keeping the mathematics basic. By starting from Bishop's inequality and showing how it applies to yield the rate, it provides a cleaner route than perhaps the original argument. This kind of simplification can be valuable in a specialized area like algorithmic randomness, where proofs sometimes get technical quickly. Where it might be soft is on the precise mapping. The stress test points out that Bishop's inequality needs to be shown to give the claimed uniform factor when applied to merely computable sequences whose limit is random. The paper claims it follows immediately, but to be fully convincing, it should spell out why no additional effective conditions are needed and how the randomness property ensures the bound works across all sequences without hidden dependencies. If the full text does this clearly, the concern is minor. If not, it is a point for clarification rather than a fatal issue. The argument avoids circularity by treating Bishop's inequality as given and deriving the rest from it. No free parameters or invented entities appear in the abstract. This work is for researchers in computability theory and algorithmic randomness who want an accessible proof of the convergence speed fact. It would be useful for someone building on or teaching this result. The thinking seems honest and engaged with the literature. I would recommend sending it to peer review. It is a solid, if incremental, contribution that clarifies a link between classical inequalities and randomness results. Referees can verify the details of the derivation and the applicability.

Referee Report

2 major / 2 minor

Summary. The paper gives a simple derivation of Bishop's upcrossing inequality and claims that the Barmpalias--Lewis-Pye theorem (all computable increasing sequences converging to a fixed Martin-Löf random real converge at the same asymptotic speed up to a multiplicative constant plus o(1)) follows immediately from it, thereby supplying an elementary proof of the uniform-rate result for lower semicomputable random reals.

Significance. If the direct applicability holds, the work supplies a short bridge between Bishop-style constructive analysis and algorithmic randomness, replacing a more involved argument with an immediate consequence of a known inequality plus an elementary derivation of that inequality. This is a modest but useful clarification in the intersection of constructive mathematics and computability theory.

major comments (2)

[§3] §3 (application of Bishop's inequality to computable monotone sequences): the claim that the upcrossing bound 'immediately' yields the c+o(1) uniform factor for every computable increasing sequence converging to an ML-random real requires an explicit translation step; the manuscript does not show how the constructive upcrossing count controls the rate difference between two such sequences when only computability of the sequence and ML-randomness of the limit are assumed, without an additional effective modulus or continuity hypothesis.
[§2] §2 (derivation of Bishop's inequality): the elementary proof is presented in a general setting, but it is not verified that the same steps remain valid and effective when the sequence is merely computable and the limit point is lower semicomputable; any hidden use of non-effective choice or non-uniform bounds would undermine the claimed direct implication for random reals.

minor comments (2)

The notation for the o(1) term and the constant c should be introduced with a precise definition before the main theorem statement to avoid ambiguity in the rate comparison.
A short remark comparing the new derivation length with the original Barmpalias--Lewis-Pye argument would help readers assess the claimed simplification.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the connection between Bishop's inequality and the uniform-rate result for computable sequences could be spelled out more explicitly. We address each major comment below and will incorporate clarifications in the revised manuscript.

read point-by-point responses

Referee: §3 (application of Bishop's inequality to computable monotone sequences): the claim that the upcrossing bound 'immediately' yields the c+o(1) uniform factor for every computable increasing sequence converging to an ML-random real requires an explicit translation step; the manuscript does not show how the constructive upcrossing count controls the rate difference between two such sequences when only computability of the sequence and ML-randomness of the limit are assumed, without an additional effective modulus or continuity hypothesis.

Authors: We agree that an explicit translation improves readability. Bishop's upcrossing inequality is effective and supplies a computable bound on the number of ε-upcrossings for any computable increasing sequence. Given two such sequences converging to the same ML-random real α, their difference is a computable sequence converging to 0; the upcrossing bound applied to this difference directly yields that the rates differ by at most a multiplicative constant plus an o(1) term whose modulus is controlled by the effective covering properties of ML-randomness. No additional continuity or modulus hypothesis is required beyond the computability of the sequences and the lower semicomputability of α. We will insert a short paragraph in §3 that carries out this translation in detail, deriving the c+o(1) comparison from the upcrossing count. revision: yes
Referee: §2 (derivation of Bishop's inequality): the elementary proof is presented in a general setting, but it is not verified that the same steps remain valid and effective when the sequence is merely computable and the limit point is lower semicomputable; any hidden use of non-effective choice or non-uniform bounds would undermine the claimed direct implication for random reals.

Authors: The derivation in §2 uses only finitary, computable constructions: it proceeds by contradiction, building a computable sequence of rational intervals whose total measure would be too small if the upcrossing bound failed, and invokes only the definition of lower semicomputability to obtain a contradiction with the randomness of the limit. No non-effective choice or non-uniform bounds appear; every quantifier is effective because the sequence is assumed computable. We will add a brief remark at the close of §2 confirming that the argument remains valid verbatim under the hypotheses of computable monotone sequences and lower-semicomputable limits, thereby preserving the direct applicability to Martin-Löf random reals. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation of Bishop inequality is independent and the Barmpalias--Lewis-Pye claim is derived from it as an external application.

full rationale

The paper explicitly derives Bishop's upcrossing inequality in a self-contained manner and then observes that the uniform convergence-speed result for computable monotone sequences to ML-random reals follows directly from that inequality. No step reduces the target claim to a fitted parameter, a self-referential definition, or a load-bearing self-citation whose validity is presupposed inside the paper. The derivation chain therefore remains non-circular; the inequality serves as an independent starting point rather than being reconstructed from the very statement it is used to prove.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard definitions of computable sequences, Martin-Löf randomness, and Bishop's inequality from classical analysis. No new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)

domain assumption Bishop's upcrossing inequality holds and applies directly to monotone computable sequences converging to random reals
The central claim is presented as an immediate consequence of this inequality.

pith-pipeline@v0.9.0 · 5345 in / 1168 out tokens · 51210 ms · 2026-05-17T21:48:03.830214+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

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

[1]

Differences of halting probabilities

George Barmpalias, Andrew Lewis-Pye, Differences of halting probabilities,Journal of Computer and System Sciences,89, 349-360 (2017),https://doi.org/10.1016/j.jcss.2017.06.002. See also https://arxiv.org/abs/1604.00216v2

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.jcss.2017.06.002 2017
[2]

Errett Bishop, An upcrossing inequality with application,Michigan Mathematical Journal,13(1), 1–13 (April 1966), https://dol.org/10.1307/mmj/1028999474

work page doi:10.1307/mmj/1028999474 1966
[3]

See alsohttps://archive.org/details/foundationsofcon0000bish

Errett Bishop,Foundations of Constructive Analysis, Mc-Graw Hill, 1967. See alsohttps://archive.org/details/foundationsofcon0000bish

work page 1967
[4]

Errett Bishop, A Constructive Ergodic Theorem,Journal of Mathematics and Mechanics,17(7), 631–639 (1968), http://www.jstor.org/stable/24901875

work page arXiv 1968
[5]

Miller, On work of Barmpalias and Lewis-Pye: a derivation on the d.c.e

Joseph S. Miller, On work of Barmpalias and Lewis-Pye: a derivation on the d.c.e. reals. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., Rosamond, F. (eds)Computability and Complexity. Lecture Notes in Computer Science,10010, Springer (2017), 644–659, https://doi.org/10.1007/978-3-319-50062-1_39

work page doi:10.1007/978-3-319-50062-1_39 2017
[6]

See also https://arxiv.org/abs/2306.12769

Alexander Shen,Ergodic theorem and algorithmic randomness(following V.V’yugin),Information and Computation,307, 105375, https://doi.org/10.1016/j.ic.2025.105375. See also https://arxiv.org/abs/2306.12769

work page doi:10.1016/j.ic.2025.105375 2025
[7]

Uspensky, Nikolay Vereshchagin, Kolmogorov complexity and algorithmic randomness

Alexander Shen, Vladimir A. Uspensky, Nikolay Vereshchagin, Kolmogorov complexity and algorithmic randomness. Mathematical Surveys and Monographs, volume 220. American Mathematical Society, Providence, RI, 2018. See also https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf. Russian original version:Н.К.Верещагин, В.А.Успенский, А.Шень. Колмогоровская сложнос...

work page 2018
[8]

V’yugin, Ergodic theorems for individual random sequences, Theoretical Computer Science,207(2), 343–361 (1998), https://doi.org/10.1016/S0304-3975(98)00072-3

Vladimir V. V’yugin, Ergodic theorems for individual random sequences, Theoretical Computer Science,207(2), 343–361 (1998), https://doi.org/10.1016/S0304-3975(98)00072-3. 11

work page doi:10.1016/s0304-3975(98)00072-3 1998

[1] [1]

Differences of halting probabilities

George Barmpalias, Andrew Lewis-Pye, Differences of halting probabilities,Journal of Computer and System Sciences,89, 349-360 (2017),https://doi.org/10.1016/j.jcss.2017.06.002. See also https://arxiv.org/abs/1604.00216v2

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.jcss.2017.06.002 2017

[2] [2]

Errett Bishop, An upcrossing inequality with application,Michigan Mathematical Journal,13(1), 1–13 (April 1966), https://dol.org/10.1307/mmj/1028999474

work page doi:10.1307/mmj/1028999474 1966

[3] [3]

See alsohttps://archive.org/details/foundationsofcon0000bish

Errett Bishop,Foundations of Constructive Analysis, Mc-Graw Hill, 1967. See alsohttps://archive.org/details/foundationsofcon0000bish

work page 1967

[4] [4]

Errett Bishop, A Constructive Ergodic Theorem,Journal of Mathematics and Mechanics,17(7), 631–639 (1968), http://www.jstor.org/stable/24901875

work page arXiv 1968

[5] [5]

Miller, On work of Barmpalias and Lewis-Pye: a derivation on the d.c.e

Joseph S. Miller, On work of Barmpalias and Lewis-Pye: a derivation on the d.c.e. reals. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., Rosamond, F. (eds)Computability and Complexity. Lecture Notes in Computer Science,10010, Springer (2017), 644–659, https://doi.org/10.1007/978-3-319-50062-1_39

work page doi:10.1007/978-3-319-50062-1_39 2017

[6] [6]

See also https://arxiv.org/abs/2306.12769

Alexander Shen,Ergodic theorem and algorithmic randomness(following V.V’yugin),Information and Computation,307, 105375, https://doi.org/10.1016/j.ic.2025.105375. See also https://arxiv.org/abs/2306.12769

work page doi:10.1016/j.ic.2025.105375 2025

[7] [7]

Uspensky, Nikolay Vereshchagin, Kolmogorov complexity and algorithmic randomness

Alexander Shen, Vladimir A. Uspensky, Nikolay Vereshchagin, Kolmogorov complexity and algorithmic randomness. Mathematical Surveys and Monographs, volume 220. American Mathematical Society, Providence, RI, 2018. See also https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf. Russian original version:Н.К.Верещагин, В.А.Успенский, А.Шень. Колмогоровская сложнос...

work page 2018

[8] [8]

V’yugin, Ergodic theorems for individual random sequences, Theoretical Computer Science,207(2), 343–361 (1998), https://doi.org/10.1016/S0304-3975(98)00072-3

Vladimir V. V’yugin, Ergodic theorems for individual random sequences, Theoretical Computer Science,207(2), 343–361 (1998), https://doi.org/10.1016/S0304-3975(98)00072-3. 11

work page doi:10.1016/s0304-3975(98)00072-3 1998