6
votes
1answer
130 views

A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation. A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
0
votes
3answers
405 views

Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...
1
vote
1answer
225 views

Equivalent Markov Random Fields

Hi, Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ? Thanks!
1
vote
1answer
192 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
172 views

Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...
4
votes
1answer
269 views

Combinatorial descriptions of the stationary distribution of a Markov chain

When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible. ...
1
vote
1answer
237 views

Connectivity of a graph with fixed number of vertices and edges

Hi, first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge. So this is the ...
2
votes
2answers
511 views

probability distribution of hitting nodes on a finite graph random walk

Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...
10
votes
1answer
614 views

Different uses of the word “ergodic”

There appear to be two definitions of the word ergodic. The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ...
0
votes
1answer
94 views

how to find a sequence of digits in base b such that each consecutive block of size k appears exactly once?

My question is most precisely stated in the title. As an example, if we consider base 10, and k=4, then I am asking, is it possible to have a sequence of length 10^4 + 3, such that each 4 digit number ...