Questions tagged [random-walks]

The tag has no usage guidance.

118 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
14
votes
0answers
232 views

A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity. ...
14
votes
0answers
552 views

Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been ...
9
votes
0answers
213 views

Is the P.M.F. of the first return time of a random walk monotone?

Suppose $X_1,X_2,\ldots$ are i.i.d. $\mathbb Z$-valued random variables such that the random walk $$S_n=\sum_{i=1}^nX_i$$ is recurrent with some period $k\geq1$ (i.e., $\Pr[S_n=0]>0$ if and only if ...
8
votes
0answers
188 views

Superharmonic functions and amenability

Let $G$ be a group generated by a finite set $S$. Let $P$ be a Markov operator defined by the uniform measure on $S$. A function is superharmonic if $Pf\leq f$. Assume that there is a set of non-...
8
votes
0answers
637 views

Asymmetric random walk on the line with barriers

The most commonly considered random walk on the line takes one step left or right with equal probability until a barrier is reached (if there are any barriers). More generally, suppose we fix any ...
7
votes
0answers
101 views

Sum of variables uniformly distributed on a circle: a cyclic property

Consider a random walk starting at the origin in the plane, walking $n$ steps in independent uniformly random directions with step lengths $a_1,\ldots,a_n$, and observing the distance from the origin. ...
7
votes
0answers
129 views

Random walk on $\mathbf{Z}_d$ with Jacobi $\theta$ transition probabilities

In the context of a finite-dimensional quantum mechanical problem, I was led to study the random walk on $\mathbf{Z}_d$ (i.e the integers modulo $d$), $d$ odd with transition probabilities given by: $...
7
votes
0answers
519 views

Calculate the expectation of the maximum of averaged random walks

Let $X_1, X_2, \ldots$ be iid random variables with bounded second moment. The question is to calculate the exact value of $$\mathbb{E} \max_{1 \le j < \infty} \frac{X_1 + \cdots + X_j}{j}.$$ Is ...
7
votes
0answers
250 views

Fixed radius mean value property implies harmonicity?

Let $f$ be a continuous real-valued function on $\mathbb{R}^n$. It is well known that the following are equivalent: $f$ is harmonic. $f$ satisfies the ball mean value property $$ f(x)=\frac{1}{|B(x,r)...
7
votes
0answers
127 views

Speed on recurrent graphs

Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?
7
votes
0answers
1k views

On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
6
votes
0answers
176 views

Distribution of the stopping time of an autoregressive sequence

Consider $e_t$ being i.i.d. uniformly chosen from $\pm 1$. Let $\eta$ be a small positive constant. What is the distribution of $T$ such that $\eta^{0.5} (1+\eta)^T W_T$ first hits $\pm 1$, in which $$...
6
votes
0answers
395 views

Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
5
votes
0answers
115 views

Random process on a sequence of rolls of an $n$-sided die

Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
5
votes
0answers
90 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 ...
5
votes
0answers
133 views

Continuity of the Green function with respect to the measure

Let $G$ be a finitely generated group and let $\mu$ be a finite measure on $G$. Define the Green function as $$G(\mu)=\sum_{n\geq 0}\mu^{*n}(e),$$ where $\mu^{*n}$ is the $n$th convolution power of $\...
5
votes
0answers
125 views

Random walks in arrangements of lines in the plane

Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$. (Simple: each pair of lines meet in a distinct point, i.e., no three lines pass through the same point.) Start a random walk at ...
5
votes
0answers
163 views

Random Up-walk on Young's Lattice

Starting from the empty partition, $\varnothing$, follow a random up-walk of length $n$ on Young's Lattice, where an edge's transition probability is 1/updegree. For a particular partition, $\lambda$, ...
5
votes
0answers
123 views

Chains of right annihilators in group rings

See the update below This problem emanates from a question on not-so-simple random walks on finitely generated groups. But to explain the connections would require an extremely long essay. Let $G$ be ...
5
votes
0answers
391 views

Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)

Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
5
votes
0answers
86 views

Most visited vertex in a random walk with place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
5
votes
0answers
181 views

hitting time of a subset

Suppose you have the simple random walk on $L=\mathbb{Z}^n,$ and $A \subset L$ is a subset (in my case, the subset is a union of hyperplanes, so in particular infinite). There is a random variable $T(...
5
votes
0answers
1k views

Compute the expected value of the next step of a sorted random walk

Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. ...
4
votes
0answers
59 views

A random walk/ruin theory problem with steps whose distribution has infinite mean

In what follows, I will make liberal use of the notations and terminology from ruin theory, just because I think it makes matters more intuitive. However, the problem I'm posing does not depend on its ...
4
votes
0answers
73 views

Random walks on the Poincaré disk

Let $G$ be the group of isometries of the Poincaré disk. Let $\mu$ be a probability measure on $G$, and consider $g_1,..,g_n$ i.i.d. random variables on $G$ distributed according to $\mu$. For $z\in \...
4
votes
0answers
113 views

Ihara zeta function and closed paths and trails

Let $\Gamma$ be a finite graph. There seem to be two definitions of closed path in the literature. In one, a closed path is just a walk whose starting vertex is the same as the ending vertex. (Let us ...
4
votes
0answers
155 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 ...
4
votes
0answers
213 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 ...
4
votes
0answers
147 views

Who proved the reflection principle in random walks and Brownian motion?

I've heard Henry McKean say that the reflection principle is due to Désiré André. But the wikipedia page seems to say that André did not use a reflection principle. Does anyone know where the "modern" ...
4
votes
0answers
103 views

Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?

In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
4
votes
0answers
226 views

Self-adjusting random walk

Let $X_t$ be a random process such that \begin{eqnarray} X_1 &=& 0\\ X_t &=& X_{t-1} + \left\{\begin{array}{ll} A_t, & X_{t-1} \geq 0\\ B_t, & X_{t-1} < 0 \end{array}\...
4
votes
0answers
138 views

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
4
votes
0answers
84 views

Is the family of probabilities generated by a random walk on a finitely generated amenable group asymptotically invariant?

Is the family of probabilities $\mu^n$ (convolution) generated by a random walk $\mu$ on a finitely generated amenable group $G$ asymptotically invariant ($\|g\mu^n-\mu\|_{L^1}\to 0$ for any $g\in G$)?...
4
votes
0answers
288 views

Why is the density function of a sum of many iid random variables (i.e., the Gaussian) self-dual?

In the usual proof of the central limit theorem via characteristic functions, we note that if $X_1, \dots, X_n$ are independent and identically distributed, with probability density function $f(x)$, ...
4
votes
0answers
152 views

1d random walk probability of previous n positions

I have the following question. (May be it is very simple, but I cannot find the answer). Suppose I have a 1d random walk on integer numbers with equal pobabilities of unit step in either direction (...
4
votes
0answers
173 views

Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice. Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...
4
votes
0answers
151 views

Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...
4
votes
0answers
1k views

Random walk on the hypercube

Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$: start from a point $x \in H_N$ pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and $...
4
votes
0answers
537 views

Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
3
votes
0answers
73 views

Random walk in a switching scenery

For each $x \in \mathbf{Z}$ let $(\eta_t(x))_{t\geq0}$ denote independent copies of a process $(\eta_t(0))_{t\geq0}$ defined as follows. The process $\eta_t(0)$ takes values in $\{-1,1\}$, where $-1$ ...
3
votes
0answers
53 views

Algebraic property of a transition matrix

Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...
3
votes
0answers
300 views

Random walk on $\mathbb{R}$ with "sticky" origin

Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...
3
votes
0answers
102 views

Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position

I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees. Consider a 1D random walk on the integers, starting at the origin, ...
3
votes
0answers
115 views

Any chance to get the moments of this exotic distribution?

Let us define the following cumulative distribution: \begin{align} \Pr (Y(t)\geq a)=\sum_{n=0}^\infty \frac{e^{-kt}(kt)^n }{n!}\int_a^\infty[\circledast_{f}\circ H_a ]^n\delta (x) dx \end{align} where ...
3
votes
0answers
149 views

Sequential generation of any random graph

The high-level question is: can we generate any random graph with size $d$ using a Markov chain? For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
3
votes
0answers
134 views

average probability for an edge be a in random spanning tree of a weighted graph

any cofactor of a Laplacian of a weighted graph will give the sum of all weighted spanning trees, lets denote it by $A$. The same can be calculated for spanning trees which avoid certain edge $e$, ...
3
votes
0answers
127 views

Probability that explosive random walk $X\to\gamma X+\epsilon$ with $\gamma>1$, always stays positive

Let $\{\epsilon_t\}_{t\ge0}$ be a sequence of iid random variables with full support. Let $\delta\ge0$ and $\gamma>1$. Then set $X_0 = \delta$ and define for $t\ge0$: $$ X_{t+1} = \gamma X_{t} + \...
3
votes
0answers
147 views

Question about martin boundaries of random walks induced on transient subgroups

Suppose $\Gamma$ is a discrete, finitely generated, non-amenable group, and consider a random walk given by a measure $\mu$. Assume the measure is symmetric, finitely generated, and the support of $\...
3
votes
0answers
191 views

Uniform sub-linearity of sub-additive functions on groups

Suppose $G$ is a finitely generated group and suppose $f: G \to \mathbb{R}$ is subadditive function, that is: $f(g_1\circ g_2) \leq f(g_1) + f(g_2)$. One example of such $f$ is the word length in some ...
3
votes
0answers
226 views

criterion for deciding whether the product of a sequence of Givens rotations can reach the full special orthogonal group

By Givens' rotation $R(1,2;\theta)$ I mean a matrix which has the $$\begin{pmatrix} \hphantom{-}\cos \theta &\sin \theta \cr -\sin \theta & \cos \theta \end{pmatrix}$$ $2 \times 2$ block at ...