10
\$\begingroup\$

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 , so the shortest submission in bytes for each language is declared the winner for its language. No answer will be accepted
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman it seems like some earlier comments have been deleted, so this might be redundant, but reducible and periodic matrices are already excluded by "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", which I read as saying the input is guaranteed to converge to a unique solution. (i.e. the input matrix is guaranteed to be ergodic.) \$\endgroup\$ – Nathaniel Mar 8 '18 at 1:49
  • \$\begingroup\$ @Nathaniel That isn't quite true, as if the chain is reducible you can have a result (like for the identity matrix) that meets what you said but the chain it describes is not irreducible and therefore the input wouldn't be guaranteed to be ergodic (since it won't be positive recurrent). Guaranteeing ergodicity is what the OP wants, and I think they have that now, thanks to the additional constraint of all of the row values being identical. If you know a better way to constrain the input without needing to add an explanation of Markov chains, I'm sure HyperNeutrino would appreciate it! :) \$\endgroup\$ – FryAmTheEggman Mar 8 '18 at 2:06
  • 1
    \$\begingroup\$ @FryAmTheEggman ah, you're right, sorry. I was thinking of power iteration rather than raising the matrix to a power. (So by "unique solution" I meant "one that's independent of the starting point of the iteration process", but that's not relevant here.) I agree that the 'all rows are identical' condition does the job. I suppose the OP could just say "the Markov chain is guaranteed to be ergodic," which would satisfy people like us who are likely to worry about it! \$\endgroup\$ – Nathaniel Mar 8 '18 at 2:56
  • \$\begingroup\$ Actually, if B is a solution to BA = B, then so is cB for any scalar constant c. So a non-zero solution cannot be strictly unique, unless you somehow fix the scale. (Requiring B to be stochastic would do it.) Also, obviously, whether its the rows or the columns of B that are equal will depend on whether A is left or right stochastic. \$\endgroup\$ – Ilmari Karonen Mar 8 '18 at 3:07
  • 2
    \$\begingroup\$ For anyone else who never learned about matrices during Math-class in high school and how to multiply them: mathsisfun.com/algebra/matrix-multiplying.html. I had to look it up to understand what was being asked.. Maybe it's common knowledge elsewhere on Earth.. :S \$\endgroup\$ – Kevin Cruijssen Mar 8 '18 at 8:49
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I wonder why function(m){ while(any(m!=(m=m%*%m)))0 m} doesn't work. Numerical inaccuracies preventing the termination condition from triggering? \$\endgroup\$ – CodesInChaos Mar 8 '18 at 9:19
  • \$\begingroup\$ @CodesInChaos most likely it's a lack of precision. Switching to an arbitrary precision library doesn't help, either -- they either time out (Rmpfr) or fail (gmp) in the same manner, although I'm probably doing something wrong. \$\endgroup\$ – Giuseppe Mar 8 '18 at 16:22
  • \$\begingroup\$ @Giuseppe I guess the suggested approach is repeated squaring until no longer changes? (I can't read R) \$\endgroup\$ – user202729 Mar 8 '18 at 16:35
  • \$\begingroup\$ @user202729 yeah it is. R uses 64-bit floating point numbers and I know errors propogate pretty quickly. \$\endgroup\$ – Giuseppe Mar 8 '18 at 16:41
  • \$\begingroup\$ I think that algorithm is unstable. Jelly has the same problem too. (TODO prove this and find an alternative) \$\endgroup\$ – user202729 Mar 8 '18 at 16:45
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How does eigs always return the eigenvector corresponding to 1? My memory of markov chains is a bit fuzzy. \$\endgroup\$ – Giuseppe Mar 7 '18 at 19:24
  • \$\begingroup\$ 42 bytes \$\endgroup\$ – Giuseppe Mar 7 '18 at 19:32
  • \$\begingroup\$ @Giuseppe Because the matrix is stochastic, and a couple other things, its maximum eigenvalue is 1, and eigs returns starting from the largest eigenvalue. Also, thanks for the golf! \$\endgroup\$ – FryAmTheEggman Mar 7 '18 at 19:39
  • \$\begingroup\$ Ah, right. Markov chains are on my next exam but since it's for actuaries, some of the details are entirely missing. \$\endgroup\$ – Giuseppe Mar 7 '18 at 19:47
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 6 bytes

æ׳$ÐL

This is a full program.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog), 18 6 bytes

12 bytes saved thanks to @H.PWiz

+.×⍨⍣≡

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +.×⍨⍣≡ for 6 bytes. That is, square until nothing changes \$\endgroup\$ – H.PWiz Mar 7 '18 at 18:57
  • \$\begingroup\$ @H.PWiz I believe it is. I have no idea why I hadn't done it in the first place. Thanks! \$\endgroup\$ – Uriel Mar 7 '18 at 19:02
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Counting the compiler flag bytes, this results in 192 again. Included your suggestion nonetheless. \$\endgroup\$ – Jonathan Frech Jun 20 '18 at 21:08
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech Dec 18 '18 at 21:24
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Use dot instead of matmul :D \$\endgroup\$ – HyperNeutrino Mar 8 '18 at 4:01
  • \$\begingroup\$ Actually, take numpy arrays as input and do x=n@n :P tio.run/… \$\endgroup\$ – HyperNeutrino Mar 8 '18 at 4:03
  • \$\begingroup\$ 59 bytes \$\endgroup\$ – HyperNeutrino Mar 8 '18 at 4:04
  • \$\begingroup\$ Added back the f= at front because it is recursively called ;) \$\endgroup\$ – Shieru Asakoto Mar 8 '18 at 4:07
  • \$\begingroup\$ Oh yeah you're right :) good call! \$\endgroup\$ – HyperNeutrino Mar 8 '18 at 4:09
2
\$\begingroup\$

Java 8, 356 bytes

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

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,j,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=0;i<l;i++)     //   Inner loop over the rows
      for(j=0;j<l;j++)   //    Inner loop over the columns
        for(k=0;k<l      //     Inner loop to multiply
            ;            //       After every iteration:
             t[i][j]=(q!=null?q:q.ZERO).add(
                         //        Sum the value at position [i,j] in matrix `t` with:
               m[i][k]   //         [i,k] in matrix `m`,
               .multiply(m[k++][j]));
                         //         multiplied with [k,j] in matrix `m`
          q=t[i][j];     //      Set the value at position [i,j] to temp `q`
    for(f=i=0;           //   Set the flag-integer to 0
        i<l;i++)         //   Loop over the rows
      for(j=0;j<l;)      //    Inner loop over the columns
        if(!t[i][j].setScale(9,x.UP).equals(m[i][j++].setScale(9,x.UP)))
                         //     If any value in matrices `t` and `m` aren't the same
          f=1;}          //      Set the flag-integer to 1 again
  return m;}             //  Return the modified input-matrix `m` as our result
\$\endgroup\$
  • \$\begingroup\$ Why is the main function so verbose? \$\endgroup\$ – user202729 Mar 8 '18 at 16:31
  • \$\begingroup\$ @user202729 Because float/double don't have the proper floating point precision, java.math.BigDecimal should be used instead. And instead of simply +-*/, BigDecimals use .add(...), .subtract(...), .multiply(...), .divide(...). So something as simply as 7/10 becomes new BigDecimal(7).divide(new BigDecimal(10)). In addition, the ,scale,RoundingMode in the divide are required for values with 'infinite' decimal values (like 1/3 being 0.333...). The main method can of course be golfed, but I didn't bother when I did a search&replace to convert the floats to BigDecimals. \$\endgroup\$ – Kevin Cruijssen Mar 8 '18 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.