8
$\begingroup$

This is similar to a random walk using $\pi$ as the input.

Consider taking steps on an infinite grid based on the digits of $\pi$ (though we could use any number). If we express the number in base $8$, then each digit $0$ to $7$ represents a step to one of the $8$ neighbors including diagonals (base 4 would be an alternative with up/down left/right). One possible mapping of these steps could be from the current position (or pixel) $P$ to one of these neighbors as $$ \begin{array} \\ \hline 0 & 1 & 2 \\ 7 & P & 3 \\ 6 & 5 & 4 \\ \hline \end{array} $$ Considering $\pi$ in base 8 we have $$ \pi_8 = 3.1103755 \dots $$ so the first step would be one cell to the right (3). The second and third steps both move one cell up (1). The fourth step moves up and to the left, $etc$.

The first 1022 steps (starting at green position ending at black) looks like this:

enter image description here

While discussing this game a friend of mine claimed that as we continued steps toward infinity, $\pi$ would fill the plane. Clearly a bold claim, and I am suspicious. Is it provable? If it doesn't work in base $8$, could it work in the base $4$ case where we move up/down or left right?

$\endgroup$
  • 3
    $\begingroup$ If $\pi$ is normal to base $8$, your friend is right. But this is an open statement. Do you mind continue and show the results ? I guess the movement of the point is chaotic. $\endgroup$ – Peter Aug 26 '16 at 20:45
  • $\begingroup$ "Fill the plane" meaning what? A surjective map to all points in the integer lattice (or similarly defined set using "cells")? $\endgroup$ – mathguy Aug 26 '16 at 20:45
  • $\begingroup$ I doubt it's provable as too little is known about the digits of $\pi$. It is possible, though really I doubt anyone believes it, that there are eventually there are much more $0,1,2$ in the digits than the other digits and you'd have a significant upwards bias. $\endgroup$ – quid Aug 26 '16 at 20:46
  • 1
    $\begingroup$ Little is known about the behaviour of the expansion of $\pi$ after, say, Graham's number of decimal places. From that point on, as far as know, what you describe is for all intents and purposes indistinguishable from a true random walk. $\endgroup$ – Arthur Aug 26 '16 at 20:46
  • 1
    $\begingroup$ @Peter there are normal numbers that don't fill the plane $\endgroup$ – mercio Aug 26 '16 at 21:48
9
$\begingroup$

I suspect your friend is thinking as follows: the digits of $\pi$ are "basically random," so the walk generated by $\pi$ should go "all over the place." There are two pieces to this to consider:

  • How random is $\pi$?

and

  • How do random walks behave?

Let me begin with the second question, because it's easier to answer. We forget about the digits of $\pi$, and instead imagine we have some fair die that we're rolling, with an appropriate number of sides, and using this to generate a random walk. What happens?

Let's ignore base $8$ for the moment; the bases $4$ and $2$ are easier to visualize. In base $2$, we move left/right in a line; in base $4$, we move up/down/left/right in the plane. In either case, we're moving in a particularly nice lattice. Similarly, the base $6$ version is a cubical lattice (up/down/left/right/forward/back), and so on. In general, the base $2n$ version is a walk in the $n$-dimensional cubical lattice.

So fix $n$, and roll a $2n$-sided die repeatedly. What's the probability that we "fill the space?"

Surprisingly, the dimension matters! Specifically, if $n=1$ or $n=2$ the answer is $1$ (we almost certainly fill the space), whereas if $n\ge 3$ the answer is $0$ (we almost certainly don't fill the space). See Polya's recurrence theorem.

So if we believe $\pi$ "behaves randomly" (whatever that means, for the moment), then we should believe that the base-4 version of $\pi$ fills the plane, and the base-2 version fills the line; but the base-6 version probably doesn't fill 3d-space, and so on.

What about the base-$8$ version you have, which doesn't really fit into this cubical pattern? Well, it will still fill space with probability $1$, but that takes a bit of work.


OK, so what about the second question - how random is $\pi$?

Say that a real number $r$ is simply normal to base $b$ if, in the base-$b$ expansion of $r$, each of the possible $b$-many digits appears ${1\over b}$th of the time. (That is, $$\lim_{n\rightarrow\infty}{\mbox{number of occurrences of $d$ in the first $n$ base-$b$ digits of $r$}\over n}= {1\over b},$$ for each digit $d$.) For example, Champernowne's constant is simply normal to base $10^k$ for every $k$. A number $r$ is absolutely normal if it is simply normal to every base; this implies that every sequence of $k$ digits in base $b$ appears the "right" proportion of the time in the base-$b$ expansion of $r$ (consider base $b^k$).

It is strongly believed that $\pi$ (and many other interesting real numbers) are absolutely normal, but this remains wildly open. Currently, we do not even know a single "natural" example of a real number which is absolutely normal! (We do know explicit examples - see e.g. this 2002 paper of Becher - but they are very contrived.) However, we also know that "most" (measure-$1$) real numbers are absolutely normal! Basically, if you determine the digits of a real number by flipping an appropriate coin, with probability $1$ the result is absolutely normal.

To the best of my knowledge, it is not known whether $\pi$ is simply normal to any base, or even if every digit occurs infinitely often in $\pi$ for in any specific base $>2$. As the comments above have stated, absolute normality is almost certainly overkill for showing that the 2d-walk fills the plane with probability $1$ (see Robert Israel's answer below), but I don't think we have proved any sufficient amount of "randomness" about $\pi$.

$\endgroup$
  • $\begingroup$ Very long, but superb answer! (+1) $\endgroup$ – Peter Aug 26 '16 at 21:24
7
$\begingroup$

Equiprobability in base $8$ is not necessary, as you could tour the plane with e.g. digits $1,4,6$.

And normality is not sufficient: consider a sequence that is random except that when the walker would otherwise hit $[1,0]$ you change the digit. Although this will require changing infinitely many digits (because a random walker in the plane will hit $[1,0]$ infinitely many times), the fraction of digits to be changed goes to $0$ (asymptotically, the probability of the random walker being at $[1,0]$ at time $t$ decreases like $1/t$), so that these changes do not affect normality in any base.

$\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.