How do you calculate a transition matrix from an adjacency matrix?

For a weighted adjacency matrix, divide each entry in a row by the sum of that row. The resulting row contains the probabilities of moving from the corresponding vertex to each possible next vertex.

Does every random walk converge to a stationary distribution?

A finite irreducible Markov chain has a unique stationary distribution. If it is also aperiodic, the distribution from any initial state converges to that stationary distribution. Periodic chains can have stationary distributions without their step-by-step distributions converging.

Random Walk Matrix Simulator - Transition Matrices and Stationary Distributions

Interactive simulator

Build and Simulate a Random Walk

Enter a weighted adjacency matrix. Each row represents the current vertex, and each column represents a possible next vertex.

Weighted adjacency matrix

Enter a square matrix with nonnegative weights. Use commas or spaces between entries and one line per row. Matrix size: 2×2 to 8×8.

Example network

Starting vertex

Probability steps

Random walk steps

Number of walks

Initial distribution

What you can explore

Weighted adjacency matrices.
Row-stochastic transition matrices.
Probability distribution after each step.
Individual random walk trajectories.
Empirical vertex visit frequencies.
Approximate stationary distributions.
Graph structure and long-term behaviour.

\[ P_{ij}=\frac{w_{ij}}{\sum_j w_{ij}} \] \[ \boldsymbol{\pi}_{k+1} =\boldsymbol{\pi}_kP \]

Rows represent current vertices; columns represent destination vertices. A row with no outgoing edges is treated as an absorbing state with a self-loop.

Numerical results

Random Walk Analysis

Analyzed

Number of vertices

Transition steps

Total edge weight

Stationary residual

Long-run behaviour

Network visualization

Vertices represent states. Connections represent possible transitions. Directed edges are shown with arrows.

The graph is a visual representation of the entered adjacency matrix. Edge weights determine transition probabilities.

Adjacency and transition matrices

Initial probability distribution

Probability evolution

The distribution at step k is calculated using \(\boldsymbol{\pi}_k=\boldsymbol{\pi}_0P^k\).

Each line shows the probability of occupying one vertex after successive steps.

Distribution history

Approximate stationary distribution

The simulator uses Cesàro averages of successive distributions to estimate a stationary probability vector. This method can also produce a stationary estimate for periodic chains.

Random walk simulation

A sample trajectory is generated by randomly selecting the next vertex according to the transition probabilities.

Sample walk path

Monte Carlo visit frequencies

Multiple independent walks are used to estimate the proportion of time spent at each vertex. The first visit at time zero is included in each walk.

Vertex	Visits	Empirical frequency	Stationary estimate

Step-by-step mathematical explanation

Mathematical foundation

What Is a Random Walk?

A random walk is a process in which an object moves from one state to another according to specified probabilities. In graph theory, the states are vertices and possible movements are edges.

At every step, the current vertex determines the probability of moving to each possible destination. The next movement is selected randomly according to these probabilities.

\[ X_0\rightarrow X_1\rightarrow X_2\rightarrow\cdots \]

A random walk on a finite graph can be represented as a finite-state Markov chain. Its transition matrix contains all one-step movement probabilities.

From graph to matrix

Adjacency Matrix and Transition Matrix

An adjacency matrix records the connections between vertices. For a weighted graph, the entry \(w_{ij}\) represents the weight of the connection from vertex i to vertex j.

\[ W= \begin{bmatrix} w_{11}&w_{12}&\cdots&w_{1n}\\ w_{21}&w_{22}&\cdots&w_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ w_{n1}&w_{n2}&\cdots&w_{nn} \end{bmatrix} \]

To construct a transition matrix, divide each row by its total outgoing weight:

\[ \boxed{P_{ij}=\frac{w_{ij}}{\sum_{j=1}^{n}w_{ij}}} \]

This produces a row-stochastic matrix: every entry is nonnegative and every row sums to one.

\[ \boxed{\sum_{j=1}^{n}P_{ij}=1} \]

If a vertex has no outgoing edges, the simulator treats it as an absorbing state by assigning a probability of one to remain there.

Probability evolution

How a Random Walk Uses Matrix Multiplication

Let the initial probability distribution be a row vector:

\[ \boldsymbol{\pi}_0= \begin{bmatrix} p_1&p_2&\cdots&p_n \end{bmatrix} \]

