The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
312 views

Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...
1
vote
1answer
232 views

Fundamental inequality of entropy in random walks

I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely, $\textbf{Question}$: ...
4
votes
1answer
420 views

Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...
5
votes
1answer
254 views

Memory of Uniformly Random Dyck Paths

Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have ...
2
votes
1answer
802 views

Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...
5
votes
1answer
286 views

The minimal norm of a shifted stochastic matrix

Hello, Given a row-stochastic matrix $M$ with singular values $\sigma_{1}\geq\ldots\geq\sigma_{n}$, I am looking for an upper bound on the expression: $\min_{\alpha}\parallel M- ...
2
votes
0answers
532 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 ...
1
vote
1answer
1k views

asymmetric random walk, hitting time probability

Let's consider an asymmetric Random Walk on $Z$, with transition probabilities $p_{i, i+1}=p$, $~~p_{i, i+1}=q$, $\forall i \in \mathcal{Z}$, $p+q=1$ and $p>q$. I am interested in the probability ...
0
votes
0answers
411 views

Probability density function of the node positions in a random walk after N time slots

Hello, my question basically is how do I find the probability density function of the position of the nodes in a given area after N discrete time slots when the nodes move following the 2D random walk ...
1
vote
1answer
76 views

Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some ...
1
vote
1answer
426 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
11
votes
1answer
467 views

Distribution of maximum of random walk conditioned to stay positive

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...
12
votes
3answers
479 views

Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
30
votes
1answer
1k views

Prime Number Races in 2 Dimensions

Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto \sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective? In 1999, when I was an undergraduate student, ...
0
votes
0answers
98 views

Theorem Leads for tied-down random walk

