• Black YouTube Icon
  • Black Google+ Icon
  • Black Facebook Icon
  • Black Twitter Icon
  • Black LinkedIn Icon

© 2016 by One on Epsilon PTY LTD

Are These Digits Random?

April 28, 2017

Try chanting a list of random digits. For example, "3", "5", "2", "8" and so fourth. What makes you choose those digits instead of others?

 

It isn't easy to understand how the brain works in this case. I certainly don't understand it. Nevertheless, we can explore some mathematics associated with sequences of digits that appear random, even though they are not.

 

For starters, look at the list of digits 0741852963. Do you recognize any pattern or rule? Most likely not.

 

But what you can do is notice that every decimal digit appears exactly once in 0741852963. When this occurs, such a list is called a permutation of the digits 0-9.

 

There are many possible permutations. Aren't there? Everyone knows the standard permutation 0123456789 in which the digits just increase one by one. Similarly, 9876543210 is easy to describe. But many permutations, like 0741852963, are more obscure.

 

Actually, how many permutations are there? This isn't the subject of this week's post, but we might as well have a quick look at it:

 

There are 3,628,800 possible permutations of the digits 0-9.

 

You can obtain this number using 10 factorial, written 10!. Yes, the exclamation mark reads “factorial” and means multiplying 10 by 9 by 8 by 7 all the way down to 1:

 

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800.

 

Now here is a question: Are some of the permutations "more random" than others?

 

There isn't a definitive answer. If there was one, it would perhaps depend on how we measure randomness. If for example, we would just assume that every permutation is equally likely, then 0123456789 or 9876543210 are not more random than the 0741852963 that we started with.

 

Nevertheless, 0123456789 is less obscure than 0741852963. Would you not agree? As you are reading this, I bet you that somewhere around the globe a child is counting 0123456789. But who is thinking about 0741852963 at the moment? Perhaps it is just you and the others reading this blog post?

There is an area of theoretical computer science that measures randomness of sequences based on how hard or easy it is to describe (or program) the sequence. This type of thing is sometimes called the Kolmogorov Complexity of the sequence. The ideas and theory of Kolmogorov Complexity are complex, so let's not go there fully. Instead, let's borrow the general principle: "How to describe (or program) a sequence of digits"?

 

Q: How would you describe 0123456789?

A: "Write the digits 0-9 in an increasing order." Simple!

 

Q: Could you write a computer program that does that?

A: Yes. Without focusing on any specific computer programming language, let's maybe describe the procedure, program or algorithm like this:

 

1: set x to be 0

2: do lines 3 and 4, 10 times

3:   print x

4:   set x to be x+1

 

Not a programmer? No problem. Just treat lines 1,2,3 and 4 as commands to a computer. In line 1, a variable x is set to the value 0. Then lines 3 and 4 are circulated through 10 times. In line 3 the value of x is printed and in line 4 the value is incremented by one.  Can you now see why this program prints 0123456789?

 

Q: When the program finishes, what is the value of x?

A: x = 10. However, that value is never printed.

 

Q: OK, so how would you write a program for the sequence 9876543210?

A: Maybe something like this?

 

1: set x to be 9

2: do lines 3 and 4, 10 times

3:   print x

4:   set x to be x-1

 

Do you see how it works? What is the value of x when this program finishes?

So lets get back to our special permutation 0741852963. How do we write a program to create this sequence?

 

For an arbitrary permutation of the digits, there typically isn't a simple program. But 0741852963 is not an arbitrary sequence. As I prepared this blog post, I created it using a linear congruential generator. This is a classic, simple, yet robust manner for creating a sequence of numbers that appears random. Such a sequence is sometimes called pseudorandom.

 

Generation of (pseudo)random numbers has many applications including cryptography, video-games, statistics and general scientific computing. Being able to ask the computer to generate numbers that appear random is a great feature.

 

The linear congruential generator is typically applied for numbers much bigger than a single digit. Nevertheless, exploring how we use it to make an arbitrary (looking) permutation of 0-9, can be very instructive. Let's do that.

