# Questions tagged [random-walks]

The tag has no usage guidance.

364 questions
Filter by
Sorted by
Tagged with
46 views

### Concentration (or two sided tail bounds around expectations) of maximum and minimum of $n$ iid, subgaussian random variables

I asked this on MSE, but got no answer, hence asking here now. Help appreciated! My question is motivated by this question and this question, where the first was aimed for giving a one sided tail ...
47 views

### Support of random closed walk in arbitrary graph

Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...
61 views

### Reference request: Donsker's theorem for non-identical, independent random variables

The central limit theorem can be generalized to independent but not iid random variables, provided they satisfy the Lyapunov condition (which looks something like a variance bound), see https://en....
761 views

21 views

74 views

### Probability of m crossings of 0 before time n of a Gaussian random walk

Let $S_n = \sum_{n=1}^n X_n$ be a Gaussian random walk where $X_n$ are i.i.d random variables with distribution $\mathcal{N} (0,1)$. Could anyone show some hints and reference about how to compute the ...
194 views

273 views

### Random Walk on Pentagonal Tiling

I’ve recently been looking at closed walks on tilings of the plane in which the “player” can move from one tile to any of its edge-adjacent neighbors. In particular, I’m trying to find asymptotic ...
175 views

### Dyck paths weighted by height profile

We are interested in a question concerning a weight function on Dyck paths that penalizes visits to higher heights. Let $\rho$ be a parameter. Let $D_k$ be the set of all nearest neighbor random walk ...
67 views

### Transition matrix for shortest path walk

Consider a directed, weighted graph $G$. Let $s$ and $t$ be two distinct vertices of $G$ and consider a walker that starts at $s$ and traverses a random shortest path from $s$ to $t$, chosen uniformly ...
106 views

### WIll a proliferating 3D random walk a.s. revisit the origin?

The concept of a "proliferating random walk" on a lattice is that at any time $t \in \Bbb N \cup 0$, there is some set consisting of at least one particle, each of which is on its own lattice point. ...
555 views

### A comprehensive list of random walk inequalities?

I am interested in finding a comprehensive list of all noticeable random walk inequalities. ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$ I can only seem to find books/papers that list ...
213 views

### Quadratic variation of sum of random variables

Let $N = (N_t)_{t\geq 0}$ be a Poisson process and consider random variables $Z_n$, $n\in N$. Compute the quadratic variations $[X]_t$ where $X_t = \sum_{n=1}^{N_t}Z_n$. What I did was plugging $X_t$ ...
355 views

### Growing a chain of unit-area triangles: Fills the plane?

Define a process to start with a unit-area equilateral triangle, and at each step glue on another unit-area triangle.                     $50$ ...
101 views

### Entropy of endpoints of a random walk in a dense graph

Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$. Let $X$ be a random vertex of $G$ chosen proportional to ...
1k views

767 views

### Random Walks on high dimensional spaces

I've read on a paper that, in the two dimensional case, if you start from the origin and take steps of length one in arbitrary directions (uniformely on the unit sphere $S^1$, not left-right-up-down), ...
Our goal is to sample from the Laplace distribution conditioned on a linear subspace. Here are the details of this problem. Let $$p(x) \propto \exp(-\|x\|_1/\sigma)$$ be the pdf of the Laplace ...