Convergence of a Markov Process

Question

Challenge

Given a left- or right-stochastic matrix where the limit as x approaches infinity of the matrix to the power of x approaches a matrix with all finite values, return the matrix to which the matrix converges. Basically, you want to keep multiplying the matrix by itself until the result no longer changes.

Test Cases

[[7/10, 4/10], [3/10, 6/10]] -> [[4/7, 4/7], [3/7, 3/7]]
[[2/5, 4/5], [3/5, 1/5]] -> [[4/7, 4/7], [3/7, 3/7]]
[[1/2, 1/2], [1/2, 1/2]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/3, 2/3], [2/3, 1/3]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/10, 2/10, 3/10], [4/10, 5/10, 6/10], [5/10, 3/10, 1/10]] -> [[27/130, 27/130, 27/130], [66/130, 66/130, 66/130], [37/130, 37/130, 37/130]]
[[1/7, 2/7, 4/7], [2/7, 4/7, 1/7], [4/7, 1/7, 2/7]] -> [[1/3, 1/3, 1/3], [1/3, 1/3, 1/3], [1/3, 1/3, 1/3]]

Rules

• Standard Loopholes Apply
• You may choose whether you want a right- or a left-stochastic matrix
• You may use any reasonable number type, such as floats, rationals, infinite precision decimals, etc
• This is code-golf, so the shortest submission in bytes for each language is declared the winner for its language. No answer will be accepted

Answer 1

R,  44  43 bytes

function(m){X=m
while(any(X-(X=X%*%m)))0
X}

Try it online!

Just keeps multiplying until it finds a fixed matrix. Apparently X!=(X=X%*%m) does the comparison, then reassigns X, so that's neat.

Thanks to @Vlo for shaving off a byte; even though crossed out 44 is still regular 44.

Answer 2

Octave, 45 42 35 bytes

@(A)([v,~]=eigs(A,1))/sum(v)*any(A)

Try it online!

Saved 3 bytes thanks to Giuseppe, and 7 more thanks to Luis Mendo!

This uses that the eigenvector corresponding to the eigenvalue 1 (also the maximum eigenvalue) is the column vector that is repeated for each value of the limiting matrix. We have to normalise the vector to have sum 1 for it to be stochastic, then we simply repeat it to fill out the matrix. I'm not too well versed in golfing Octave, but I haven't been able to find a functional way to do repeated multiplication, and a full program seems like it will always be longer than this.

We can use any(A) since from the restrictions we know that the matrix must describe an irreducible Markov chain, and so each state must be reachable from the other states. Therefore at least one value in each column must be non-zero.

Answer 3

Wolfram Language (Mathematica), 14 bytes

Output floats:

N@#//.x_:>x.#&

Try it online!

---

Wolfram Language (Mathematica), 30 bytes

Output fractions:

Limit[#~MatrixPower~n,n->∞]&

Try it online!

Answer 4

Jelly, 6 bytes

æ׳$ÐL

This is a full program.

Try it online!

Answer 5

APL (Dyalog), 18 6 bytes

12 bytes saved thanks to @H.PWiz

+.×⍨⍣≡

Try it online!

Answer 6

C (gcc), 207 192 190 181 176 bytes + 2 flag bytes -lm

• Saved fifteen seventeen twenty-two bytes thanks to ceilingcat.
• Saved nine bytes; removing return A;.

float*f(A,l,k,j)float*A;{for(float B[l*l],S,M=0,m=1;fabs(m-M)>1e-7;wmemcpy(A,B,l*l))for(M=m,m=0,k=l*l;k--;)for(S=j=0;j<l;)m=fmax(m,fdim(A[k],B[k]=S+=A[k/l*l+j]*A[k%l+j++*l]));}

Try it online!

Answer 7

k/q, 10 bytes

k/q because the program is identical in both languages. The code is really just idiomatic k/q.

{$[x]/[x]}

Explanation

{..} is out lambda syntax, with x as an implicit parameter

$[x] has $ as the binary matrix multiplication operator, providing only one parameters creates a unary operator that left multiplies by the Markov Matrix

/[x] applies the left multiplication until convergence, starting with x itself.

Answer 8

Python 3, 75 61 bytes

f=lambda n:n if allclose(n@n,n)else f(n@n)
from numpy import*

Try it online!

In test cases there are float inaccuracies, so the values may differ by a bit from the exact fractions.

PS. numpy.allclose() is used because numpy.array_equal() is longer and prone to float inaccuracies.

-14 bytes Thanks HyperNeutrino ;) Oh yes I forgot the @ operator ;P

Answer 9

Java 8, 356 339 bytes

import java.math.*;m->{BigDecimal t[][],q;RoundingMode x=null;for(int l=m.length,f=1,i,k;f>0;m=t.clone()){for(t=new BigDecimal[l][l],i=l*l;i-->0;)for(f=k=0;k<l;t[i/l][i%l]=(q!=null?q:q.ZERO).add(m[i/l][k].multiply(m[k++][i%l])))q=t[i/l][i%l];for(;++i<l*l;)f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?f:1;}return m;}

-17 bytes thanks to @ceilingcat.

Definitely not the right language.. Damn floating point precision..

Explanation:

Try it online.

import java.math.*;     // Required import for BigDecimal and RoundingMode
m->{                    // Method with BigDecimal-matrix as both parameter and return-type
  BigDecimal t[][],q;   //  Temp BigDecimal-matrix
  RoundingMode x=null;  //  Static RoundingMode value to reduce bytes
  for(int l=m.length,   //  The size of the input-matrix
          f=1,          //  Flag-integer, starting at 1
          i,k;          //  Index-integers
      f>0;              //  Loop as long as the flag-integer is still 1
      m=t.clone()){     //    After every iteration: replace matrix `m` with `t`
    for(t=new BigDecimal[l][l],
                        //   Reset matrix `t`
        i=l*l;i-->0;)   //   Inner loop over the rows and columns
      for(f=k=0;        //    Set the flag-integer to 0
          k<l           //    Inner loop to multiply
          ;             //      After every iteration:
           t[i/l][i%l]=(q!=null?q:q.ZERO).add(
                        //       Sum the value at the current cell in matrix `t` with:
             m[i/l][k]  //        the same row, but column `k` of matrix `m`,
             .multiply(m[k++][i%l])))
                        //        multiplied with the same column, but row `k` of matrix `m`
        q=t[i/l][i%l];  //     Set temp `q` to the value of the current cell of `t`
    for(;++i<l*l;)      //   Loop over the rows and columns again
      f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?
                        //    If any value in matrices `t` and `m` are the same:
         f              //     Leave the flag-integer unchanged
        :               //    Else (they aren't the same):
         1;}            //     Set the flag-integer to 1 again
  return m;}            //  Return the modified input-matrix `m` as our result