Questions tagged [random-walks]
The random-walks tag has no usage guidance.
511
questions
-1
votes
0
answers
40
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 ...
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_{...
3
votes
1
answer
157
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 ...
5
votes
3
answers
552
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 ...
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 ...
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 ...
1
vote
0
answers
123
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 ...
1
vote
0
answers
77
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 ...
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 ...
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 ...
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\...
2
votes
0
answers
124
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 ...
2
votes
0
answers
88
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 ...
0
votes
1
answer
212
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 ...
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$-...
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$ ...
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 $...
5
votes
2
answers
347
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 ...
2
votes
0
answers
83
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/(...
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 ...
4
votes
1
answer
475
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 ...
-1
votes
1
answer
133
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 $(...
3
votes
2
answers
188
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, ...
2
votes
2
answers
117
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, ...
8
votes
0
answers
149
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 ...
1
vote
1
answer
207
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 ...
7
votes
1
answer
306
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 ...
4
votes
1
answer
246
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 ...
2
votes
1
answer
159
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,...$ ...
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 ...
1
vote
0
answers
67
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$ ...
4
votes
1
answer
139
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{...
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 ...
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 ...
1
vote
1
answer
96
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 ...
0
votes
1
answer
73
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 ...
6
votes
1
answer
337
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\}$....
3
votes
2
answers
425
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 $...
4
votes
1
answer
359
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 ...
0
votes
0
answers
186
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"...
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 ...
1
vote
1
answer
122
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$, ...
7
votes
1
answer
230
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 ...
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 ...
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_{...
3
votes
2
answers
235
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 ...
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 ...
6
votes
1
answer
208
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 ...
4
votes
1
answer
231
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 ...
3
votes
2
answers
233
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 ...