5 ms·

I might be ignorant here, but wouldn't it suffice to prove that digits of Pi are random? Just check whether the distribution is uniform, the same way you would

by mamon 8y ago

I might be ignorant here, but wouldn't it suffice to prove that digits of Pi are random? Just check whether the distribution is uniform, the same way you would validate pseudorandom sequence generator for a programming language. Once you proved that Pi digits are random the normality hypotesis becomes trivial: as number of known Pi digits approaches infinity the probablity of any finite sequence to appear approaches 1.

amelius 8y ago
That's sort of the whole point of normal numbers, and pi is not known to belong to this class. https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Normal_number Quoting: > It is widely believed that the (computable) numbers √2, π, and e are normal, but a proof remains elusive.
mikeash 8y ago
You can’t just check all the digits. There are an infinite number of them and you don’t know if they stop looking random at some point after you stop checking.
arayh 8y ago
Here's a brief look into the distribution of the digits of pi if you're interested: https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.html https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.ht... Summary: It's "seems" quite random, but has yet to proven as such.
pitaj 8y ago
The distribution wouldn't even need to be uniform, right? As long as one or more digits never stopped appearing at any point, the infinite sequence would include every possible sequence of numerals.
- v_lisivka 8y ago
  I'm 100% sure that Pi doesn't include e.g. 0.(3) sequence, or e sequence, or many many other sequences, or even just million of zeroes in the row.
  - billforsternz 8y ago
    Why would you be sure it doesn't include a million zeroes in a row? If the digits are random, as appears likely, it definitely will include a million zeroes in a row. The problem is even if you could turn every atom in the universe into a supercomputer, and somehow get them all cooperatively working on calculating the digits, you'd still never get to the million zeroes sequence in a million universe lifetimes. But they're still out there somewhere.
    - v_lisivka 8y ago
      Because geometry of a circle will be skewed if Pi will contains millions zeroes in a row. Pi is not a random number even if it digit sequence looks as pseudo-random sequence.
      - zuminator 8y ago
        One would expect a repdigit sequence of length k to appear once in a 10^k normal sequence. So in the 10^1000000 expansion of pi, one should expect a million zeroes to appear in a row once. You can check this to a limited extent here: http://www.angio.net/pi/ http://www.angio.net/pi/. It only goes up to 200 million (2 x 10^8) digits, but sure enough 00000000 happens to appear twice. (Nonetheless, we don't actually know if pi is normal.)
        billforsternz 8y ago
        Thanks for this, very interesting. My earlier intuition is more than confirmed; If you turn every atom in the universe into a supercomputer, get them all working together generating digits of pi, for a million universe life times, you only get 10^80 (atoms in universe approx) * 10^10 (10 billion digits per sec each say) * 10^11 (years in a universe life time roughly) * 10^8 (seconds in a year roughly) * 10^6 (a million universe lifetimes) = 10^115 (ish) digits. In fact that is an incomparably smaller number that 10^1000000 digits, only good for a single run of 115 zeroes in a row. Basically there's an awful lot of room between zero and mathematical infinity, and normal large numbers that we experience or even try to reason about in everyday life don't and can't begin to stretch even a little way towards the ultimate mathematical limits.
- ginnungagap 8y ago
  Normality also includes the distribution of the substrings in the definition, it's not just "every finite string of numbers compares somewhere"
v_lisivka 8y ago
Digits of Pi are not random, instead they are uniformly distributed or "pseudo-random". Not all sequences are uniformly distributed, thus it very unlikely that we will be able to find long pieces of non-uniformly distributed sequences in uniformly distributed sequence.
- saagarjha 8y ago
  I’m sorry, but I don’t think you quite understand what randomness, or pseudorandomness, means. In a truly random sequence, the probability of any given finite sequence appearing in it is 1.
  - v_lisivka 8y ago
    AFAIK, nobody proved that Pi digits sequence is normal. See https://www.quora.com/How-random-are-the-digits-in-pi https://www.quora.com/How-random-are-the-digits-in-pi . So it quite possible for some finite sequences to be omitted from the Pi digits sequence.

by mamon 8y ago

amelius 8y ago

That's sort of the whole point of normal numbers, and pi is not known to belong to this class. https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Normal_number Quoting: > It is widely believed that the (computable) numbers √2, π, and e are normal, but a proof remains elusive.

mikeash 8y ago

You can’t just check all the digits. There are an infinite number of them and you don’t know if they stop looking random at some point after you stop checking.

arayh 8y ago

Here's a brief look into the distribution of the digits of pi if you're interested: https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.html https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.ht... Summary: It's "seems" quite random, but has yet to proven as such.

pitaj 8y ago

The distribution wouldn't even need to be uniform, right? As long as one or more digits never stopped appearing at any point, the infinite sequence would include every possible sequence of numerals.

v_lisivka 8y ago
I'm 100% sure that Pi doesn't include e.g. 0.(3) sequence, or e sequence, or many many other sequences, or even just million of zeroes in the row.
- billforsternz 8y ago
  Why would you be sure it doesn't include a million zeroes in a row? If the digits are random, as appears likely, it definitely will include a million zeroes in a row. The problem is even if you could turn every atom in the universe into a supercomputer, and somehow get them all cooperatively working on calculating the digits, you'd still never get to the million zeroes sequence in a million universe lifetimes. But they're still out there somewhere.
  - v_lisivka 8y ago
    Because geometry of a circle will be skewed if Pi will contains millions zeroes in a row. Pi is not a random number even if it digit sequence looks as pseudo-random sequence.
    - zuminator 8y ago
      One would expect a repdigit sequence of length k to appear once in a 10^k normal sequence. So in the 10^1000000 expansion of pi, one should expect a million zeroes to appear in a row once. You can check this to a limited extent here: http://www.angio.net/pi/ http://www.angio.net/pi/. It only goes up to 200 million (2 x 10^8) digits, but sure enough 00000000 happens to appear twice. (Nonetheless, we don't actually know if pi is normal.)
      - billforsternz 8y ago
        Thanks for this, very interesting. My earlier intuition is more than confirmed; If you turn every atom in the universe into a supercomputer, get them all working together generating digits of pi, for a million universe life times, you only get 10^80 (atoms in universe approx) * 10^10 (10 billion digits per sec each say) * 10^11 (years in a universe life time roughly) * 10^8 (seconds in a year roughly) * 10^6 (a million universe lifetimes) = 10^115 (ish) digits. In fact that is an incomparably smaller number that 10^1000000 digits, only good for a single run of 115 zeroes in a row. Basically there's an awful lot of room between zero and mathematical infinity, and normal large numbers that we experience or even try to reason about in everyday life don't and can't begin to stretch even a little way towards the ultimate mathematical limits.
ginnungagap 8y ago
Normality also includes the distribution of the substrings in the definition, it's not just "every finite string of numbers compares somewhere"

v_lisivka 8y ago

Digits of Pi are not random, instead they are uniformly distributed or "pseudo-random". Not all sequences are uniformly distributed, thus it very unlikely that we will be able to find long pieces of non-uniformly distributed sequences in uniformly distributed sequence.

saagarjha 8y ago
I’m sorry, but I don’t think you quite understand what randomness, or pseudorandomness, means. In a truly random sequence, the probability of any given finite sequence appearing in it is 1.
- v_lisivka 8y ago
  AFAIK, nobody proved that Pi digits sequence is normal. See https://www.quora.com/How-random-are-the-digits-in-pi https://www.quora.com/How-random-are-the-digits-in-pi . So it quite possible for some finite sequences to be omitted from the Pi digits sequence.