scribd.com/doc/87930409/18/Leads-for-tied-down-random-walk [Theorem 3.7, page 38] Could you explain me the last equality in the proof? I mean this: $$\frac{2[\sqrt{1 - s^2t^2} - ...
4
votes
1answer
244 views

Approximating a hitting time for some state using the stationary distribution?

Provided a random walk on a bounded interval, with step probabilities, $p$ and $q$ and a stationary distribution $\pi$, how "bad" of an approximation is to assume that the hitting time for a position ...
2
votes
1answer
305 views

Manhattan distance vs. absorption time on an unbounded integer lattice

Imagine I have unbounded $d$-dimensional integer lattice where I take two vertices, $v_a$ and $v_b$, separated by a fixed Manhattan distance $L$, and I release a random walker at $v_a$ and allow for ...
4
votes
5answers
559 views

Spectrum of transition matrix for symmetric random walk

I asked this question previously on math.stackexchange.com, where it had little traction. Consider the symmetric random walk on $\{0,1,…,n\}$ with transition probabilities $P(j→j±1)=1/2$ for $0 ...
2
votes
1answer
411 views

Probability that a “closable” self-avoiding random walk forms a polygon

Consider a self-avoiding random walk on an infinite graph (for concreteness, the grid of 2-dimensional lattice points $\mathbb{Z}^2$), in which on each step, the next position is chosen uniformly at ...
11
votes
2answers
906 views

Random walks on Coxeter groups

Let $G_N$ be the group generated by elements $a_1,\ldots,a_N$ subject to the relations $a_i^2=1$ and $(a_ia_j)^3=1$. The growth function of $G_N$ is then ...
2
votes
1answer
2k views

Expected Hitting Time for Simple Random Walk from origin to point (x,y) in 2D-Integer-Grid

Consider a simple random walk on the lattice $\mathbb Z^2$ starting at the origin $(0,0)$ where in each step, one of the four adjacent vertices in chosen uniformly at random, i.e. with probability ...
10
votes
1answer
355 views

Elephant populations (and Dyck words)

Hello, I'm relatively new to this forum so apologies if I have tagged my question incorrectly. I have been in contact with a wildlife biologist recently concerning counting elephant populations and ...
1
vote
1answer
245 views

Extending Wald's equation to two classes of i.d. random variables?

I try to adopt Wald's equation to a slightly more complex problem. In fact, after a full day, I found some solution now, but it has a confusing argument in the middle. Perhaps somebody can help me at ...
7
votes
1answer
863 views

Generating function for Random Walk Hitting Time, taking the wrong root

In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...
8
votes
2answers
528 views

A discrete random walk that avoids previously visited vertices for an exponentially distributed time interval

Imagine a discrete random walk on an infinite one-dimensional lattice where, for every unit interval of time, $(t_1, t_2, ...)$, the walker takes a step with uniform probability to its left or right. ...
4
votes
2answers
348 views

How does a quasi-isometry affect Poisson or Martin boundaries?

Take two graphs (of bounded valency) or manifolds (f bounded geometry) $G$ and $G'$. Assume there is a quasi-isometry $f:G \to G'$, and assume the Poisson or Martin boundary of $G$ is known, what may ...
1
vote
1answer
301 views

The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself

What is the probability that a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice is able to take more than $N$ steps, i.e. able to take more than $N$ steps before trapping itself ...
5
votes
0answers
153 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 ...
5
votes
0answers
807 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" ...
10
votes
2answers
959 views

Markov chains: invariant measures and explosion

The following seems like such an elementary question, but I didn't get anywhere with it. Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure ...
1
vote
1answer
197 views

Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...
2
votes
1answer
373 views

MCMC with progressive demollification of delta distributions

Edit: I simplified the example to a canonical case for clarity. Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space ...
3
votes
2answers
487 views

Simple random walk on the 3-1 tree is recurrent

Hello guys, There is an infinite tree structure named "the 3-1 tree", denoted by $T_{3-1}$. The tree is constructed as follows: The origin vertex (which can be referred to as the zeroth level) has ...
3
votes
1answer
317 views

Where does directed random walk hit the boundary of a region?

I have a problem that I more or less know the answer to (in an ad hoc way), but would really like to see it done in a systematic way. In spite of this, I will pose the question in quite a concrete ...
4
votes
1answer
233 views

Probability of a topologically non-trivial random walk on a finte torus

Hi: this question is regarding the topological properties of random walks on a finite torus. Consider an unbiased random walk on finite square lattice on a torus of linear dimension $L$. Place a ...
2
votes
2answers
247 views

Probability of a Random Walk crossing an increasing function of the standard deviation

Let $(S_n)_{n=0}^{\infty}$ be a random walk with $S_n = \sum_{i=1}^n X_i$, and let the $X_i$ be distributed according to some (bounded) distribution function $F$ with mean $0$ and variance $1$, so ...
1
vote
0answers
191 views

A random walk with uniformly distributed steps II

The problem is a improved version of this problem, A random walk with uniformly distributed steps Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will ...
3
votes
1answer
393 views

Transience of self avoiding random walks on $\mathbb{Z}^d$

I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...
1
vote
1answer
273 views

Limit of a rescaled random sum of i.i.d. random variables

Consider a sequence of i.i.d. random variables $(X_i)_{i \in \mathbb N}$ and let $S_n=X_1+\dots+X_n$ For every $\alpha \in ]0,+\infty[$, let $N(\alpha)$ be a discrete random variable on $\mathbb N$, ...
2
votes
1answer
324 views

Reference Request: Cover time for simple random walk on nxn torus

I'm putting the finishing touches on my masters thesis and need a reference for the following fact (which my advisor told me): Let $G$ be the $n\times n$ grid and identify the sides to make it a ...
20
votes
5answers
3k views

A random walk with uniformly distributed steps

The following problem has bothered me for a long time. Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the ...
2
votes
0answers
200 views

$n$-th return of a random walk on $\Bbb Z^d$

Lets define $f_n = P(X_n =0 , X_k \ne 0, k< n)$ the first return distribution of the random walk $X_n$ on $\mathbb{Z}^d$, and lets go ahead and assume that $f_n \approx n^{-(1+\alpha)}$ for some ...
1
vote
2answers
392 views

Gibbs sampling step size

I have some data generated using MCMC methods and in particular Gibbs sampling. I computed the autocorrelation but I'm unsure how to determine how many samples to skip. I'd like to determine that ...
1
vote
0answers
253 views

Random Walk in $\mathbb{R}^n$

Have there been papers dealing with random walks in $\mathbb{R}^n$ that are not on the lattice $\mathbb{Z}^n$? Instead of walking in one of the directions possible in $\mathbb{Z}^n$ with probability ...
8
votes
1answer
300 views

Mixing time of unitary Brownian motion

Let $B_t$ be the unitary Brownian motion, i.e. Brownian motion on the unitary group $U(N)$. What is known about the mixing time of $B_t$, that is, how fast does the measure $B_t(\delta_{\{Id\}})$ ...
2
votes
1answer
964 views

first passage time, brownian motion

Hi, If X(t) is Brownian motion in 2D, where X(0) = 0, then we can ask what is the expected time required to first hit a circle of radius R, centered at the origin. This is a First Passage Time ...
8
votes
0answers
959 views

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of ...
3
votes
1answer
307 views

Maximum vertical distance for a lattice path when NSEW steps are allowed

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed. For a given path $L$, let $\max(L)$ be the maximum value of the $y$ coordinate ...
13
votes
5answers
1k views

Simple Random Walk on a Locally Finite Graph - when is it recurrent?

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...
9
votes
1answer
1k views

Pólya's Random Walk Constants at infinity

Let be the probability that a random walk on a d-D lattice returns to the origin. In 1921, Pólya proved that $p(1)=p(2)=1$ but $p(d)<1$ for $d>2$. ...