Jump to content

Matrix/Stochastic/Introduction/Section

From Wikiversity


A real square matrix

M=(aij)1≤i,j≤n

is called a column stochastic matrix if all entries

aij≥0,

and every column sum (that is, for every j), is

∑i=1naij=1.

The basic interpretation for a column stochastic matrix is the following: There is a set of n possible places, spots, positions, vertices in a network, web pages, etc., where someone or something can be with a certain probability (a distribution, a weighting). Such a distribution is described by an n-tuple (v1v2⋮vn) with real non-negative numbers vi satisfying ∑i=1nvi=1. This is also called a distribution vector. A column stochastic matrix describes the transition probability in the given network in a certain time segment. The entry aij is the probability that an object being at the vertex j (a visitor of the web page j) moves to the position i (goes to the webpage i). The j-th standard vector corresponds to the distribution where everything is in the vertex j.The j-th column of the matrix describes the image of this standard vector under the matrix. In general, for a given distribution v, applying the matrix computes the image distribution Mv; see exercise. A natural question is whether there are distributions that are stationary (stationary distribution, or fixed distribution, or eigendistribution), that is, they are transformed to themselves, or whether there exist periodic distributions, or whether there exist limit distributions, and how to compute them.


A column stochastic 2×2-matrix has the form

(p1p21−p11−p2)

wit

0≤p1,p2≤1.

The characteristic polynomial is

(X−p1)(X−1+p2)−(1−p1)p2=X2+(p2−p1−1)X+p1(1−p2)−p2(1−p1)=X2+(p2−p1−1)X+p1−p2=(X−1)(X+p2−p1).

Eigenvalues are 1 and p1−p2. A stationary distribution is (exclude the cases p1=1 and p2=0 for the following computation) given by (p2p2−p1+11−p1p2−p1+1), because of

(p1p21−p11−p2)(p2p2−p1+11−p1p2−p1+1)=(p1p2p2−p1+1+p21−p1p2−p1+1(1−p1)p2p2−p1+1+(1−p2)1−p1p2−p1+1)=(p1p2+p2(1−p1)p2−p1+1(1−p1)p2+(1−p2)(1−p1)p2−p1+1)=(p2p2−p1+11−p1p2−p1+1).


The column stochastic 2×2-matrix

(0110)

transforms the distribution (p1−p) into the distribution (1−pp). The contribution (1212) is transformed to itself, that is, it is a stationary distribution. The distribution (10) is transformed into (01), and vice versa. It is a periodic distribution, the period length is 2.


The column stochastic n×n-matrix

(11⋯100⋯0⋮⋮⋱⋮00⋯0)

transforms the distribution (v1⋮vn) into the distribution

(11⋯100⋯0⋮⋮⋱⋮00⋯0)(v1v2⋮vn)=(∑i=1nvi0⋮0)=(10⋮0).

The first standard vector is an eigenvector of the eigenvalue 1; every other standard vector, and in fact every distribution vector, is transformed into the first standard vector. The kernel is generated by the vectors e1−ej, j≥2, and does not contain any distribution vector.


Let N be a network (a "directed graph“), consisting in a set K of vertices, and a set of directed edges, which can exist between the vertices. For example, K is the set of all web pages, and there exists an arrow from j∈K to i∈K, if the web page j has a link to the web page i. The linking structure can be expressed by the adjacency matrix

A=(aij),

where

aij:={1,there exists a link from j to i,0, else,,

or by the column stochastic matrix

B=(bij),

where

bij=aijdj,

and dj is the number of links starting at the vertex j. This division ensures that the column sum equals 1 (we suppose that there is at least one link starting at any vertex).

The adjacency matrix, and the column stochastic version of the adjacency matrix of the graph on the right (where we add always self links) are

(1000011000101001111010111) and (1500001512000150130015121312015013121).