4
$\begingroup$

Let's say I've been captured by Russian operatives and am locked in a room with only one object: a book listing the digits of $\pi$.

I'm told to generate a sequence of binary digits. If this sequence is random, they will cut off one of my arms and let me free; if this sequence is not random, however, I will be killed.

My first solution was to take the digits of $\pi \ \text{mod} \ 2$, so that:

$$3.1415926535897...$$ $$\downarrow$$ $$1.1011100111011...$$

And I would read the digits from left-to-right of the second number.

My Question

Is there any way to prove that the bits I generate are random (no discernible pattern)?

Are the digits of $p \ \text{mod} \ 2$ random for any transcendental $p$? How about any irrational $p$?

I feel like this should be a really easy question (with an affirmative answer), but I don't know how to show it.

$\endgroup$
  • 1
    $\begingroup$ How do you define "random"? How would they be able to test whether a sequence you give is randomly generated or generated via some method which is not truly random? By the very nature of the fact that you are using a mathematical constant, if you were to create your "random" sequence using the same method more than once you will have exactly the same result. How is this possibly random? $\endgroup$ – JMoravitz Jun 2 '16 at 18:12
  • 2
    $\begingroup$ Why russian operatives? Is it arbitrary or a manifestation of the rampant russophobia? Also, that book would have to be a really big one.. $\endgroup$ – MathematicianByMistake Jun 2 '16 at 18:21
  • 1
    $\begingroup$ "rampant russophobia" :D $\endgroup$ – Zubin Mukerjee Jun 2 '16 at 18:41
  • $\begingroup$ @MathematicianByMistake I'm less concerned about the Russian operatives and more concerned about the fact that OP still loses an arm even if he's able to get results. $\endgroup$ – anonymouse Jun 2 '16 at 18:49
  • $\begingroup$ @SSS haha Well, indeed it's not like one may go very far while missing a limb! The problem remains though in defining random-as JMoraviz pointed out. What sequence would satisfy "randomness"?.. $\endgroup$ – MathematicianByMistake Jun 2 '16 at 18:51
4
$\begingroup$

$\pi$ has an infinite number of digits.

Thus a book listing all the digits of $\pi$ would be infinitely big.

So the room containing both you and the book would be infinitely big as well.

You are in an infinitely big room, hence you are free.

$\endgroup$
  • 7
    $\begingroup$ I think your last step is unwarranted. The room might be infinitely big, but still only big enough to contain you and that book. Which means that you'll have zero freedom to move. $\endgroup$ – Raskolnikov Jun 2 '16 at 18:26
  • $\begingroup$ This is funny, but doesn't really answer the question. $\endgroup$ – Noah Schweber Jun 2 '16 at 18:29
  • $\begingroup$ @NoahSchweber I think that the question is somewhat vague while also a bit racist-in the russophobic-sense. $\endgroup$ – MathematicianByMistake Jun 2 '16 at 18:32
  • $\begingroup$ @Raskolnikov Honestly I had not thought of that ! Neat observation! $\endgroup$ – MathematicianByMistake Jun 2 '16 at 18:33
  • 2
    $\begingroup$ As a variation on this: Since the book is infinitely long, it took an infinitely long time to produce. Hence you are presumably in a situation where time has no meaning and you are already in a lot more trouble than merely being in prison. $\endgroup$ – Semiclassical Jun 2 '16 at 18:58
3
$\begingroup$

You should be precise about what you mean when you say "random", since "no discernible pattern" is still ambiguous.

You should read about pseudorandom number generators, because that may be the kind of randomness you want.

As for $\pi$, it isn't even known whether $\pi$ is a normal number in any base.

$\endgroup$
2
$\begingroup$

There are long lists of digits for $\pi$ online. You could write a computer program that calculates different types of statistics to test your hypothesis.


One interesting statistic could be to measure $$P(X_{i+1}=1|X_{i},\cdots,X_{i-n})$$That is: the conditioned probability of one bit being $1$ given that we know the binary number of length $n$ preceding it. This conditioned probability should converge to the stationary $P(X_{i+1}=1)$ for all such $n$ bit numbers if there is no short term-memory in our source.

$\endgroup$
1
$\begingroup$

I suspect you are wondering if you could begin arbitrarily at a point somewhere within the infinite pool of decimal numbers and then start creating One Time Pads (OTP).

Although it would be hard to detect by most people, and it does emulate randomness, it's not truly "pure random" because it does technically have a discernable pattern. It would fool most, but not all. It likely could be used for non-cryptographic applications. You would not want to use Pi(π), Phi(Φ), Euler's Constant(e), the Bible, War and Peace, Moby Dick, or any other known, discernable sources if the intent is for "pure random" crytography.

$\endgroup$
  • $\begingroup$ "it does emulate randomness" I think this is an unsolved problem, since it's not even known yet whether $\pi$ is a normal number in any base. $\endgroup$ – Zubin Mukerjee Jun 5 '16 at 5:43
0
$\begingroup$

What does "random" mean? In one natural sense (or class of senses, rather) coming from computability theory, your sequence is not random: even though it's hard to notice it, there is a pattern to the bits.

While it's clear that in some intuitive sense "$\pi$ mod 2" is somewhat random, and "$\pi$" is somewhat less random, I suspect it will be very difficult to pin down exactly what you mean by this (and so very difficult to give a satisfying answer to your question!).

$\endgroup$
0
$\begingroup$

Someone could say that there's nothing random in Pi's digits, meaning that those digits are there already, you just don't know what they are! Just don't tell the Russian how you got those binary digits!

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