Abstract
We expand our effective framework for weak convergence of measures on the real line by showing that effective convergence in the Prokhorov metric is equivalent to effective weak convergence. In addition, we establish a framework for the study of the effective theory of vague convergence of measures. We introduce a uniform notion and a non-uniform notion of vague convergence, and we show that both these notions are equivalent. However, limits under effective vague convergence may not be computable even when they are finite. We give an example of a finite incomputable effective vague limit measure, and we provide a necessary and sufficient condition so that effective vague convergence produces a computable limit. Finally, we determine a sufficient condition for which effective weak and vague convergence of measures coincide.
Summary
This paper develops the computable analysis perspective on measure convergence, asking when and how the classical equivalences between weak and vague convergence can be effectivised. The setting is M(R), the space of finite Borel measures on R, equipped with computable structure.
The first main result (Theorem 4.1) shows that for uniformly computable sequences of measures, effective weak convergence and effective convergence in the Prokhorov metric are equivalent. This is the effective analogue of the classical fact that the Prokhorov metric metrises weak convergence.
The second main contribution introduces two definitions of effective vague convergence — a non-uniform one (Definition 5.1, using individual indices of compactly supported test functions) and a uniform one (Definition 5.2, using a single procedure for all test functions). These are shown to be equivalent (Theorem 5.3).
A striking negative result (Proposition 5.6) shows that effective vague convergence is fundamentally weaker than its weak counterpart: there exists a uniformly computable sequence that effectively vaguely converges to a finite but incomputable limit measure. This contrasts sharply with effective weak convergence, where limits of computable sequences are always computable.
The condition bridging the gap is a computable modulus of convergence for the total masses (Theorem 5.8): with this extra condition, effective vague convergence implies effective weak convergence (and hence computability of the limit). For probability measures, effective vague and weak convergence coincide unconditionally (Corollary 5.12).
Key Contributions
- Proves effective weak convergence equals effective Prokhorov metric convergence (Theorem 4.1)
- Introduces uniform and non-uniform effective vague convergence, proves their equivalence (Theorem 5.3)
- Constructs an incomputable effective vague limit (Proposition 5.6) — limits under vague convergence need not be computable, even when finite
- Gives necessary and sufficient condition for computable vague limits: mu(R) must be computable (Proposition 5.7)
- Shows effective weak and vague convergence coincide when total masses converge computably (Theorem 5.8)
- Derives effective equivalence of weak and vague convergence for computable probability measures (Corollary 5.12)
Methodology
The paper operates in the framework of computable analysis (Type-2 computability / TTE). Measures are represented via their actions on rational open intervals. A measure is “computable” if mu(U) is left-c.e. uniformly in an index of U. Sequences are “uniformly computable” if each mu_n is computable uniformly in n. The effective Portmanteau theorem (Theorem 3.5, from McNicholl-Rojas) provides multiple equivalent characterisations of effective weak convergence. The proof of Theorem 4.1 adapts the classical Prokhorov-metrises-weak-convergence argument, using Lemma 4.2 to compute covers by mu-almost decidable balls. For Theorem 5.3, approximation by rational polygonal functions (Lemma 5.4) translates between compact-support and name-based definitions.
Key Findings
- The Prokhorov metric is the correct effective metrisation of weak convergence on M(R)
- Effective vague convergence is strictly weaker than effective weak convergence in general
- The “vagueness” of effective vague convergence manifests as potential incomputability of limits — a phenomenon without classical analogue
- The total mass of the limit is the key: if mu(R) is computable, the limit is computable; if not, the limit can be incomputable despite being finite
- For probability measures, effective weak and vague convergence coincide — recovering the classical result in the computable setting
Important References
- Effective notions of weak convergence of measures on the real line — McNicholl and Rojas’s prior work establishing the effective weak convergence framework
- Computability of probability measures and Martin-Lof randomness over metric spaces — Hoyrup and Rojas’s treatment of M(X) as a computable metric space
- Convergence of random processes and limit theorems in probability theory — Prokhorov’s classical work on the Prokhorov metric