8
votes
0answers
192 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
0
votes
0answers
30 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 ...
0
votes
0answers
112 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
2
votes
1answer
49 views

Proof that stochastic process on infinite graph ends in finite step.

Infinite Graph Let $G$ be an infinite graph that is constructed this way: start with two unconnected nodes $v_1$ and $u_1$. We call this "level 1". Create two more unconnected nodes $v_2$ and $u_2$. ...
3
votes
1answer
79 views

Cheeger's inequality: Markov chain version is a special case of graph version?

For a Markov chain the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a ...
0
votes
1answer
211 views

Random-Tree simulation

I wanna simulate a Galton-Watson Tree to a maximum of n generation given a reproduction law P. I use Maple but I am unable to create the edges of the tree whenever there are more than two vertices in ...
3
votes
0answers
193 views

Cover time and intersection time for lazy random walks on graphs

Consider a simple lazy random walk on an $n$-vertex undirected, connected graph: this is the Markov chain which transitions from $i$ to $j$ with probability $p_{ij}=1/(2d(i))$ where $d(i)$ is the ...
2
votes
0answers
97 views

Cover times and hitting times of random walks, once again.

This is a followup to my question Cover times and hitting times of random walks. Consider a random walk on an undirected graph with $n$ vertices which, at each step, moves to a uniformly random ...
9
votes
4answers
491 views

Probability of global epidemic

Consider $\mathbb{Z}^2$ as a graph, where each node has four neighbours. 4 signals are emitted from $(0,0)$ in each of four directions (1 per direction) . A node that receives one signal (or more) at ...
0
votes
1answer
100 views

Random Walks and Jumps

I am trying to understand why Random Walks' and Random Jumps', on a graph, transition matrix are also stochastic matrix. A stochastic matrix is a matrix the values of each row add up to 1 and no ...
1
vote
1answer
70 views

Degree of girraphs

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent. The random walk on the square grid returns to the origin with probability 1, and for the cubic grid ...
6
votes
2answers
147 views

How long does it take for every node of a graph to become infected?

Consider the following stochastic process. We begin with an undirected graph on $n$ vertices, exactly one of which is ''infected.'' Now at every time step, each infected node infects one of its ...