If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science theory

### Course: Computer science theory>Unit 3

Lesson 2: Modern information theory

# Origin of Markov chains

Introduction to Markov chains. Created by Brit Cruise.

## Want to join the conversation?

• Could Markov chains be considered a basis of some (random) cellular automaton? I mean, each Markov chain represents a cell, the state of the cell is that of the chain, and the probabilities of switching a state could be replaced with an algorithm. Then you could arrange lots of chains on a grid, and get an automaton? • Interesting idea. Generally cellular automata are deterministic and the state of each cell depends on the state of multiple cells in the previous state, whereas Markov chains are stochastic and each the state only depends on a single previous state (which is why it's a chain).

You could address the first point by creating a stochastic cellular automata (I'm sure they must exist), or by setting all the probabilities to 1. The second point is a bit more tricky. You could create a state for each possible universe of states (so if you had a 3x3 grid and each cell could be on or off, you'd have 2^9 = 512 states) and then create a Markov to represent the entire universe, but I'm not sure how useful that would be.

If you created a grid purely of Markov chains as you suggest, then each point in the cellular automata would be independent of each other point, and all the interesting emergent behaviours of cellular automata come from the fact that the states of the cells are dependent on one another.

I suspect a cellular automata is a more general system than a Markov chain in that each state has multiple inputs (but then it is less general in that all the probabilities are generally equal to 1).
• How is the "central limit theorem" a dangerous idea and how did it correspond to the idea of eugenics as implied by the paper at ? • If you read more into Eugenics you'll see that the binomial distribution underlies (and one could argue justifies) some of the troubling implications of the movement. Though more generally, the topic of free will and determinism is a passionate/touchy subject as it's often tied to ones belief system(s)
• I've got a question. I was doing this experiment at home with the 2 glasses, and in each of the two glasses there were 2 red candies and 2 white candies. Except I got to the point where I had 4 red candies in the red box, and 4 white candies in the white box. It was Red's turn, which meant I could only pick red candies, thus messing my probabilities up, since the probability of picking a red candy neared 1. Can someone explain what I'm doing wrong please? • Cool experiment! The problem is that you should never move a bead from one cup to another. Watch the video again closely. The bead you choose should always go back into the same cup, and based on the color of that bead you move to another cup.

For example
if you were to pick a white candy from glass A, you should immediately put it back, output white, and then move to the cup which represents white.
• Claude Shannon's original paper and book (pub one year after), was much more narrowly targeted than today's information theory (actually it was called communication theory by Shannon originally, in fact). Why does this mathematical theory have such a huge range of applications to various academic disciplines today? In other words, did Shannon not see the possible connections, or did he just ignore them (except his three tier (Weaver's actually) heuristic). Did Shannon get it wrong, further, in not giving information a real physical series of values. Electrons do have some mass, after all. And they may be able to "collapse the wave function" when bouncing off, or a photon doing the same, a micro-subatomic "wavicle." • Why is it called a Markov Chain? Why not a Markov Loop? • So, if we found the most dependent variable in the world and found its ratio, we could conceivably understand the workings of the entire universe? • Okay but this is only a binary marcov chain. What if you had 3 or 4 or 5 different outcomes if it were independent but it is actually dependent? • Is there a way to calculate what the probability of each outcome (that is, mathematically and not by running a bunch of trials)? • Yes, I've done this and Brit Cruise said that it was right.

Look at the Markov chain in the exploration.
The probability of staying at 0 if you're at 0-->s0
The probability of changing from 1 to 0->c1
The probability of staying at 1 if you're at 1-->s1
The probability of changing from 0 to 1->c0
The ratio of 0s to 1s is
s0+c1 : s1+c0
Proof:

By knowing the ratio of 0s to 1s, we can find the probability of having a 0 and the probability of having a 1.
Let's say that the ratio of 0s to 1s is 3:2.
This means for every 5 outcomes, there are 3 0s and 2 1s.
The probability of having a 0 is 3/5 and the probability of having a 1 is 2/5.
The probability of having a 0 and the probability of having a 1 if the ratio of 0s to 1s is a:b is a/(a+b) and b/(a+b), respectively.
We can substitute s0+c1 in for a and s1+c0 in for b.
Probability of having a 0:
(s0+c1)/(s0+c1+s1+c0)
Probability of having a 1:
(s1+c0)/(s0+c1+s1+c0)

I hope this helps!
• Is the summary (at the end) of this question correct?

Let's say we have a Markov chain like the one seen in the Markov Chain Exploration.

Let's say you've set the Markov Chain to have the following probabilities.
Probability of 0-->1 is c0 (change from 0)
Probability of 0-->0 is s0 (stay from 0)
Probability of 1-->0 is c1 (change from 1)
Probability of 1-->1 is s1 (stay from 1)

The probability that we start at state 0 is 1/2 and the probability that we start at state 1 is 1/2. Therefore, we need to half the probabilities of everything if we are not told if we are at 0 or 1.

If we don't know if we are at 0 or 1...
Probability of 0-->1 is c0/2
Probability of 0-->0 is s0/2
Probability of 1-->0 is c1/2
Probability of 1-->1 is s1/2

Now, the probability we will get a 0 is the probability that we are moving to a 0. The starting probability will be irrelevant after infinite trials of the probability of 0 being the probability that we are moving to a 0. Also, this is the same case for 1.
The probability that we are moving to a 0 is s0/2+c1/2.
The probability that we are moving to a 1 is c0/2+s1/2.
Because of this, the ratio of a 0 to 1 after infinite trials is the ratio of the probability that we are moving to a 0 to the probability that we are moving to a 1 or
s0/2+c1/2 : c0/2+s1/2
Multiply both sides of the ratio by 2.
s0+c1 : c0+s1
This ratio might not be fully simplified if you plug in the probabilities, but this is as simplified as we can get algebraically.

Let's summarize this Question.
If we are using a Markov Chain of that found in the Exploration and
the probability of moving from a 0 to a 1 is c0,
the probability of moving from a 0 to a 0 is s0,
the probability of moving from a 1 to a 0 is c1, and
the probability of moving from a 1 to a 1 is s1, then
the ratio of 0s to 1s after an infinite number of trials is
s0+c1 : s1+c0  