# Tagged Questions

The tag has no usage guidance.

557 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. ...
373 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 ...
313 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 ...
157 views

497 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 ...
321 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 way....
238 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 ...
254 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 ...
197 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 "...
419 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 ...
284 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$, ...
351 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 ...
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 ...
206 views

325 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\}})$ ...
1k 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 ...
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 $... 1answer 311 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 ... 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 ... 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$. http://mathworld.wolfram.com/... 2answers 442 views ### Limit shape for fixed-perimeter lattice polygons Let$P$be a simple polygon defined by$n$unit-length segments connecting lattice points of$\mathbb{Z}^2$. I have two operations that preserve the perimeter of$P$. The first is the "pop" of a ... 2answers 899 views ### probability distribution of hitting nodes on a finite graph random walk Consider a finite, undirected, scale-free graph$\{G}$, with uniform edge weights. We define a truncated random walk on$\{G}$as a random walk that continues for exactly$\{k}$steps. For an ... 2answers 380 views ### Complexity of detecting a convex body in$\mathbb{R}^n$? Let$K_0$be a bounded convex set in$\mathbb{R}^n$within which lie two sets$K_1$and$K_2$.$K_0,K_1,K_2$have nonempty interior. Assume that,$K_1\cup K_2=K_0$and$K_1\cap K_2=\emptyset$. The ... 1answer 408 views ### Decomposition of Haar measure other than Hurwitz's Hurwitz defined a decomposition of the Haar measure on$SO(n)$based on Given's rotation. So by left multiplication of Givens rotation one can always bring an orthogonal matrix into the identity. The ... 0answers 187 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 ... 1answer 246 views ### Walks that cannot hit the boundary I've casually proved, as application of some ideas that I am developing, a result that might be of interest in itself. I am completely new in this field and then I would like to ask your help to ... 2answers 901 views ### What is the maximum diameter of$N$steps of a random walk? Since probability is quite far away from my daily buisiness, please forgive me if my use of terminology is wrong or the question is too trivial. However, I was not able to find the right keyword to ... 0answers 273 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 ... 2answers 955 views ### Probability of first return to starting vertex in Random walk on regular finite graph Hi, this is related to this earlier question. Given Random walk on a regular graph$G=(V,E)$. The Random walk is simple so that transition probabilities are$1/\text{deg}(v_i)$, and time is in ... 1answer 429 views ### Comparing hitting probabilities for two different random walks Let$p$be a probability in$]0,1[$, and let$(X^p_i)_{i \geq 1}$be a i.i.d. family of variables with law$P(X=1)=p, P(X=-\frac{p}{1-p})=1-p$(so that$E(X)=0$). Set$S^p_n=\sum_{k=1}^{n} X^p_k$for ... 3answers 260 views ### How long does it take a Brownian particle to achieve a uniform probability distribution across a space? Imagine I have a point-like Brownian particle, with diffusion constant$D$, and I place it at some initial coordinate in a cage of known geometry. Assuming the volume$V$of the cage is "everywhere" ... 3answers 430 views ### Averaging over random walk on binary lattice I have a function$f$defined over a bit vector of length$n$. Equivalently, this is a function defined on the set of integers$[0,\ldots,2^n-1]$. I would like to compute the mean or variance or some ... 0answers 144 views ### Reference request for a result on subsets unlikely to be hit by random walks in a group Suppose we are performing a random walk in a group. More precisely, we have a finite generating set$S$of a group$G$and the probability of walking along generator$s$is given by$\mu(s)$for some ... 1answer 723 views ### How far can a particle travel from its origin if it exhibits self-avoiding Brownian motion in two-dimensions? Let's say I have a point-like Brownian particle undergoing two-dimensional diffusion on an infinite plane with the caveat is that the particle can never return to a coordinate that it previously ... 0answers 539 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. ... 0answers 287 views ### Cover time for a biased random walk on an 'N'-dimensional integer lattice Imagine that I have a random walk on an$N$-dimensional integer lattice,$Z^N$, of finite dimensions,$(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some ... 1answer 593 views ### exactly simulating a random walk from infinity In diffusion-limited aggregation on the square lattice, one lets a particle do "random walk from infinity" until it hits the current aggregate, at which point the site occupied by the particle is ... 5answers 4k views ### Probability of a Random Walk crossing a straight line Let$(S_n)_{n=1}^{\infty}$be a standard random walk with$S_n = \sum_{i=1}^n X_i$and$\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let$\alpha \in \mathbb{R}$be some constant. I would like to know the ... 1answer 3k views ### Rolling a random walk on a sphere A ball rolls down an inclined plane, encountering horizontal obstacles, at which it rolls left/right with equal probability. There are regularly spaced staggered gaps that let the ball roll down to ... 4answers 1k views ### Will a random walk on [0, inf) tend to infinity? [closed] Consider a random walk on [0, inf) where you start at 0. With probability p = 0.5, you increase by 1. With probability (1-p) = 0.5, you decrease by 1, but not below 0. As time goes to infinity, will ... 2answers 1k views ### Probability of return at step$n$of a Random walk to its starting vertex Hi, given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site at step$n$? Specifically, I am interested in the ... 4answers 2k views ### What is the cover time of a random walk on a cube? I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ... 2answers 563 views ### Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory? The second stage of elliptic curve factorization has the drawback of large memory usage. Let$n=pq$,$E(\mathbb{Z}/n\mathbb{Z})$is elliptic curve and$P$point on$E(\mathbb{Z}/n\mathbb{Z})$. On$...
Preface: I am fairly new to the concept of Hausdorff dimension, so I don't know how interesting a question this is. Identify walks on $\mathbb{Z}$ with infinite binary sequences (say $0$ means moving ...