The probability distribution after one step is obtained by multiplying the initial distribution by the transition matrix:

\[ \boxed{\boldsymbol{\pi}_1=\boldsymbol{\pi}_0P} \]

After two steps:

\[ \boldsymbol{\pi}_2=\boldsymbol{\pi}_0P^2 \]

More generally, after k steps:

\[ \boxed{\boldsymbol{\pi}_k=\boldsymbol{\pi}_0P^k} \]

The matrix power \(P^k\) contains the probabilities of moving from each starting vertex to each destination vertex in exactly k steps.

Long-term behaviour

Stationary Distribution of a Random Walk

A stationary distribution is a probability vector that remains unchanged after one transition. It satisfies:

\[ \boxed{\boldsymbol{\pi}P=\boldsymbol{\pi}} \]

It is therefore a left eigenvector of the transition matrix corresponding to eigenvalue one.

Important distinction: A stationary distribution is not necessarily the limiting distribution from every initial state. For a finite irreducible and aperiodic chain, the stationary distribution is unique and the distribution converges to it from any starting distribution. Periodic chains can have a stationary distribution while their step-by-step probabilities continue to oscillate.

A special result for undirected graphs

Stationary Distribution and Vertex Degree

For a finite connected undirected weighted graph, the stationary distribution of the ordinary random walk has a particularly simple form.

The weighted degree of vertex i is the sum of the weights of its incident edges:

\[ d_i=\sum_j w_{ij} \]

The stationary probability of vertex i is:

\[ \boxed{\pi_i=\frac{d_i}{\sum_j d_j}} \]

Vertices with more total incident edge weight receive more stationary probability. For an unweighted undirected graph, this reduces to probability proportional to the ordinary vertex degree.

This formula assumes a connected undirected graph with positive degree at every vertex. The simulator uses the general iterative stationary-distribution estimate for directed and disconnected networks.

Applications

Where Are Random Walk Matrices Used?

1. Search engines and PageRank

Random-surfer models use transition probabilities between web pages to estimate their relative importance.

2. Network analysis

Random walks help study connectivity, centrality, movement and information flow through networks.

3. Physics and statistical mechanics

Random walks are used to model diffusion, particle movement and stochastic processes.

4. Machine learning

Graph-based learning methods use random walks to explore relationships and generate node representations.

5. Biology and chemistry

Random walks can model movement through molecular networks, biological pathways and interaction graphs.

6. Transportation systems

Transition matrices can describe probabilistic movement between stations, locations and transport connections.

Frequently asked questions

Random Walk Matrix FAQs

1. What is a random walk matrix?

A random walk matrix is usually a transition matrix whose entries represent the probabilities of moving between states or vertices in a graph.

2. How is a transition matrix calculated?

Divide each adjacency-matrix row by its sum. Every nonzero row then sums to one, giving the probability of selecting each possible destination.

3. What is a stationary distribution?

It is a probability vector that remains unchanged after multiplication by the transition matrix: πP = π.

4. What is the stationary distribution of an undirected graph?

For a finite connected undirected weighted graph, each vertex's stationary probability is proportional to its weighted degree.

5. Does every random walk converge?

Not necessarily. A finite irreducible chain has a unique stationary distribution, but convergence from every initial distribution additionally requires aperiodicity.

6. Why can a random walk oscillate?

Periodic network structures can force the walk to alternate between groups of vertices. A walk on a bipartite graph without self-loops is a common example.

7. What is the difference between a random walk and a Markov chain?

A random walk is a particular type of Markov chain in which transitions are typically associated with movement through a graph or network. A Markov chain is the broader mathematical framework for systems with probabilistic state transitions.

8. What does a row-stochastic matrix mean?

It is a matrix with nonnegative entries in which every row sums to one. Each row can therefore represent a probability distribution over possible next states.

9. Can adjacency matrices contain weights?

Yes. Weighted adjacency matrices represent stronger or weaker connections. The transition probability is proportional to the corresponding edge weight.

10. What is the difference between a stationary distribution and visit frequency?

A stationary distribution is a mathematical probability vector satisfying πP = π. Visit frequency is an empirical estimate obtained by observing simulated walks. The empirical frequency approaches the stationary distribution under suitable long-run conditions.

Continue learning

Related Matrix Calculators

Explore other interactive tools for Markov chains, matrix powers, eigenvalues and numerical methods.