How to generate a Markov Matrix efficiently

A Markov Matrix is a square matrix,which have two features:

• All elements great than or equal to $0$(But I hope all element great than or equal to $0.1$)
• All the columns add up to $1$

I have a custom function for this

MarkovMatrix[dim_] :=
Module[{m}, Label[start];
m = Transpose[
Append[#, 1 - Total[#]] & /@
RandomReal[1, {dim, dim - 1}, WorkingPrecision -> 2]];
If[AllTrue[m, # > .1 &, 2], m, Goto[start]]; m]


Usage:

For example to generate a 4*4 matrix

MatrixForm[m = MarkovMatrix[4]]


But my MarkovMatrix is low efficiency function.Are there any better method can do this?

• Surely you mean the columns add up to $1$ – Feyre Jun 27 '16 at 18:18
• Transpose[Normalize[#, Total] & /@ RandomReal[1, {4, 4}]]? Anyway: the more common term is stochastic matrix. – J. M. is away Jun 27 '16 at 18:18
• @Feyre OMG.I make a typo.Thanks for your reminder. – yode Jun 27 '16 at 18:22
• @J.M. I have to say this is a beautiful solution.It deserve a answer but a comment.Another extra my request can you make all element great than or equal to $0.1$ with same elegant method? (Thanks for your term. :) – yode Jun 27 '16 at 18:29
• relevant: mathematica.stackexchange.com/questions/69707/… and mathematica.stackexchange.com/q/33652/2079. And for heavens sake never use Goto. – george2079 Jun 27 '16 at 19:59

Here's something even more compact than my proposal in the comments:

Standardize[RandomReal[1, {4, 4}], 0 &, Total]


If you must have a left stochastic matrix where all the entries should be greater than a set value, you can do rejection sampling: keep generating a matrix as long as the smallest value is smaller than the cutoff:

While[Min[sm = Standardize[RandomReal[1, {4, 4}], 0 &, Total]] < 0.1]; sm


If a doubly stochastic matrix is desired (that is, all columns and all rows sum to unity), some more trickery is necessary:

While[Min[dsm = FixedPoint[Standardize[Transpose[Standardize[#, 0 &, Total]],
0 &, Total] &, RandomReal[1, {4, 4}],
SameTest -> (Norm[#1 - Transpose[#2], "Frobenius"] <
1.*^-12 &)]] < 0.1]; dsm


I make no guarantees on the distribution followed by the matrices generated by either method.

• God,actually I want accept this answer right now.But as this counsel,I'll open it for some time. – yode Jun 27 '16 at 18:38

Assuming you want uniformly distributed n-dimensional probability vectors with a minimum value, I think you can use:

MarkovMatrix[n_, min_:0] := If[min n<1,
Transpose @ RandomPoint[Simplex[IdentityMatrix[n](1-min n)], n] + min,
$Failed ]  For example: MarkovMatrix[4, .1] // TeXForm $\left( \begin{array}{cccc} 0.378616 & 0.267013 & 0.416824 & 0.142604 \\ 0.14229 & 0.305494 & 0.177654 & 0.203273 \\ 0.231628 & 0.175853 & 0.154734 & 0.178135 \\ 0.247466 & 0.251641 & 0.250788 & 0.475988 \\ \end{array} \right)$• For earlier versions that do not have RandomPoint[], here is some equivalent code: MarkovMatrix[n_, min_: 0] := If[min n < 1, Transpose[((1 - min n) Append[#, 1 - Total[#]]) & /@ RandomVariate[DirichletDistribution[ConstantArray[1, n]], n]] + min,$Failed] – J. M. is away Jul 26 '17 at 14:09

Here is my idea

make[n_] := ConstantArray[0.1, {n, n}] + (
(1 - 0.1 n) #/Total[#, {2}] &[RandomReal[{0, 1}, {n, n}]])


Because of the minimum you specified for each entry, this works for $n<11$ only. Did you consider letting the minimum value dependent on $n$ in a decreasing manner?

• Thanks for your solution.And I have no that thinking,I just don't hope the element too tiny,which will make some troubles for my processing in following. – yode Jun 27 '16 at 18:34