Re: SingularValueDecomposition
- To: mathgroup at smc.vnet.net
- Subject: [mg119723] Re: SingularValueDecomposition
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Sat, 18 Jun 2011 19:57:20 -0400 (EDT)
- References: <201106181015.GAA15305@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
SingularValueDecomposition seems to HANG for that matrix, so my next try
was solving directly:
v = Array[x, 14]
{x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11],
x[12], x[13], x[14]}
soln = Quiet@Solve[Flatten@{Thread[v - m.v == 0], Plus @@ v == 1}, v]
soln[[1, All, -1]] // Total
{{x[2] -> 132/7967 + (6119 x[1])/7967, x[3] -> x[1],
x[4] -> 193/7967 + (5265 x[1])/7967,
x[5] -> 396/7967 + (2423 x[1])/7967,
x[6] -> 193/7967 + (5265 x[1])/7967,
x[7] -> 508/7967 + (855 x[1])/7967,
x[8] -> 802/7967 - (3261 x[1])/7967,
x[9] -> 508/7967 + (855 x[1])/7967,
x[10] -> 1047/7967 - (6691 x[1])/7967,
x[11] -> 1390/7967 - (11493 x[1])/7967,
x[12] -> 1047/7967 - (6691 x[1])/7967,
x[13] -> -(325/7967) + (12517 x[1])/7967,
x[14] -> 2076/7967 - (21097 x[1])/7967}}
1 - x[1]
x[1] has to be zero, and that doesn't seem like what we're looking for, if
all states communicate. (Do they?)
You can try something with
SingularValueDecomposition@N@m
(which doesn't hang), but this may also be instructive:
{values, vectors} = Eigensystem@m;
vectors = Normalize[#, Total] & /@ vectors;
p = Transpose@vectors;
d = DiagonalMatrix@values;
m.p == p.d
True
steady = vectors[[Flatten[Position[values, 1, 1], 1]]];
m.# == # & /@ steady
Total /@ steady
{True, True}
{1, 1}
With TWO unit eigenvalues, this markov chain is not of the sort you may
want, with a single steady state reached from any initial conditions.
p is also not invertible:
Det@p
0
Hence, we can't use the handy trick that
PowerMatrix[m, n] == p . d^n . Inverse@p
Good luck.
Bobby
On Sat, 18 Jun 2011 05:15:18 -0500, John Snyder <jsnyder at wi.rr.com> wrote:
> I read Jon McLoone's recent post on the WolframBlog concerning the
> solution of the drunken sailor's walk problem by using a Markov chain
> transition probability matrix. He mentions that it may also be possible
> to solve the problem using the SingularValueDecomposition function, but
> he does not illustrate this. I am trying to figure out how this could be
> done.
>
> Here is a simple "toy" example. Assume that I have the following Markov
> chain transition probability matrix m where each row sums to 1:
>
>
> m={{1/4,1/4,0,1/4,0,0,0,0,0,0,0,0,1/4,0},{1/4,1/4,1/4,0,1/4,0,0,0,0,0,0,0,0,0},{0,1/4,1/4,0,0,1/4,0,0,0,0,0,0,1/4,0},{0,0,0,1/4,1/4,0,1/4,0,0,0,0,0,1/4,0},{0,0,0,1/4,1/4,1/4,0,1/4,0,0,0,0,0,0},{0,0,0,0,1/4,1/4,0,0,1/4,0,0,0,1/4,0},{0,0,0,0,0,0,1/4,1/4,0,1/4,0,0,1/4,0},{0,0,0,0,0,0,1/4,1/4,1/4,0,1/4,0,0,0},{0,0,0,0,0,0,0,1/4,1/4,0,0,1/4,1/4,0},{0,0,0,0,0,0,0,0,0,1/4,1/4,0,1/4,1/4},{0,0,0,0,0,0,0,0,0,1/4,1/4,1/4,0,1/4},{0,0,0,0,0,0,0,0,0,0,1/4,1/4,1/4,1/4},{0,0,0,0,0,0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,1}};
>
> Assuming that I start in the position 2 (column 2 out of 3, in the first
> of 4 rows) I want to find the so-called "fixed point", the ultimate
> state density function, as the number of steps goes to infinity. I know
> that I can do this numerically using MatrixPower as follows (here is 100
> steps which appears to be more than enough in this case):
>
> In[19]:= MatrixPower[N[m],100][[2]]//Chop
> Out[19]= {0,0,0,0,0,0,0,0,0,0,0,0,0.809663,0.190337}
>
> I believe that it is also possible to get this same result by using the
> SingularValueDecomposition function, but I cannot figure out how to get
> this to work. Can someone please show me how to use
> SingularValueDecomposition to get the same answer to this question? I
> know there are other ways to solve this, but I am really interested in
> using SingularValueDecomposition in this case. Thanks.
>
>
--
DrMajorBob at yahoo.com
- References:
- SingularValueDecomposition
- From: John Snyder <jsnyder@wi.rr.com>
- SingularValueDecomposition