# Is it meaningful to talk about margins-of-error in a Markov Chain?

We're creating a Markov Chain based on an analysis of user's history. We add up and normalise users behaviour, and then normalise to create a two dimensional map of probabilities, but some of these probabilities are very low and I was wondering if there is a margin of error, and how you might go about calculating that?

-

Didier's answer is complete and correct, but I wanted to give you something more like a 'practitioner's viewpoint' and use some slightly less technical language.

Let's say you want to approximate some process as a Markov chain whose state at time $t$ is $x_t$, and there are $N$ states $1,\dots,N$ in total. Then you are trying to estimate a whole bunch of transition probabilities which you collect together into a matrix $Q$ called the transition matrix, with entries

$$Q_{ij} = \textrm{Pr}(x_{t+1} = j | x_t = i)$$

i.e. the probability of a transition from $i$ to $j$. The maximum likelihood estimate (in some sense the 'best' estimate) of the transition probability $Q_{ij}$ is the number of times we've seen the transition happen, divided by the number of times we've been in state $i$, that is

$$\hat{Q}_{ij} = \frac{n_{ij}}{n_i}$$

where $n_i$ is the number of times you've been in state $i$ and $n_{ij}$ is the number of times you've seen a transition from $i$ to $j$.

To save me writing $i$s and $j$s all over the place, I'm just going to call this probability $q$, and I'm going to replace $n_i$ with $n$ and $n_{ij}$ with $m$, so we're now trying to estimate $q$ with the proportion

$$\hat{q} = \frac{m}{n}$$

This is just estimating a binomial proportion. The variance of a binomial random variable with probability $q$ is $q(1-q)$ (and our best estimate of the variance comes by replacing $q$ with $\hat{q}$) so an approximate 95% confidence interval for our transition probability is

$$\hat{q} \pm 1.96 \sqrt{\frac{\hat{q}(1-\hat{q})}{n}}$$

where we've approximated our binomial distribution with a normal one. There are two problems with this: (i) we're throwing out some knowledge, namely the fact that the transition probabilities have to add up to 1 given the state we came from (this is the source of degeneracy in Didier's covariance matrix) and (ii) this interval is totally borked whenever $q$ is small or when we don't have many samples -- in particular it is infinite when $n$ is zero! If you're trying to estimate a Markov chain with a large number of states, you'll nearly always be in the case where you don't have enough samples.

What can you do instead? The Bayesian solution is to incorporate your prior beliefs about the transition probabilities. Maybe you don't have any prior beliefs, but that's fine too. You can go down two routes:

1. Use a uniform prior
2. Use a Jeffery's non-informative prior

Arguably (2) is a better representation of reality, but frankly it's a lot harder to implement, so I'd go with (1) if I were you. All this means is that you replace your estimate for the transition probability $q$ with

$$\tilde{q} = \frac{m+1}{n+N}$$

(remember $N$ is the total number of states). This is equivalent to assuming that you'd seen each transition precisely once before you started the experiment, and it's also known as Laplace smoothing with smoothing parameter 1. If some transitions are impossible (e.g. there is no hyperlink from page 3 to page 6) then you can incorporate that into your priors as well by suitably modifying this equation (concretely, you don't put the '$+1$' in the numberator if the transition is impossible, and you replace the $+N$ on the bottom with $+M$, where $M$ is the number of possible transitions from that state).

This will almost certainly give you a nicer transition matrix than using maximum likelhood estimation, and it's also guaranteed to converge to the true transition matrix as the number of samples increases.

To get confidence intervals for this estimate, you could again use the normal approximation, replacing $\hat{q}$ by $\tilde{q}$ and $n$ with $n+N$. If you wanted to be more accurate for the cases where you don't have much data, you can use a more accurate estimator, for example the Wilson score interval, but if all you want is a rough idea of how accurate your estimates are, then the normal approximation should be fine.

-
I think this is the longest answer I've ever written on this site, so I hope it's useful! –  Chris Taylor Nov 19 '11 at 14:36
In what parts of my answer do I use some slightly more technical language? –  Did Nov 19 '11 at 19:01
Hi Chris, thanks for the response. Its really good. Unfortunately, I'm a bit of a math noob so I'm still trying to read through it. Do you know any good books that a beginner could get started with this subject? –  Ricardo Gladwell Nov 20 '11 at 10:00
@Didier "well-defined", "strong law of large numbers", "CLT-type result", "stationary measure". I don't think there's anything wrong with your answer, but I hazarded a guess that the OP might not be mathematically sophisticated enough to know what they are. Although I then probably got carried away with my own answer and used some technical language there too. Oh well. –  Chris Taylor Nov 20 '11 at 11:54
@Ricardo If there's anything you don't understand feel free to ask. You might want to take a look at this series of video lectures for an intro to modelling with markov chains: ai-class.com/course/video/videolecture/138 –  Chris Taylor Nov 20 '11 at 11:55

When one observes a finite Markov chain with transition probability matrix $Q$ during an interval of time of length $n$, the coefficients of $Q$ are often estimated through a matrix $\hat Q_n$ defined as follows: for every vertices $x$ and $y$, $\hat Q_n(x,y)=N_n(x,y)/N_n(x)$, where $N_n(x,y)$ denotes the number of times a transition from $x$ to $y$ occurred and $N_n(x)$ denotes the number of times the vertex $x$ was visited.

If $n$ is large enough, $N_n(x)\ne0$ for every $x$ hence $\hat Q_n$ is well defined and is indeed a Markov transition matrix, and, by the strong law of large numbers for Markov chains, $\hat Q_n(x,y)\to Q(x,y)$ almost surely, for every $x$ and $y$.

The discrepancy $\hat Q_n-Q$ (which might be what you are after and are calling margin of error) satisfies a CLT type result, namely, $\sqrt{n}(\hat Q_n-Q)\to Z$ where the convergence is in distribution and $Z=(Z(x,y))_{x,y}$ is a centered Gaussian family indexed by the ordered pairs of states of the Markov chain and whose (degenerate) covariance matrix $\Sigma$ can be explicitly written down in terms of $Q$ and of the associated stationary measure $\pi$ through some explicit series of coefficients of powers of $Q$.

The take-home message here is that, assuming that the empirical matrix $\hat Q_n$ is known (and that $n$ is large enough for $\hat Q_n$ to be well defined), the theoretical matrix $Q$ is such that, for every states $x$ and $y$, $Q(x,y)=\hat Q_n(x,y)-\frac1{\sqrt{n}}Z_n(x,y)$ where $Z_n$ is asymptotically centered Gaussian with a (semi-explicit) covariance matrix $\Sigma$.

-