2
$\begingroup$

Are there irrational numbers whose digits are considered pseudo-random?

Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a rational sequence whereas as irrational numbers are not periodic.

This follows from the question if a pseudo-random number generator is necessarily periodic. It can be expressed as a Turing machine which itself cannot compute reals other than by recursively enumerating them. If effectively, there exists such an irrational number, then there are pseudo-random number generators, in theory, that are non-periodic.

$\endgroup$
  • $\begingroup$ I think this question is difficult to state because you need precise definitions of pseudorandom and pseudorandom generator. According to standard theoretical definitions, I think, PRGs are not periodic, but they halt after a certain fixed amount of output. $\endgroup$ – usul May 11 '14 at 20:57
  • 3
    $\begingroup$ PRGs need not be periodic. See, for example, the Blum-Micali definition. From such a non-periodic PRG there are several ways one might construct an infinite string and consider that as the binary expansion of a real number. Surely most of these ways will lead to irrational numbers... $\endgroup$ – Joshua Grochow May 12 '14 at 14:43
  • $\begingroup$ Indeed, all of these ways will lead to irrational numbers, as long as they aren't periodic. $\endgroup$ – mjqxxxx May 21 '14 at 4:21
8
$\begingroup$

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior.

Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (with non-trivial probability) from a uniformly random sequence sampled from $\{0, \ldots, B\}^n$ by any algorithm $A$ in a class of algorithms $\cal A$. Usually in cryptography, $\cal A$ is the class of polynomial-time algorithms or polynomial-size circuits. Then it is easy to see that any sequence that can be generated in polynomial time by a deterministic algorithm is not pseudorandom: the distinguisher just simulates the generator. For this reason, pseudorandom generators in cryptography are randomized, and we speak of a pseudorandom distribution rather than a fixed pseudorandom sequence.

However, there are weaker notions of pseudorandomness (corresponding to more restricted classes $\cal A$ of distinguishers) that the expansion of an irrational number in an integer basis might satisfy. For example, $\sqrt{2}$, $e$, and $\pi$ are conjectured to be normal, which is a kind of pseudorandomness: each pattern of $k$ digits in base $B$ appears with frequency $1/B^k$, in the limit. This is like pseudorandomness with respect to distinguishers which can only ask "approximately how often does this pattern appear in the expansion of $\sqrt{2}$?" However, at the moment we are unable to prove normality for any of the above fundamental constants, in any base, even though it is conjectured they are absolutely normal, i.e. normal in every base. This is a famous open problem.

Something that we understand better is sequences like $(k\sqrt{2} \bmod 1)_{k = 1}^\infty$ ($x \bmod 1$ just means the fractional part of $x$). By Weyl's ergodicity criterion, we know that for any Lebesgue integrable function $f$, the average $$ \overline{f}_n = \frac{1}{n-1}\sum_{k = 0}^{n-1}{f(k\sqrt{2} \bmod 1)}, $$ converges to the expectation $\mathbb{E}[f(x)]$, where $x$ is a uniformly sampled random number from $[0, 1]$. We also have deviation estimates: for $f$ the indicator function of an interval $I = [a, b]$, $a, b \in [0,1]$, the average $\overline{f}_n$ deviates from the expectation $b-a$ by $O((\log n)/n)$ in the worst case, and by $O(\sqrt{\log n}/n)$ on most intervals $[a, b]$ ("most" is measured by the natural product measure). Moreover, Beck has recently shown a central limit theorem, which quantifies the statement that numbers $n$ for which the deviation is large are very rare. For an intro to the pseudorandomness properties of these sequences, check section 2.3. of Chazelle's discrepancy book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.