Computable randomness and betting for computable probability spaces

Unlike Martin‐Löf randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting “bit‐wise” definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness—endomorphism randomness—which the author hopes will shed light on the open question of whether Kolmogorov‐Loveland randomness is equivalent to Martin‐Löf randomness. The last section contains ideas for future research.     

Martin–Löf random generalized Poisson processes

Martin–Löf randomness was originally defined and studied in the context of the Cantor space $2^{\omega }$. In [2] probability theoretic random closed sets (RACS) are used as the foundation for the study of Martin–Löf randomness in spaces of closed sets. We use that framework to explore Martin–Löf randomness for the space of closed subsets of $\mathbb{R}$ and a particular family of measures on this space, the generalized Poisson processes. This gives a novel class of Martin–Löf random closed subsets of $\mathbb{R}$. We describe some of the properties of these Martin–Löf random closed sets; one result establishes that a real number is Martin–Löf random if and only if it is contained in some Martin–Löf random closed set.     

Defining a randomness notion via another

To compare two randomness notions with each other, we ask whether a given randomness notion can be defined via another randomness notion. Inspired by Yu's pioneering study, we formalize our question using the concept of relativization of randomness. We give some solutions to our formalized questions. Also, our results include the affirmative answer to the problem asked by Yu in a discussion with the second author, i.e., whether Schnorr randomness relative to the halting problem is equivalent to Martin‐Löf randomness relative to all low 1‐generic reals.     

How much randomness is needed for statistics?

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle (which we call the “classical approach”). The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ (we call this approach “Hippocratic”). While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity.     

Constructive equivalence relations on computable probability measures

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences.In what follows, we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general.     

Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

When series of computable functions with varying domains are computable

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point‐free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well‐defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than ε for any , in an earlier paper.)     

Truth‐table Schnorr randomness and truth‐table reducible randomness

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth‐table Schnorr randomness (defined in 6 too only by martingales) and truth‐table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth‐table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth‐table Schnorr randomness. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Martin Kernels for Markov Processes with Jumps

We prove the existence of boundary limits of ratios of positive harmonic functions for a wide class of Markov processes with jumps and irregular (possibly disconnected) domains of harmonicity, in the context of general metric measure spaces. As a corollary, we prove the uniqueness of the Martin kernel at each boundary point, that is, we identify the Martin boundary with the topological boundary. We also prove a Martin representation theorem for harmonic functions. Examples covered by our results include: strictly stable Lévy processes in R ^d with positive continuous density of the Lévy measure; stable-like processes in R ^d and in domains; and stable-like subordinate diffusions in metric measure spaces.     

图灵机计算实数函数的稳定性

定义在全体实数上的可计算函数是一个很重要的概念．在这以前定义可计算的实数函数有两个途径．第一个途径是首先要定义可计算实数的指标．想要确定实数函数y=f（x）是不是可以计算就要看是否存在一个自然数的（部分）递归函数将可计算实数x的指标对应到可计算实数y的指标．这样一来对实数函数的研究依赖于对自然数函数的研究．第二个定义可计算的实数函数的途径是以逼近为基础的．一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的．用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数．例如“〈”和“=”的命题函数就是不可以计算的因为它们是不连续的命题函数．本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义．我们的定义不需要用到自然数的（部分）递归函数．根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的．用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多．     

Computability of the ergodic decomposition

The study of ergodic theorems from the viewpoint of computable analysis is a rich field of investigation. Interactions between algorithmic randomness, computability theory and ergodic theory have recently been examined by several authors. It has been observed that ergodic measures have better computability properties than non-ergodic ones. In a previous paper we studied the extent to which non-ergodic measures inherit the computability properties of ergodic ones, and introduced the notion of an effectively decomposable measure. We asked the following question: if the ergodic decomposition of a stationary measure is finite, is this decomposition effective? In this paper we answer the question in the negative.     

Transition probabilities of Lévy‐type processes: Parametrix construction

We present an existence result for Lévy‐type processes which requires only weak regularity assumptions on the symbol with respect to the space variable x. Applications range from existence and uniqueness results for Lévy‐driven SDEs with Hölder continuous coefficients to existence results for stable‐like processes and Lévy‐type processes with symbols of variable order. Moreover, we obtain heat kernel estimates for a class of Lévy and Lévy‐type processes. The paper includes an extensive list of Lévy(‐type) processes satisfying the assumptions of our results.     

