1
vote
1answer
27 views

Steps in a proof from Spectral Graph Theory by Fan Chung

On page 15 of Spectral Graph Theory by Fan Chung, http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf, before eq (1.14) is the step, $\displaystyle || \sum_{i\neq 0} (1-\lambda_i)^s a_i \phi_i ...
1
vote
1answer
65 views

Markov Chain with Memory

One of the defining characteristics of a Markov Chain is that it is memoryless: the next state depends only on the current state, and not on the set of preceding states. I'm looking for a ...
1
vote
2answers
69 views

Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
5
votes
1answer
98 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
0
votes
1answer
62 views

Ergodicity of this Markov Chain

I was recently involved in a debate with a friend over the following graph, and whether it is ergodic or not. In the following diagram, each edge has a strictly positive probability of being travelled ...
1
vote
0answers
74 views

Expected distance traversed between 2 vertices on probabilistic graph

Let $V = \{1,2,3,...,N\}$ be the vertex set of a graph. Let $d(i,j)>=0$ represent the $(i,j)$ vertex distance between vertices $i$ and $j$, $i \in V, j \in V$. Now, define a non-negative number ...
0
votes
0answers
43 views

When random walk Markov matrix of the graph is normal?

I'm considering random walk on undirected graph $G$. At every time step, walker moves to a random neighbour, with all neighbours being equally likely. With adjacency matrix $A$ the random walk Markov ...
2
votes
2answers
319 views

The second largest eigenvalue for Perron-Frobenius matrix

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix. My question: Is there any estimation of the difference between the first and ...
2
votes
0answers
271 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
4
votes
2answers
426 views

Random walk on lollipop graph

Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
-1
votes
1answer
135 views

Stationary distribution for different types of graph

This is a follow-up questions to posts: Stationary distribution for directed graph Stationary distribution for different types of graph The definition of stationary distribution in ...
0
votes
1answer
631 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
1
vote
1answer
68 views

spectral gap of the graph / Markov chain

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
1
vote
1answer
125 views

Gradient of a function on the vertices of a graph

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$ ...
0
votes
2answers
490 views

Why is every irreducible matrix with period 1 primitive?

In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried ...
1
vote
0answers
45 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
1
vote
1answer
306 views

Transition matrix

I have a directed graph $G_1$. I extract its transition matrix $T_1$. Now I also have directed graph $G_2$, which is equal to $G_1$ with inverted edges. If I get its transition matrix $T_2$, what is ...