# Questions tagged [random-walks]

The tag has no usage guidance.

526 questions
Filter by
Sorted by
Tagged with
82 views

130 views

### Dispersion of random walk with scaled step sizes

Let $Y_j$ be a sequence of independent Gaussian random variables with mean zero and unit variance ($\mathbb{E} Y_j = 0$ and $\mathbb{E} Y_j^2 = 1$) and let $\sigma:\mathbb{R}\to [1,2]$. We define the ...
• 452
488 views

### Probability of $\operatorname{Bin}(n,p)=\operatorname{Bin}(n,q)$ is decreasing when $n$ increases

$\newcommand{\Bin}{\operatorname{Bin}}$I would like to show that $\mathbb P(\operatorname{Binomial}(n,p) = \operatorname{Binomial}(n,q))$ decreases when $n$ increases for a fixed pair $(p,q)$. This ...
• 233
232 views

### Bounds on hitting time of sum of i.i.d. random variables

I have a sequence $(X_i)_{i\geq 1}$ of i.i.d. random variables taking values in $\mathbb Z$. I know that each $X_i$ has mean $0$ and finite variance $\sigma^2$. Let $S_n=X_1+\cdots+X_n$. Then I can ...
74 views

65 views

### Random pseudo-walk with 'disappearing' values

This question is a twist on a question I asked here Random pseudo-walk of Poisson variables, but with randomly 'disappearing' objects. I do not know how to generalize the (satisfactory) answer given ...
• 61
43 views

32 views

### Transience of the SRW on regular graphs of exponential growth

Let $G$ be a $d$-regular graph of exponential growth. By exponential growth I mean that $$\liminf_{r \to \infty} | B(o, r)|^{1/r} >1.$$ Here $B(o,r)$ is the ball of radius $r$ centered at a given ...
• 6,182
537 views

### Balancing act for infinite walks

Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any ...
• 18.4k
145 views

### Running minimum of exponential random walks

Let $\{X_i\}$ be a collection of i.i.d. Exp$(1)$ random variables. For $k \in \mathbb{Z}_{>0}$, define $$S_k = \sum_{i=1}^k X_i$$ and note that $\mathbb{E}[S_k] = k$. I was wondering if there is ...
• 485
112 views

140 views

### How to sample uniformly over a polytope knowing its vertex presentation?

Say that a convex polytope $P$ is presented as $P = \mathrm{Conv}(v_1, \dots , v_m)$. I would like to sample over $P$, without generating the facet presentation of the polytope. How can I do that? I ...
• 1,435
119 views

### Random walk with same directions and different step sizes

Let $X\sim e^{iU}$, where $U$ is uniformly distributed on $(0, 2\pi]$. Define $\chi_1, \cdots, \chi_t$ as i.i.d. random variables with the same distribution as $X$. Consider the following two random ...
• 489
282 views

### How far does a random walker travel before returning to the origin?

Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\}$. It is well known that this random walk is ...
• 59
77 views

### A question on the convex hull of independent random walks

Consider $m$ independent random walks $X^1_n, \dots, X^m_n$ driven by a probability measure $\mu$ in $\mathbb{Z}^d$. Assume that the $\mu$ has no drift, that is, the expected value of a $\mu$-...
• 6,182
72 views

### Small angles between independent centred random walks in $\mathbb{Z}^d$

Let $W_n$ and $W'_n$ denote two independent random walks in $\mathbb{Z}^d$ defined using a finitely supported centred (mean zero) probability measure on $\mathbb{Z}^d$. For $N \ge 1$, let $\theta_n$ ...
• 6,182
183 views

• 2,403
1k views

### Optimal search puzzle

Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
509 views

### Probability to return to the origin for a uniform random walk

Consider a uniform random walk on $\mathbb{R}$, with stepsize chosen uniformly from the interval $(-1,1)$. The random walk start at $x=0$. Denote by $\rho_p dx$ the probability that the random walk ...
• 185k
143 views

• 443