# How to generate Markov chains with given length and end state?

Suppose I have a discrete Markov process with states called 'Alice', 'Bob', 'Charlie', 'Daryl', 'Edith', and 'Fiona' and a given transition matrix. How can I get Mathematica to generate a finite Markov chain of given length, say 8, that ends with a given state, say 'Daryl'?

I would like the output formatted simply like this:

Bob, Daryl, Charlie, Alice, Alice, Fiona, Bob, Daryl.

Edit: of course there's a trivial solution: generate any Markov chain of length 7 and then append Daryl. But that's not what I mean. The chain has to arise genuinely from the probabilities.

• If your process is reversible, then you can construct the chains starting from the end. Have you checked if it is? – Roman Jul 11 '19 at 3:21

A random transition matrix for a 6-state Markov process:

SeedRandom;
T = Normalize[#, Total] & /@ RandomReal[{0, 1}, {6, 6}];


Calculate the probabilities of the six states at equilibrium:

p = Normalize[First@NullSpace[Transpose[T] - IdentityMatrix], Total]
(*    {0.221926, 0.16537, 0.0993953, 0.168152, 0.158438, 0.186718}    *)


Set up a Markov process that starts at equilibrium (or change this to start at a specific state):

P = DiscreteMarkovProcess[p, T];


Sample 100 length-8 Markov chains and pick those that end in state 4:

With[{M = 100},
Select[Normal[RandomFunction[P, {0, 7}, M]], #[[-1, 2]] == 4 &][[All,All,2]]]


{{2, 5, 3, 4, 6, 4, 4, 4}, {3, 6, 5, 1, 3, 6, 6, 4}, {1, 2, 5, 3, 3, 2, 4, 4}, {6, 5, 3, 3, 5, 5, 4, 4}, {1, 1, 3, 3, 2, 3, 3, 4}, {4, 1, 1, 2, 5, 6, 6, 4}, {6, 4, 5, 3, 2, 5, 5, 4}, {6, 1, 6, 4, 1, 1, 1, 4}, {5, 1, 1, 3, 5, 5, 3, 4}, {1, 6, 1, 6, 1, 6, 6, 4}, {1, 6, 6, 3, 1, 1, 6, 4}, {1, 6, 1, 6, 1, 1, 4, 4}, {1, 1, 1, 1, 2, 2, 4, 4}, {6, 6, 1, 1, 4, 5, 2, 4}, {2, 1, 6, 3, 2, 2, 5, 4}, {4, 6, 1, 4, 6, 1, 2, 4}, {6, 4, 2, 3, 6, 1, 2, 4}}

• Thank you so much for this! – Kim Fierens Jul 11 '19 at 19:25