display | more...

I've looked at raincomplex's homenode picture a million times, and thought, eh, yeah, a state transition graph on his whiteboard. Big deal. Until today.

Today I was bored and looked at it again, and thought it might be fun to see what kind of string of states I'd get if I walked through the graph a number of times. And then, because I was REALLY bored, I wrote out the state transition matrix and wondered what it would look like if I multiplied it by itself a bunch of times. Here are the results.

The diagram on his homenode gives a set of rules of a six sided die, if the die faces were labeled 0,1,2,3,4,5 instead of the usual 1,2,3,4,5,6. The die face is the state. But the results are exactly the same. The transition rules are:

  1. When the die face is 0, the next possible die face is either 0 or 3, with equal likelihood of either appearing.
    (Note: in his notation, you're rolling another imaginary die, and if that second imaginary die shows 0,2, or 4, then your first die face remains 0, and if the second one shows 1, 3, or 5, then the first die face changes to a 3. Obviously, with a fair die, either outcome is equiprobable.)
    Let's make up some notation. Let's write it this way: P{0|0}=1/2, P(3|0}=1/2,
    meaning, in words, "The probability of the next state being 3, given that the present state is 0, is 1/2"
    So the general notation is Prob{next state given present state} = (some number)
  2. When the die face is 1, the next possible die face is either 0 or 3, with equal likelihood of either appearing.
    P{0|1} = 0.5
    P{3|1} = 0.5
  3. When the die face is 2, the next possible die face is either 1 or 4, with equal likelihood of either appearing.
    P{1|2} = 0.5
    P{4|2} = 0.5
  4. When the die face is 3, the next possible die face is either 1 or 4, with equal likelihood of either appearing.
    P{1|3} = 0.5
    P{4|3} = 0.5
  5. When the die face is 4, the next possible die face is either 2 or 5, with equal likelihood of either appearing.
    P{2|4} = 0.5
    P{5|4} = 0.5
  6. When the die face is 5, the next possible die face is either 2 or 5, with equal likelihood of either appearing.
    P{2|5} = 0.5
    P{5|5} = 0.5

You can rewrite this as a probability transition matrix, T, where the element in the ith row and the jth column is the probability of transition from state i to state j, where (i,j) = {0,1,2,3,4,5}. (Note that the matrix starts with a zeroth row and a zeroth column, like in Matlab.)

 1/2   0    0   1/2   0    0
 1/2   0    0   1/2   0    0
  0   1/2   0    0   1/2   0
  0   1/2   0    0   1/2   0
  0    0   1/2   0    0   1/2 
  0    0   1/2   0    0   1/2 

Multiplying the probability transition matrix T by itself is squaring it. So T2 is:

 1/4  1/4   0   1/4  1/4   0
 1/4  1/4   0   1/4  1/4   0
 1/4   0   1/4  1/4   0    0
 1/4   0   1/4  1/4   0    0
  0   1/4  1/4   0   1/4  1/4
  0   1/4  1/4   0   1/4  1/4

Let's keep going. We're suckers for deducing patterns, aren't we? T3 is:

 1/4  1/8  1/8  1/4  1/8  1/8
 1/4  1/8  1/8  1/4  1/8  1/8
 1/8  1/4  1/8  1/8  1/4  1/8
 1/8  1/4  1/8  1/8  1/4  1/8
 1/8  1/8  1/4  1/8  1/8  1/4
 1/8  1/8  1/4  1/8  1/8  1/4

It turns out that if you keep going, and let N go to infinity, then TN is:

 1/6  1/6  1/6  1/6  1/6  1/6
 1/6  1/6  1/6  1/6  1/6  1/6
 1/6  1/6  1/6  1/6  1/6  1/6
 1/6  1/6  1/6  1/6  1/6  1/6
 1/6  1/6  1/6  1/6  1/6  1/6
 1/6  1/6  1/6  1/6  1/6  1/6

Pretty cool, huh? This says that every state is equally probable in the long run.

It is NOT equiprobable in the short run! If you know that you are in one state, then the rules of transition still apply: If you are in state 1, for example, you KNOW that your next state is going to be either 0 or 3, and no others! But if you run this pseudorandom sequence over a long enough time, your probability of being in any given state is equiprobable, with equal probability of 1/6.

If you rolled this crazy die, here's what a sequence of throws would look like:

 0 3 4 2 4 5 5 5 2 1 3 4 5 2 1 0 0 3 1 0 3 4 2 4 5 2 1

I'm not sure of user raincomplex's use for this little rule based algorithm but perhaps he can post that himself.

Probability transition matrices are used in coding and information theory, the theory of random processes, Markov chains (and more generally, Markov processes, like our favorite bot, E2D2, uses to generate something close to natural language comments in the catbox), mathematical economics, queueing theory, and even the design of communications protocols. You don't want to be stuck in a certain state for which there is no way out, or a loop out of which you can never transition.

My friend Steve Heppe created a probability transition matrix for all the squares of Monopoly, plus the cards you'd get that would instantly shuffle you off to jail or Go, or the nearest railroad, and he determined that, long term, some squares were more likely than others, so you ought to buy those and put up hotels on them. Every Monopoly player is aware of the tendency to land on certain squares more than others. Steve did this when he was in high school. Smart feller. Of course, it was TJHSST, the best public school in the country.

REFERENCES

  1. Richard W. Hamming, Coding and Information Theory, Prentice-Hall, (c)1980, pp. 80-85
  2. Norman Abramson, Information Theory and Coding, McGraw-Hill, (c)1963, pp. 95 ff.
  3. Athanasios Papoulis, Probability, Random Variables, and Stochastic Processes, (c)1965, pp. 532 ff. The magnificent, magisterial first edition. It's probably on more bookshelves of more communications engineers and coding/information theorists than any other book. My advisor at Georgia Tech, Dr. Aubrey Bush, had this book thoroughly memorized. He could tell me what page a certain topic or theorem was on. "The Price theorem? Ah yeah, that suckah's on page 226. Ol' Bob Price was at MIT with me when he came up with that. Good man, Bob. Smart feller."
  4. Athanasios Papoulis and S. Unnikrishna Pillai, Probability, Random Variables, and Stochastic Processes, 4th ed., (c)2002, pp. 698 ff. Some day I'm going to write a node about Papoulis. His very name strikes fear into the hearts of all first year graduate students in electrical engineering, because it was synonymous with the dreaded random processes classes we all had to take. His books are wonderful.

The image in question is a state transition graph I drew (pencil, 5cm x 5cm), with six nodes, transcribed below.

0 --024--> 0
0 --135--> 3
1 --024--> 0
1 --135--> 3
2 --024--> 1
2 --135--> 4
3 --024--> 1
3 --135--> 4
4 --024--> 2
4 --135--> 5
5 --024--> 2
5 --135--> 5

The rules describe a one-dimensional six-state cellular automaton with an asymmetric neighborhood, with one extra state not shown above (called 6). Oops. I mean, I totally omitted it so as to preserve the beautiful symmetry of the graph. The rules for 6 are: 6 --0246--> 6 and 6 --135--> 4. In each rule, the left number is the current cell, the center numbers are allowed values for the cell just to its left, and the right number is the value of the current cell in the next generation.

A state is a finite sequence of cells valued 0-5. To the left of this sequence is an infinite number of 0s, and to its right an infinite number of 6s. (Below I indicate this with a single 0 and 6 on either side of the state.) So suppose we begin with the state 31:

Generation  1:  0316

                03   a 3 with a 0 to the left becomes a 1
                 1   (3 --024--> 1)

                 31   a 1 with a 3 to the left becomes a 3
                  3   (1 --135--> 3)

                  16   a 6 with a 1 to the left becomes a 4
                   4   (6 --135--> 4)
so,
Generation  2:  01346
Generation  3:   0456
Generation  4:   02246
Generation  5:   01126
Generation  6:    0346
Generation  7:    0156
Generation  8:     0546
Generation  9:     0256
Generation 10:     01246
Generation 11:      0426
Generation 12:      0216
Generation 13:      01046
Generation 14:       0326
Generation 15:       0146
Generation 16:        056
Generation 17:        0246
Generation 18:        0126
Generation 19:         046
Generation 20:         026
Generation 21:         016
Generation 22:          046
Generation 23:          026
Generation 24:          016
Generation 25:           046

You'll notice that the numbers "travel" to the right, eating into the infinite 6s there. At the end, the state begins to cycle (albeit offset by one cell each cycle) between 4, 2, and 1. Does this seem familiar? If we treat the states as integers in base 6, ignoring the 6s:

Generation  1:  0316 = 19
Generation  2:  01346 = 58
Generation  3:   0456 = 29
Generation  4:   02246 = 88
Generation  5:   01126 = 44
Generation  6:    0346 = 22
Generation  7:    0156 = 11
Generation  8:     0546 = 34
Generation  9:     0256 = 17
Generation 10:     01246 = 52
Generation 11:      0426 = 26
Generation 12:      0216 = 13
Generation 13:      01046 = 40
Generation 14:       0326 = 20
Generation 15:       0146 = 10
Generation 16:        056 = 5
Generation 17:        0246 = 16
Generation 18:        0126 = 8
Generation 19:         046 = 4
Generation 20:         026 = 2
Generation 21:         016 = 1
Generation 22:          046 = 4
Generation 23:          026 = 2
Generation 24:          016 = 1
Generation 25:           046 = 4

When decreasing, the numbers are being divided by two (ni+1 = ni/2). When increasing, they are following the formula ni+1 = 3ni+1. This is the hailstone sequence, which if the Collatz conjecture is true, does always end with the (4, 2, 1) cycle, for any initial state ≥ 1.

Why does this work? In short, because 3n = 6(n/2). That is, in base 6, multiplying by three is the same thing as dividing by two and then shifting one digit to the left (i.e., adding a 0 on the right side). The rules at the top of this writeup describe division by two in base 6*. Thus to multiply by three and add one**, we simply need to move everything a digit to the left and add 4***, then divide by two as normal, according to the rules.

* The derivation of which is tedious beyond the scope of this writeup.
** as per the Collatz function when the argument is odd (which in base 6 occurs when it ends in 1, 3, or 5)
*** The rules perform truncating division for odds---adding 4 makes up for both the truncation (1/2 in base 6 is ".3") and the "add one" part of 3n+1. This addition is the sole reason for the extra symbol (6).

Does this get us closer to a solution to the conjecture? Who knows, and probably not. The whole thing is so simple and yet something flabbergastingly impenetrable is happening. It's very easy to restate in other ways, and so far that hasn't helped anybody figure it out.

Log in or register to write something here or to contact authors.