1
vote
0answers
18 views

Contraction of Random walk on graph

I'm working on something involving random walks on graphs, and I came across the following operator : we are given a graph, and a transition matrix M of a markov chain which corresponds to the graph ...
5
votes
0answers
76 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
59 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 ...
0
votes
0answers
65 views

Determine if graph is aperiodic

I have two questions: (1) is there are fast (polynomial time) way of determining if a graph is aperiodic? (2) does adding in self-loops in a connected graph guarantee aperiodicity? (If it matters ...
0
votes
0answers
35 views

How to perform a stochastic search of the locality of a node in a network?

In a graph that may be a random graph (ER graph), scale free network, etc. I would like to obtain a distribution of the locality of the nodes surrounding a ...
1
vote
0answers
69 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
41 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
288 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 ...
1
vote
0answers
254 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
393 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
134 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
518 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
65 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
462 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
303 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 ...