So here is the code for our specific sequence, 0741852963:

 

1: set x to be 0

2: do lines 3 and 4, 10 times

3:   print x

4:   set x to be (11*x + 7) mod 10

 

You may be impressed that the code is compact and looks very similar to the code for generating 0123456789. Almost exactly the same! What are the differences?

 

You now perhaps ask  what is (11*x+7) mod 10?  Here "mod" stands for modulo.

 

A number z mod 10  is the remainder obtained when dividing z by 10.
You can also do mod 2, mod 45, or mod any number.

 

Q: What is 23 mod 10?

A: 23 divided by 10 is 2 with a remainder of 3. So 23 mod 10 = 3.

 

Q: So isn’t any (whole) number mod 10, just the units digit of the original number?

A: Yes. Indeed when looking at numbers using base 10, mod 10 is special.

 

Just to see you are comfortable with modulo:

 

Q: What are the numbers z, such that z mod 2 = 0?

A: These are exactly the even numbers!

 

Q: So are the numbers z with z mod 2 = 1, exactly the odd numbers?

A: Yes!

OK, so you understand mod.  Look now again at the line, (11*x+7) mod 10. This line takes x, multiplies by 11, adds 7 and then takes mod 10, keeping only the units digit. This may seem like some sort of black magic, but let's see how it works.

 

Write out what is happening in lines 3 and 4, repeating 10 times:

 

printing 0

x = (11*0 + 7) mod 10 = 7

 

printing 7

x = (11*7 + 7) mod 10 = 84 mod 10 = 4

 

printing 4

x = (11*4 + 7) mod 10 = 1

 

printing 1

x = (11*1 + 7) mod 10 = 8

 

printing 8

x = (11*8 + 7) mod 10 = 5

 

printing 5

x = (11*5 + 7) mod 10 = 2

 

printing 2

x = (11*2 + 7) mod 10 = 9

 

printing 9

x = (11*9+ 7) mod 10 = 6

 

printing 6

x = (11*6 + 7) mod 10 = 3

 

printing 3

x = (11*3 + 7) mod 10 = 0

 

At this point the program stops. Notice that the last execution, setting x to 0, did not affect the output.

 

Q: If we ran the loop (on lines 3, 4) one more time what would it do?

A: Since x is again 0 (where it started), it would repeat as before and print 0. And if we continued to run for a whole ten steps, the whole sequence 0741852963 would be printed again.

There is so much more to say about the linear congruential generator, and there are many options for playing with it as well. For example, you may try to change the constants 11 and 7 in line 4 to other constants. After you do that, experiment to see what happens.

 

You'll see that some constants are "good" in the sense that they create a full permutation of 0-9, while others are "less good" as they yield much smaller cycles of digits. 

 

You can also do mod 100, or mod 1000, or mod any number that you wish. In fact, many computer software packages use the linear congruential generator with mod 2^32 - 1, or mod 2^64 - 1. These are the biggest possible integers on 32 bit or 64 bit  computers.

We'll leave understanding the theory associated with the linear congruential generator for another day. But if you want to drive curiosity and nurture connections with your  students or loved ones, then you can experiment with it and have fun.

 

Here for example is a video of a very engaging activity that I found on WooTube. Perhaps you can reproduce such an activity with your students or loved ones. See the Excel based examples that Eddie Woo explores in the second half of the video. Can you reproduce such an Excel spreadsheet? Try it. Challenge your children to do the same. Better yet, nurture your connection and drive their curiosity by doing it together.

 

 

 

 

 

 

 

 

Share on Facebook
Share on Twitter
Please reload

Featured Posts

Our blog posts moved to Epsilon Stream

January 3, 2019

1/1
Please reload

Recent Posts

October 5, 2018

September 29, 2018

Please reload

Archive
Please reload

Search By Tags
Follow Us
  • Register One on Epsilon
  • Black Twitter Icon
  • Black Facebook Icon
  • Black LinkedIn Icon
  • Black YouTube Icon