28

Storing a movie into π

 3 years ago
source link: https://www.tuicool.com/articles/EfMb6zm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

O ver the years many claims of a more romantic than scientific origin have been made about π . And all of them had something to do with the infinity or the fact that the its decimal part contains every other sequence of numbers never conceived.

This is not trueor at least no one knows how to prove it. That is, the demonstration of the normality of π does not exist yet.

But many mathematicians trust in the fact that π is a normal number, even without knowing how to prove it; that’s because all the researches done till now lead to this direction.

So, assuming that π is a normal number, we can state the following:

  • the numbers in its decimal part are evenly distributed
  • any sequence of numbers of any length is contained in π.

This means that we can find our phone number somewhere inside it or, given an appropriate encoding, our name or this article precisely.

So can we find a movie inside it? Yes, encoding both the movie and π as binary strings we can eventually find the sequence of bits representing the movie inside π.

mqaERrR.png!web

Ok…but if π really contains every movie in the world, article ever written and any kind of information ever produced, can we just look for them and take note of their positions inside π?

Again, yes we can! So why we are not doing it now?

Compression

Looking for a sequence of bits inside π in order to just store the position of its first occurrence, is a kind of compression because we hope to save space by just saving a position inside a number, instead of the whole sequence.

But in order to be effective, the position (that is a number) of the first occurrence of the sequence (that is another number) must be less than the sequence itself. Otherwise we are using more space than required.

Let’s do the math

What we want to know what is the average position in π of a given sequence {X₀, X₁, X ₂, …} and if the position is less than the value of the sequence (or if it takes up less space on average).

This information can be retrieved with the following theorem:

If {X₀, X₁, X₂, …} is a sequence of random variables that are independent and identically distributed on a set S of m elements, then the expected first-occurrence time of contiguous subsequence is given recursively by

where is the longest proper suffix of that is also a prefix of .

For example we may search for the sequence “456456”, that is .

As we can see the sequence can be described with just 6 digits, but its position inside π requires 7 digits (1001000). The sequence “456456” can be found in position 1023671 ≈ E [ T ] ≈ 2 ⋅ 456456 . Thus storing the position of “456456” requires more space than the sequence itself.

Also take in account for all that:

So the growth is exponential in subsequence-length n .

Conclusion

Although it is possible to “store” a movie inside π, assuming that it is a normal number, it is not convenient in terms of space or time to look for a sequence inside π and store its position. Saving the position statistically requires more space than storing the value directly and this amount of space grows exponentially.

This obviously is not limited to π only, but to any normal number.

Uzy2mq7.png!web


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK