All Questions

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps). Assume that $\Gamma$ is bi-regular, that is ...

I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...

I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees. Consider a 1D random walk on the integers, starting at the origin, ...

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which start at $0$ stay in $[0,n]\cap\mathbb{Z}$ ...

Consider a large, probably sparse graph with Markovian random walkers on it. Define the discovery time as the expected time to first reach a vertex by random walk from a uniform start. Are there ...