$M = \begin{bmatrix}0.5 & 0.2 & 0.3\\0.2 & 0.7 & 0.1\\0.75 & 0.15 & 0.1\end{bmatrix}$

فرمول کلی

$s M = s$

حالت بعدی برابر با ضرب حالت اولی با ماتریس احتمال‌های جابجایی است

\begin{equation*} s' = s M \\ s^2 = (s M) M \\ \text{ } \\ \text{ } \\ \text{or: } \\ s^n = s M^2 \\ \dots \\ \text{______________} \\ s^n = s M^n \\ \end{equation*}

آیا می‌توانیم حالت نهایی (حالت تعادل) را به شیوه‌ای با محاسبات کمتر حساب کنیم؟

Eigenvalue decomposition:

\begin{equation*} M = V \Lambda V^{-1} \end{equation*}

سایر decompositionها:

i/j/..., fourier, wavelet, SVD, ...

Eigenvalue decomposition:

\begin{equation*} lim_{n\to\infty}M^n = (V \Lambda V^{-1}) * (V \Lambda V^{-1}) \\ \dots \\ \dots \\ = V \Lambda^n V^{-1} \end{equation*}

ماتریس تصادفی / Stochastic Matrix

In [39]:
import numpy as np
M = np.mat([[0.1, 0.2, 0.7], [0.4, 0.3, 0.3], [0.5, 0.1, 0.4]])
M.
Out[39]:
matrix([[ 0.1,  0.2,  0.7],
        [ 0.4,  0.3,  0.3],
        [ 0.5,  0.1,  0.4]])

خاصیت: جمع هر سطر یک است

تابع eig

V: Eigen vectors

D: Eigen values چیده شده در ماتریس قطری

که در ماتریس تصادفی حتماً یکی از آیگن‌ها ۱ خواهد بود

In [41]:
D, V = np.linalg.eig(M)
D = np.diag(D)
D, V
Out[41]:
(array([[ 1.        ,  0.        ,  0.        ],
        [ 0.        , -0.38284271,  0.        ],
        [ 0.        ,  0.        ,  0.18284271]]),
 matrix([[-0.57735027, -0.82720305,  0.06909714],
         [-0.57735027,  0.26745662, -0.95703598],
         [-0.57735027,  0.49416806,  0.28161627]]))
In [55]:
V * D * (V ** -1) # or V * D / V
Out[55]:
matrix([[ 0.1,  0.2,  0.7],
        [ 0.4,  0.3,  0.3],
        [ 0.5,  0.1,  0.4]])

نکته جالب پردازشی برای ماتریس تصادفی: فقط یکی باقی خواهد ماند بقیه به صفر متمایل می‌شوند

In [45]:
D ** 100
Out[45]:
array([[  1.00000000e+00,   0.00000000e+00,   0.00000000e+00],
       [  0.00000000e+00,   2.00464954e-42,   0.00000000e+00],
       [  0.00000000e+00,   0.00000000e+00,   1.61348727e-74]])

طبق آنچه گفته شد، نتیجه دو عبارت زیر برابر خواهد بود

In [46]:
V * (D ** 100) * (V ** -1)
Out[46]:
matrix([[ 0.34513274,  0.16814159,  0.48672566],
        [ 0.34513274,  0.16814159,  0.48672566],
        [ 0.34513274,  0.16814159,  0.48672566]])
In [47]:
M ** 100
Out[47]:
matrix([[ 0.34513274,  0.16814159,  0.48672566],
        [ 0.34513274,  0.16814159,  0.48672566],
        [ 0.34513274,  0.16814159,  0.48672566]])

هزینهٔ پردازشی عبارت اول به مرتب کمتر است

خاصیت دیگر: ضرب هر برداری در ماتریس نهایی نتیجهٔ یکسان (حالت تعادل) می‌دهد

Av=λv

In [52]:
[0.1, 0.7, 0.2] * (M ** 100)
Out[52]:
matrix([[ 0.34513274,  0.16814159,  0.48672566]])

کاربرد؟

  • eigenvalue centrality
  • pagerank (work differently, should be interpreted on random walk)