# Tagged Questions

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$ ...
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...