# Markov Chains vs. Bayesian Network

Background: I'm doing a project that takes a user's tweets and uses Markov Chaining to make up tweets. I'm putting together a presentation on this, and I'm struggling to make a meaningful distinction between Markov Chains and Bayesian Networks. I've looked at other explanations that are mainly about the more general Markov Process. They describe the Markov Process quite well, but things seem to go a bit over my head when they get into the Bayesian Network details.
At one point they describe the Bayesian Network as "representing a factorization of some joint probability distribution." Could someone break this down for me a bit more simply? That's one thing that may help!

From what I can tell, a Markov Chain is a directed, potentially-cyclic graph with weights between 0 and 1 (and with any given node's edges summing to 1). A Bayesian network is a directed, acyclic graph which doesn't seem to have weights, but rather a table of bayesian probabilities? It's not very useful to me to think of the difference between them as being the presence of loops, and I'm not sure I fully understand a Bayesian Network – is the difference going to mainly be that the Markov Chain introduces a random element, or is that also in the Bayesian Network?

First of all let me say that the two things you want to compare are entirely different objects and describe different things. The graph that you refer to as "describing" a markov chain is not on the "same level" as a graph describing a Bayesian network. For easing up the notation, let me name the graph with two nodes in the link the 'Markov' graph. What happens in this markov process is that we have some object that moves through states in discrete steps in time. So let us make a simple example: We observe a single human person. It (the person) can decide every day whether or not it will have pizza (P) or hamburger (H). We imagine that this human being existed since day 0 and exists for eternity. I.e. we have a concrete set of observed 'states' $s_0, s_1, s_2, ...$. One can imagine these concrete observed states as a deterministic function in some set of variables. We only have partial access to these variables: in our example, the variables could be just two components: the mood (can either be 'good' or 'bad') of the person and the meal it had the day before. We imagine that there are some functions $X_n : \Omega \to \{G, B\} \times \{P, H\}$ that gives the mood on day $n$ and the meal of the day before. We imagine that $s_n = f(X_n(\omega))$ for some single $\omega$ (the unique element containing all the information about the universe we live in) and some deterministic function $f$ and the goal is to determine this function $f$. $f$ could be something simple like 'if the mood is good then the outcome is the opposite of the meal yesterday and otherwise it is the meal of the day before' or something more complicated. As we do not have access neither to $\Omega$ nor $\omega$ nor the outcomes of $X_n$ (we cannot observe the mood, i.e. there are factors that disturb our measurements) the $X_n$ are 'random variables', meaning that in our brains we do never know the actual outcome but we just have some clue which outcome it could / should be. We name $S_n = f \circ X_n$. As $X_n$ is a random variable, so is $S_n$.

Now the Bayesian network describes the relations between the whole set of random variables $S_1, S_2, ...$. In very simple word, a Bayesian network is nothing else than defining an expression for the common density of $S_1, S_2, ...$, i.e. it brakes down $p(s_1, s_2, ...)$ into some product of simpler expressions. In the special case of a markov chain it defines all the finite common densities $p(s_1, ..., s_n)$ to be $p(s_n|s_{n-1}) * p(s_{n-1}|s_{n-2}) * ... * p(s_1|s_0) * p(s_0)$, i.e. a Markov process can be described using a Bayesian network.

Very formally and generally, for a given Bayesian Network graph over the finite collection of random variables $X_1, ..., X_n$ is that it defines the common density of all the $X_i$ as

$$p(x_1, ..., x_n) = \prod_{\text{node n}} p(\text{variable mentioned in node n} | \text{parents of node n})$$

Example:

just means that $p(a,x,v)$ is defined to be $p(a|x,v)*p(x)*p(v)$. This is to be read that $X$ and $V$ influence $A$ and $X$ and $V$ are independent.

However the Bayesian network merely defines the relationships between all the random variables involved, it does NOT define the remeining expressions. In the example above, it does not tell us anything about how to define $p(a|x,v)$ nor $p(x)$ nor $p(v)$. I.e. in the Markov example above the mere Bayesian network does not define the $p(s_k|s_{k-1})$ expressions. That is the task of the designer of the Bayesian network. Here comes the other graph into play: The Markov Graph on Wikipedia implicitly assumes that there is an infinite Bayesian Network graph in the background that looks like this:

The form of this graph essentially tells us two things: There is a 'true' unobserveable state $X_n$ and this state determines the observed state $S_n$ and the state $X_n$ only depends on the true state $X_{n-1}$ but not one the $S_j$ nor on $X_{n-2}, X_{n-3}, ...$ or even the future states. However, as stated above, this does not tell us how $p(s_k|s_{k-1})$ (nor the $p(x_n|x_{n-1})$) are defined.

For now, let us forget about the fact that there is a true state and let us consider the simplified Bayesian network

i.e. $p(s_0, ..., s_n) = p(s_n|s_{n-1})*p(s_{n-1}|s_{n-2})*...*p(s_1|s_0)*p(s_0)$ so we still need to know how these simple probability distributions are defined. What the MArkov Graph on wikipedia tells you is precisely this in a different form. Since the $s_j$ can only be two things, either $H$ or $P$ we need to fill the following table:

s_n | s_{n-1} | p(s_n|s_{n-1}
H |       H |           ???
H |       P |           ???
P |       H |           ???
P |       P |           ???


a graph like this

would then tell you to fill this table as follows:

s_n | s_{n-1} | p(s_n|s_{n-1}
H |       H |           0.3
H |       P |           0.6
P |       H |           0.7
P |       P |           0.4


for example, if the person had pizza yesterday ($s_{n-1} = P$), the chance that he has hamburgers today ($s_n = H$) is located at the transition from the state $P$ to $H$, i.e. this arrow has a 0.6 attached to it, hence, $p(s_n=H|s_{n-1}=P) = 0.6$.

I.e. in short:

This markov graph inplicitly means that it enflates to an infinite set of random variables and it implicitly means (by the work 'Markov' in it) that this infinite graph has a certain structure (the current thing only depends on the state right before it but not on the past before and not on the future) and the boundary/marginal probabilities (the simple terms that survive in the definition of the common density) are given by some probabilities denoted in the simple graph.