Questions tagged [random-walks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
34 views

Expected value of a Stochastic process

Consider a discrete stochastic process $\{X_t\}_{t \in T}$ with the following properties. Each $t \in T$ has a value $v(t) \in \mathbb{R}_{+}$ and the value is added to the overall value conditioned ...
John's user avatar
  • 161
2 votes
0 answers
101 views

Asymptotic Independence of random walks from increments?

Suppose we have two random walks $(S_n:n\geq 1)$ and $(T_n:n\geq 1)$ building from independent identically distributed increment vectors $\{(X_k,Y_k):k\geq 1\}$, i.e. $S_n=\sum_{k=1}^n X_k, T_n=\sum_{...
MikeG's user avatar
  • 665
3 votes
1 answer
154 views

Simple linear asymptotics for leaving time of particle in open-boundary TASEP

EDIT: It appears the hypothesis may not be true - I am not sure. I therefore changed my question. ORIGINAL QUESTION: Consider a system $n$ linked discrete cells numbered $1 \ldots n$. Particles are ...
aellab's user avatar
  • 133
5 votes
3 answers
544 views

Winning game probability

At each round of a game with two players Alice and Bob, Alice can win with a fixed probability $a$ and Bob can win a fixed probability $b$, such that $a+b < 1$, otherwise there is a draw. The game ...
heartwork's user avatar
  • 385
1 vote
0 answers
157 views

Locally "unshortable" paths in graphs

Setup: Consider a connected graph G, with diameter "d". Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
Alexander Chervov's user avatar
2 votes
0 answers
188 views

If the operators $B_i'$ satisfy an inequality, prove that $B_1'+\dotsb+ B_n'$ also satisfies the same inequality

Related: On a deceptively tricky calculus problem. The way that Leonard Gross proves the log Sobolev inequality is in the following stages: He proves that for any operator $B$ that satisfies the log ...
matilda's user avatar
  • 90
1 vote
0 answers
117 views

Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?

Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below. What is important - that there are huge COMMUTING subsets of generators. Question: Consider a random walk ...
Alexander Chervov's user avatar
1 vote
0 answers
75 views

Conditioned random walk over a graph

I want to solve for a conditioned random walk over a graph. I have a directed graph $G$. The random walkers start at a fixed node, Source. They all need to end up at fixed node, Sink. So the random ...
highBandWidth's user avatar
3 votes
0 answers
119 views

An analogue of Kolmogorov's law of the iterated logarithm

Let $X_1,\dots,X_n$ be independent random variables, each with mean zero and finite variance. Let $S_n = \sum\limits_{k=1}^n X_k$ and $s_n^2=ES_n^2$. We say the sequence obey the law of iterated ...
graham's user avatar
  • 131
3 votes
1 answer
340 views

Random pseudo-walk of Poisson variables

Suppose there is a pool that can contain any non-negative number of objects. At time $t$ it contains $n_t$ objects. Time is discrete. Before time $t+1$ two things happen, in this order: Unless the ...
Amir Ban's user avatar
1 vote
3 answers
246 views

Probability that a 1-D zero mean random walk remains at each step inside a square root boundary

Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\...
MathRevenge's user avatar
2 votes
0 answers
123 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 ...
giulio bullsaver's user avatar
2 votes
0 answers
86 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 ...
Farzad Aryan's user avatar
0 votes
1 answer
207 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 ...
Tiago's user avatar
  • 59
2 votes
0 answers
76 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$-...
Keivan Karai's user avatar
  • 6,064
4 votes
0 answers
70 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$ ...
Keivan Karai's user avatar
  • 6,064
4 votes
1 answer
182 views

Sign of error in the central limit theorem

Let $X_n$ and $Y_n$ be independent copies of two random variables $X$ and $Y$ with domain $\{-1,0,1\}$ for $n\in \mathbb{N}$. For a given $k\in \mathbb{N}$, I would like to find conditions on $X$ and $...
Flo Dorner's user avatar
4 votes
1 answer
250 views

A coupon collector-ish question

Imagine we are in the coupon collector setting: every time step we get independently one coupon out of $n$ coupons uniformly at random. However, unlike the coupon collector problem, we stop the at the ...
DeepC's user avatar
  • 53
2 votes
0 answers
81 views

Defining a metric on $\mathbb Z^n$ using Green's function for the simple random walk

Let $G$ be Green's function for the simple random walk on $\mathbb Z^n$ for $n\ge 3$, i.e., $G(x)$ is the expected number of visits to $x$ when the walk starts at the origin. Define $d(x,y)=G(x-y)^{1/(...
Alexander Pruss's user avatar
13 votes
2 answers
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 ...
jackisquizzical's user avatar
4 votes
1 answer
469 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 ...
Carlo Beenakker's user avatar
-1 votes
1 answer
132 views

Strong law of large numbers for a sequence of random variables in different probability spaces

Is it known whether the following version of the strong law of large numbers holds? For each $k\in\mathbb{N}$, let $\Omega_k$ be a finite set and $\mu_k$ be a probability measure on $\Omega_k$. Let $(...
Aleksi's user avatar
  • 1
3 votes
2 answers
184 views

Random walk to visible lattice points

Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible (not blocked) lattice points $p$, with a parameter $r$ a given radius of a circle centered on $p$. With $p$ the previous point, ...
Joseph O'Rourke's user avatar
2 votes
2 answers
115 views

Example of random walk in a random environment (RWRE) saying things on the environment

I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment. To clarify a bit, ...
Cal's user avatar
  • 59
8 votes
0 answers
148 views

Random walk on matrix until singularity

Consider a random walk on matrices, where one starts with the matrix $M=I_n$ and at each step randomly chooses an entry of $M$ to increase by $1$. I’m interested in two things about this walk: What’s ...
TheBestMagician's user avatar
1 vote
1 answer
205 views

Rate of convergence to uniform distribution

Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...
dohmatob's user avatar
  • 6,706
7 votes
1 answer
303 views

Diameter bound for graphs: spectral and random walk versions

This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
Stefan Steinerberger's user avatar
4 votes
1 answer
245 views

Does a subset with small cardinality represent the whole set?

Assume that we have heavy-tailed distribution $F(x)$ such that \begin{align} F(x)=\mathbb{P}[X\geq x]=x^{-0.5}. \end{align} Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...
Math_Y's user avatar
  • 311
2 votes
1 answer
158 views

A question about convergence of stochastic processes converging to a random walk

Consider the following random walk $(y_t)_{t \in \mathbb Z_+}$: $$y_t = y_{t-1} + u_t,\quad (u_t)_{t \in \mathbb Z_+} \overset{iid}{\sim} N(0,1), \quad (t \in \mathbb Z_+)$$ where $y_0, u_1, u_2,...$ ...
PSE's user avatar
  • 13
2 votes
1 answer
97 views

Randomly chosen walk of fixed length

Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$. A walk of ...
S. M. Roch's user avatar
1 vote
0 answers
66 views

Reference for the asymptotic mixing time of the random walk on the cycle

In Diaconis's book Group Representations in Probability and Statistics, Chapter 3C, there are explicit computations for the mixing time of the random walk on the cycle graph $\mathbb{Z}_{p}$, with $p$ ...
Austin80's user avatar
  • 111
4 votes
1 answer
138 views

counting fixed-area closed walks on square 2d lattice

I want to count the number $N(n,A)$ of closed walks of length $2n$ on the square $2d$ lattice enclosing a signed area of $A$. These numbers refine $\sum_A N(n,A) = \left(\begin{array}{c}2n\\n\end{...
Eric Zaslow's user avatar
2 votes
0 answers
75 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 ...
user82261's user avatar
  • 121
0 votes
0 answers
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 ...
Penelope Benenati's user avatar
1 vote
1 answer
95 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 ...
BayesFans's user avatar
0 votes
1 answer
72 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 ...
Fei Cao's user avatar
  • 700
6 votes
1 answer
335 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\}$....
Penelope Benenati's user avatar
3 votes
2 answers
419 views

Random spanning trees probability problem

We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $...
Penelope Benenati's user avatar
4 votes
1 answer
342 views

Derive the solution of the diffusion equation from the solution of a random walk

Summary The probability distribution (pdf) of a random walk in 1 dimension is represented by a Bessel function. On the other hand, the pdf of a Brownian motion in free space is represented by a ...
Sam's user avatar
  • 261
0 votes
0 answers
183 views

The meaning of random number generator test failing

I have a random number generator (number theoretic) that passes all of the NIST tests except the random excursions test. Is there any deep dark meaning to this? To amplify "deep dark meaning"...
Igor Rivin's user avatar
  • 95.5k
1 vote
2 answers
157 views

Asymptotic properties of weighted random walks / infinite convolutions of random variables

Let $(X_n)_{n\in\mathbb{N}}$ be a sequence of i.i.d. real-random variables. Let further $0<c<1$. I'm interested in the asymptotic properties of $$ \sum_{k=1}^n c^k X_k. $$ I can prove that this ...
SetofMeasureZero's user avatar
1 vote
1 answer
120 views

A question about the square root error of one dimensional random walks

Consider a one dimensional random walk, in which the probability of moving left along a line is $q=1/2$ and the probability of moving right is $p=1/2$. The square root error $\langle d_N \rangle$, ...
EGME's user avatar
  • 1,008
7 votes
1 answer
227 views

Counting returns in null-recurrent random walk

Consider two independent copies of IID random walk on ${\bf Z}$ starting from $0$, and let $N_1(t)$ (resp. $N_2(t)$) denote the number of times, up to time $t$, that the first (resp. second) walker ...
James Propp's user avatar
  • 19.4k
4 votes
1 answer
242 views

Random walk visiting a cylinder infinitely often

I wonder whether a $d$-dimensional random walk $S_n$, generated by the infinite i.i.d. copies of X given by: $X=e_1=(1, 0, 0, ..., 0)$ (with probability $p_1$) $X=e_2=(0, 1, 0, ..., 0)$ (with ...
Hamid Enki's user avatar
3 votes
1 answer
326 views

Importance resampling with exponential weighting

Suppose that we have $$ \frac{p(x)}{q(x)} \propto \exp(\tau f(x)), $$ where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x_i\}_{i=1}^n$ such that $n^{-1}\sum_{...
Minkov's user avatar
  • 1,117
3 votes
2 answers
234 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 ...
0xbadf00d's user avatar
  • 161
5 votes
1 answer
105 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 ...
Testcase's user avatar
  • 541
6 votes
1 answer
206 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 ...
Salini Mendisi's user avatar
4 votes
1 answer
226 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 ...
MikeG's user avatar
  • 665
3 votes
2 answers
232 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 ...
Hans-Peter Stricker's user avatar

1
2 3 4 5
11