Remarks on discretely absolutely star-Lindelöf spaces

In this paper, we prove the following statements(1) There exists a Hausdorff Lindelöf space X such that the Alexandroff duplicate A(X) of X is not discretely absolutely star-Lindelöf.(2) If X is a regular Lindelöf space, then A(X) is discretely absolutely star-Lindelöf.(3) If X is a normal discretely star-Lindelöf space with e(X) < ω ₁, then A(X) is discretely absolutely star-Lindelöf.     

Mappings and some decompositions of continuity on nearly Lindelöf spaces

A topological space (X, π) is said to be nearly Lindelöf if every regularly open cover of (X, π) has a countable subcover. In this paper we study the effect of mappings and some decompositions of continuity on nearly Lindelöf spaces. The main result is that a δ-continuous image of a nearly Lindelöf space is nearly Lindelöf.     

Exploring hypergraphs with martingales

Recently, in [Random Struct Algorithm 41 (2012), 441–450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 (2007), 133–142], in turn based on ideas of Martin‐Löf [J Appl Probab 23 (1986), 265–282], Karp [Random Struct Alg 1 (1990), 73–93] and Aldous [Ann Probab 25 (1997), 812–854], to prove asymptotic normality of the number L₁ of vertices in the largest component of the random r‐uniform hypergraph in the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of L₁, and joint asymptotic normality of L₁ and the number M₁ of edges of in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 (2016), 21–75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325–352, 2017     

On Frobenius normwise condition numbers for Moore–Penrose inverse and linear least‐squares problems

Condition numbers play an important role in numerical analysis. Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using norms. In this paper, we give explicit, computable expressions depending on the data, for the normwise condition numbers for the computation of the Moore–Penrose inverse as well as for the solutions of linear least‐squares problems with full‐column rank. Copyright © 2007 John Wiley & Sons, Ltd.     

Fuzzy probability measures

In [4] Höhle has defined fuzzy measures on G-fuzzy sets [2] where G stands for a regular Boolean algebra. Consequently, since the unit interval is not complemented, fuzzy sets in the sense of Zadeh [8] do not fit in this framework in a straightforward manner. It is the purpose of this paper to continue the work started in [5] which deals with [0,1]-fuzzy sets and to give a natural definition of a fuzzy probability measure on a fuzzy measurable space [5]. We give necessary and sufficient conditions for such a measure to be a classical integral as in [9] in the case the space is generated. A counterexample in the general case is also presented. Finally it is shown that a fuzzy probability measure is always an integral (if the space is generated) if we replace the operations ∧ and ∨ by the t-norm T_o and its dual S₀ (see [6]).     

锥中与稳态的薛定谔算子相关的广义Martin函数无穷远处的控制

本文研究了稳态的薛定谔算子的Dirichlet问题和Martin函数的边界行为.利用广义Martin表示和稳态的薛定谔算子对应的常微分方程基本解,在具有光滑边界的锥形区域中获得了与稳态的薛定谔算子相关的广义Martin函数无穷远处广义调和控制的一些刻画,推广了拉普拉斯算子情形的结果.     

Potential kernels,probabilities of hitting a ball,harmonic functions and the boundary Harnack inequality for unimodal Lévy processes

In the first part of this article, we prove two-sided estimates of hitting probabilities of balls, the potential kernel and the Green function for a ball for general isotropic unimodal Lévy processes. We also prove a supremum estimate and a regularity result for functions harmonic with respect to a general isotropic unimodal Lévy process.In the second part we apply the recent results on the boundary Harnack inequality and Martin representation of harmonic functions for the class of isotropic unimodal Lévy processes. As a sample application, we provide sharp two-sided estimates of the Green function of a half-space.     

Diffusion on locally compact ultrametric spaces

We consider an ultrametric space with sufficiently many isometries and we construct a class of diffusion processes on the space as appropriate limits of discrete processes on the (open and closed) balls of the space. We show, using a version of the Lévy Khintchine formula adapted to this general context, that our construction includes all convolution semigroups associated to an unbounded Lévy measure. Finally we relate our construction to the construction of diffusion processes due to S. Albeverio and W. Karwowski on p-adic fields.