# Questions tagged [random-walks]

The tag has no usage guidance.

491 questions
Filter by
Sorted by
Tagged with
57 views

66 views

### Random walks on randomly evolving graphs

I am interested in analyzing a random walk on a growing tree with vertices labelled on a tree with following properties. The number of nodes at depth $k$ is a an exponential function of $k$. One can ...
73 views

### Convergence bounds for ergodic random walk

We are given a simple connected graph $G(V,E)$, where $V$ and $E$ denote the vertex and edge sets respectively. Let $G'(V,E')$ be the graph generated by $G$ by adding one self-loop edge for each ...
1 vote
86 views

### Phase space Brownian bridge

I understand the concept of the 1 dimensional Brownian bridge with the form of: $$dx_t=\frac{-1}{1-t}x_t \, dt + dw_t$$ s.t. $x_0=0$ and $x_1=0$ where $dw_t$ is a Wiener process. I am thinking about ...
70 views

### Reference request: $\mathbb{E}|X_t| \to \infty$ as $t \to \infty$ when $\{X_t\}_{t\geq 0}$ is a continuous-time (symmetric) random walk

Let $\{X_t\}_{t\geq 0}$ be a one dimensional continuous-time (symmetric) random walk on $\mathbb Z$ defined via $$X_t = X_0 + \sum_{i=1}^{N_t} Y_i,$$ where $X_0 \in \mathbb{Z}_+$ is a non-negative ...
273 views

### Probabilistic problem on random spanning trees

Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
309 views

212 views

### Is there something like a "self-avoiding Markov chain" on a continuous space?

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants. However, as far as I can see they are ...
103 views

### Asymptotic expansion for the number of self-avoiding random walks

This question is cross-posted from https://math.stackexchange.com/questions/4580314/asymptotic-expansion-for-the-number-of-self-avoiding-random-walks. Let $c_n$ be the number of self-avoiding random ...
195 views

### Origin of the term "connective constant"

Let $G$ be a vertex-transitive locally finite graph and $c_n$ the number of self-avoiding walks in $G$ starting from some fixed vertex $v_0$. One can easily see that $c_{m+n} \leq c_m c_n$ and hence ...
105 views

### General ballot theorem: sum of independent but not identically distributed random variables?

Is there ANY ballot-type result for random walk $S_n:=\sum_{i\le n}X_i$ that allows for independent but not identically distributed random variables $X_i$, up to some uniform concentration conditions ...
219 views

### Elementary cellular automata in stochastic modes

There are several ways to run a given elementary cellular automaton in a stochastic way: by giving for each of the eight local configurations 000,100,010 and so on a probability by which the rule is ...
269 views

### Minimum of random walks

Let $M$ independent and identical random walks that follow the chi-squared distribution, i.e. in each step, a $X^2_1$ random variable is added. I am interested in the minimum random walk at each step. ...
69 views

### Logarithmic speed walks on trees

Let $T$ be the infinite $3$-regular tree, equipped with the shortest path metric $d_T$. An infinite walk on $T$ is a map $f:\mathbb{N}\to T$ such that $d_T(f(a),f(a+1))\leq 1$ for all $a$. An infinite ...
123 views

### Conditional distribution of steps of random walk given the sum

Set-up. Consider a random walk $S_n=\sum_{i=1}^n X_i$, where $\{ X_i, 1\leq i < \infty \}$ is a sequence of i.i.d. random variables with distribution $\mu$, $\mathbb{E}X_1 = 0$. Let $a > 0$. ...
52 views

### Skip-free random walks: recurrence and transience

Let us define a one dimensional random walk: for all $n\in\mathbb{N}$ $$X_n:=\sum_{i=1}^nZ_i$$ with $Z_i$ i.i.d. random variables taking values in $\{-1,0,1,2,\dots\}$. This process is sometimes ...
1 vote
298 views

163 views

### Bernoulli trials with small dependencies: asymptotics (central limit theorem, law of the iterated logarithm)

Let $\{X_k\}$ be a sequence of random variables, with $X_k\in\{+1, -1\}$ for $k>0$, generated as follows. First, define $S_n=X_1+\dots +X_n$, with $X_0=S_0=0$, and let $0<\beta<\frac{1}{2}$. ...
252 views

### Local probabilities for lattice random walk

Let $\epsilon <1/2$. Let $X$ be a random variable in $\mathbb Z$ such that $\mathbb P (X=x)\le \epsilon$ for any $x\in \mathbb Z$ (you may add any moment or regularity conditions on $X$ if needed)....
1 vote
103 views

### Distribution of a random summand conditional on the sum of independent identically distributed copies

The question is simple to state: Let $S_n = \sum_{i=1}^n X_i$, where $X_i$ are independent random variables with a common distribution $F$. For simplicity, assume that $X_i \geq 0$ with prob. 1, and ...
194 views

### Invariance principle: Brownian bridge and random walk conditioned on end point

Let $\{X_i, i \in \mathbb{N}\}$ be a sequence of non-lattice i.i.d. centered random variables, $\mathbb{E} |X_1| ^3 < 0$. Let $S_n = \sum\limits _{i=1} ^n X_i$ be the corresponding random walk and ...
361 views

### Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
Let's take a simple random walk on $\mathbb{Z}$, $(S_n)_{n\geq0}$, started at zero. If $\tau^+_0 = \inf\{n \geq 1: S_n = 0\}$ is the first time the walk returns on zero, we know that $\mathbb{E}[\tau^+... 3 votes 1 answer 166 views ### Simple random walk with an extra condition Consider a simple random walk $$\mathcal{X}_t= \sum_{n<t} X_n,$$ where$P(X_n=1)= P(X_n=-1)= 1/2.$If I put an extra condition that excludes cases with more than 5 consecutive +1, or -1 in the sum: ... 2 votes 1 answer 450 views ### Probability that a symmetric random walk returns to$0$exactly$k$times in$2n$steps I'm trying to find a formula to find the probability of exactly k returns in 2n steps of a symmetric random walk. More specifically, I am trying to show that the probability of 2 returns is exactly ... 3 votes 1 answer 143 views ### Carne-Varopoulos bound and stationary measure Let$\Gamma$denote the Cayley graph for a finitely generated group$G$, and let$p_n(x, y)$denote the transition probability that a random walk starting at$x$reaches$y$at time$n$. A famous &... 2 votes 0 answers 58 views ### Handling sums of correlated random variables with a directed path structure Recently, I've been seeing random variables with the following correlation structure based on directed paths on a graph. For example, there are$16$directed paths "directed downwards from the ... 5 votes 1 answer 176 views ### Second Skorokhod embedding in high dimensions The first Skorokhod embedding theorem says that any random variable$X$with$\mathbb E X=0$and$\mathbb E X^2<\infty $can be written as$X=B_{\tau }$where$B$is a Brownian motion and$\tau$is ... 8 votes 2 answers 256 views ### Does entropy of the random walk control the return probability Given an infinite connected graph$G$of bounded degree with vertex set$X$, let$P_x^n$the time$n$distribution of the simple random walk started at the vertex$x$(so$P^n_x(y)$is the probability ... 2 votes 2 answers 136 views ### Which infinite random graphs with percolation threshold$p_c=0$are transient? I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements$\mathbb{...
The diffusion equation with constant diffusion $D$ can be represented as: \begin{equation} \frac{\partial \phi(r, t)}{\partial t}=D \Delta \phi(r, t) \end{equation} where $\Delta$ is the Laplace ...