0

I am familiar with discrete markov processes and idea of their convergence towards a stable distribution after some number of steps. But my question is much simpler--more like a validation of some intuition.

Say I am looking at the transition of population between 3 cities. I have a $3\times3$ transition matrix $M$ with entries $m_{ij}$ for the transition probability for a person moving from city $i$ to city $j$. I also have a vector $v_0$ of initial values--in this case the initial populations of the 3 cities.

My question is how to determine the population of the 3 cities after $k$ transitions? That is, we would like to know $v_k$.

Seems like the simplest results is akin to what we would see in a simple differential equation. Something like:

$$ \text{population after first transition} = v_1 = v_0M $$

The population after a second transition would be:

$$ v_2 = v_1M = (v_0M)M $$

If we iterate this forward, then we would get:

$$ v_k = v_0M^k $$

This seems simple enough, but just wanted to make sure I did not make some careless error or leave something out. Of course I can do an eigenvector decomposition of $M^k$ to quickly determine the matrix power for something larger than a $3\times3$ matrix.

krishnab
  • 2,461

1 Answers1

2

You appear to be confusing two different, but related processes. The $3\times3$ matrix $M$ gives the transition probabilities for an individual person moving from city to city. As you follow this one person around, the matrix $M^k$ then gives the $k$-step transition probabilities, that is, the probability that that particular person ends up in city $j$ after $k$ steps if she started in city $i$.

For the aggregate populations, on the other hand, the system is much larger. Depending on how you model it, you might have $N^3$ states, where $N$ is the total population (in this model you track the location of each individual), or $\binom{N+2}{2}$ states (in this model you track the population of each city, with a total population of $N$). Either way, the transition matrix is a lot larger than $3\times3$. Now, if you want to examine the expected population distributions, you can use your individual $3\times3$ matrix: by linearity of expectation, if you have a three-element vector with the city populations, then multiplying it by $M^k$ gives you the expected population distribution, not the actual one, after $k$ steps.

amd
  • 53,693
  • thanks for catching my confusion. Right on. I get what you are saying by having $N^3$ states where each element of the transition matrix represents the probability of an individual $n_h$ moving from city $i$ to city $j$. So if I have 4 individuals in the population, then I would have to look at combinations like v = [1 1 3 2], and [2 1 3 2], ( where cities = 1,2.3) and $v_h$ for individual $h \in 1...4$. So there are $3^4$ possible states and the transition matrix $M$ has $3^4$ elements. Is that right so far? – krishnab Dec 17 '18 at 03:30
  • @amd I'm a little confused by this answer. I can't see what difference it would make to track individuals rather than just populations unless you were actually concerned with the likelihood that some particular individual was in some city after k steps. To me, the OPs interpretation of the problem in terms of population vectors seems much more natural and useful. Maybe I've misunderstood something. – Tyberius Dec 17 '18 at 03:41
  • I think I still not clear about getting the expected population distribution. If I have a vector $s$ of total populations in each of the 3 cities. Lets use new letters for clarity. Say $s_0$ = [ 200 300 150]. I want to know what $s_k$ is. So you are saying that I could multiply $s_0$ by the $3x3$ matrix $M^k$ and get the expected population distribution? Is there a way to estimate the variance of such an estimate? I suppose if I used the larger individual population models of $N$ I could sample a set of rows, and get bootstrap estimates for the variance. But can't do that with the $3x3$ matrix – krishnab Dec 17 '18 at 03:50
  • Also if anyone has any good references on these kinds of discrete models, please pass them along :). It always helps to see examples. – krishnab Dec 17 '18 at 03:51
  • @Tyberius The problem with the OPs interpretation is that multiplying by $M^k$ gives only the expected population distribution after $k$ steps, not the actual one. You can certainly represent the population distribution at any time as a three-element vector, as I mention in my answer, but the state space then consists of all $(N+2)C3$ possible distributions. – amd Dec 17 '18 at 06:49
  • @amd I guess my confusion is stemming from what you mean by actual population. Since it's probablistic, we should only get one possible distribution of people between cities. My thought is that for a more realistic scenario where you are concerned with cities with thousands or millions of people, you wouldn't be concerned with IDing each individual, but would just be interested in the expected population. If you were studying Alice, Bob, and Charlie, maybe you would want to know which city each winds up in, but otherwise I think you could get the same result by treating them... – Tyberius Dec 17 '18 at 12:23
  • @amd ...as unnamed populations of each cities and changing the populations using the $3\times3$ transition matrix. – Tyberius Dec 17 '18 at 12:24
  • 2
    @amd and Tyberius Just to close out the conversation. Key point is that the population process is stochastic. So if I was to simulate the movement of individuals $N$ between cities one at a time, I would get a different "actual" population in each city after $k$ iterations. That is just the nature of a stochastic process. But, we often characterize stochastic processes by their expected values of the variable. So the expected value of the population vector--the notation $E(s_k)$ is equal to the initial value $s_0$ times the $3x3$ city transition matrix. – krishnab Dec 17 '18 at 17:02
  • @amd I believe I'm starting to see what you are saying, that basically tracking configurations allows you to determine the probability distribution of all the states. However, I think with cities (and the case I'm most familiar with of distributions of molecules) the large number of individuals moving precludes looking at all the states and leads the expectation value to be almost the only state you encounter. – Tyberius Dec 17 '18 at 18:52
  • 1
    @Tyberius The one thing that I would add at this point is that, although you have an underlying Markov process that governs the population movement, the way that the expected (average) population distribution evolves is a stochastic process in only the most trivial sense: you know exactly what the next state will be. – amd Dec 17 '18 at 21:23