# Questions tagged [random-walks]

The tag has no usage guidance.

346 questions
Filter by
Sorted by
Tagged with
168 views

### Random walks: How many times does the largest component change?

My understanding is that for an unbiased random walk (starting at the origin) on $\mathbb R$ with $N$ steps that the expected number of sign changes is $O(\sqrt N)$. For a biased walk I believe the ...
66 views

### Intuition behind the local limit theorem in hyperbolic groups

Let $\Gamma$ be a finitely generated group and let $\mu$ be a probability measure on $\Gamma$. Denote by $X_n$ the induced random walk. Finally, let $p_n=\mu^{*n}(e)=P_e(X_n=e)$. The local limit ...
99 views

### Symmetric random walks - bounds on the amount of time spent in a subset $A$?

For a symmetric random walk $S_n$, if we have a bound $P(S_n \in A) < \delta$, do we get a bound on the amount of time $S_n$ spends in $A$? Let $S_n$ be a symmetric random walk on the integers. ...
182 views

### Strategy for finding each other in a crowd

Looking for a strategy for finding each other in a crowd, is it better to have one person move and one person stay put, or have both people move? Suppose we have a $n$ by $n$ grid of squares. Each ...
165 views

### expectation of random walk with barriers

Suppose we are flipping a coin with probability $p$ of coming up heads and $q$ of coming up tails. We start with $n$ dollars, and the game is over when we either lose all our money or win $m$ dollars. ...
42 views

### hitting probabilities of oriented random walk

Consider a random walk on $\mathbb{Z}^2$, starting at $(0,0)$. Each step it moves rightwards with probability $p$ and upwards with probability $q=1-p$. The random walk terminates when it hits the ...
143 views

### Equivalence of harmonic measures on hyperbolic groups

Consider a Gromov-hyperbolic group $\Gamma$ and let $\mu$ be a finitely supported probability measure on $\Gamma$. Assume that the support of $\mu$ generates $\Gamma$ as a semi-group, in other words, ...
70 views

### Smooth transformation of a curve with fixed ends and length [duplicate]

I am simulating polymers of fixed length and fixed ends. I would like to search the phase space of all possible conformations quickly. Is there anyway I can generate efficiently a lot of (rather) ...
248 views

### Probability that random walk stays in quadrant

Let $S_n = \sum_{i=1}^n X_i$ where $X_i \in \mathbb R^d$ are iid. random vectors with $E[X_i]=0$. We want to lower-bound the probability that \begin{align} \forall_{n=1}^m S_n \le k \end{align}...
182 views

### Random walk on the hypercube with deleted edges

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
305 views

### Is random walk drift rational?

(Question mildly edited for clarity by request of Matt F.) If $G$ is a finitely presented group, let $|\cdot|$ denote the word metric with respect to a finite set of generators. Suppose $\nu$ is a ...
94 views

### Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?

Is the following uniform SMB theorem for random walks on expander graphs true? For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...
18 views

### Approximate method to extract behavior of a Laplace transform in an intermediate region

In the theory of random walks, Tauberian type theorems are often applied to extract the small or large-time behavior from a difficult equation. For example, the Montroll-Weiss formula describing a ...
120 views

72 views

### Figuring out a consistent definition for the percolation backbone

In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...
74 views

### Graph pattern matching

Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time. ...
377 views

### Expected distance from the origin for a recurrent 1D random walk in a random environment

It is well known that for a discrete random walk on the integers with a fair coin, the expected distance of the walker from the origin after $N$ time steps is $\sqrt{\frac{2N}{\pi}}$ if $N$ is large. ...
45 views

### Finite time version of “A pattern of hitting times for a simple random walk”

The question below was asked and answered here: Let $\omega_1, \omega_2, \ldots$ be uniform iid on $\{-1,1\}$, and let $X_n = \sum_{i=0}^n \omega_i$ be the corresponding simple random walk. Fix ...
124 views

61 views

210 views

### Irreducible but not completely irreducible

Consider a product of i.i.d. $d\times d$ random matrices $A_{i}$ (with $\mathbb{E}\log\left\Vert A_{i}\right\Vert <\infty$). Let $F:M\times \mathbb R^d\to M\times \mathbb R^d$ be a linear cocycle, ...
102 views

325 views

### How to find a random cycle in a large graph?

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve ...
81 views

### Proof of reduction from random walks to martingales - why $T\le k$?

I'm trying to understand the proof of theorem 1.6 from the paper "A Matrix Expander Chernoff Bound". In the proof they say: "Iterating this construction on the remainder a total of $T ≤ k$ times" and ...
By combining two methods I've stumbled into a rather messy random walk situation. I have the typical random walk setup $$\theta_{i+1} = \theta_{i} + \hat{\theta}_{i+1}$$ Where \$\hat{\theta}_{i+1} \...