Functions that preserve p-randomness

We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time computable real number. These results follow from a general theorem: If I ⊆ R is an open interval, f: I → R is a function, and r ∈ I is p-random, then f ( r ) is p-random provided 1. f is p-computable on the dyadic rational points in I, and 2. f varies sufficiently at r, i. e. , there exists a real constant C > 0 such that either ( ∀ x ∈ I − { r } ) [ f ( x ) − f ( r ) x − r ⩾ C ] or ( ∀ x ∈ I − { r } ) [ f ( x ) − f ( r ) x − r ⩽ − C ]. Our theorem implies in particular that any analytic function about a p-computable point whose power series has uniformly p-computable coefficients preserves p-randomness in its open interval of absolute convergence. Such functions include all the familiar functions from first-year calculus.

Authors

• Stephen A. Fenner

Keywords

• Randomness
• p-Randomness
• Complexity
• Polynomial-time
• Measure
• Martingale