The tag has no wiki summary.

learn more… | top users | synonyms

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
868 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$. ...
8
votes
2answers
367 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 ...
2
votes
2answers
581 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 ...
6
votes
2answers
377 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 ...
4
votes
1answer
374 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 ...
3
votes
0answers
174 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 ...
-1
votes
1answer
240 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 ...
12
votes
2answers
675 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 ...
5
votes
0answers
232 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 ...
1
vote
2answers
779 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 ...
1
vote
1answer
355 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 ...
2
votes
3answers
255 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" ...
4
votes
3answers
397 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 ...
2
votes
0answers
136 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 ...
11
votes
1answer
640 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 ...
5
votes
0answers
384 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. ...
2
votes
0answers
258 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 ...
10
votes
1answer
529 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 ...
20
votes
5answers
3k 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 ...
36
votes
1answer
2k 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 ...
1
vote
4answers
954 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 ...
4
votes
2answers
988 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 ...
10
votes
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 ...
2
votes
2answers
485 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 ...
3
votes
2answers
297 views

Hausdorff dimension of non-recurrent walks

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 ...
9
votes
1answer
655 views

Probability of return vs. probability of return in minimal number of steps

Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ ...
7
votes
1answer
656 views

Random walk on a simple finite network

Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ). Take a random walker that wonders around ...
1
vote
1answer
261 views

Winding number bijection on graphs

Let $G=(V,E)$ be an isoradial graph. In other words the graph can be imbedded into the plane such that each face (plaquette) can be circumscribed a circle of radius 1 with the circle's center ...
4
votes
1answer
651 views

A random walk on natural numbers

We are taking a random walk on the set of natural numbers. If we are at $M$, then with probability 1/4, we stay at $M$, with probability 5/12 we move to some random number less than or equal to $M/2$, ...
3
votes
1answer
768 views

Intersection Probabilities for Random Walk in d>2

I'd like to get asymptotics on the probability that n independent random walks coalesce. Start with n independent walks. As soon as two walks intersect they become one walk and continue evolving as ...
3
votes
1answer
223 views

Self Avoiding Walk Pair Correlation

Let $\gamma(i)$ be a self avoiding walk (SAW) on a 2D lattice $L$ (a square lattice for example) starting at a predefined origin ( $\gamma(0)=(0,0)$ ) and having length $n:=\ell(\gamma)$. Furthermore, ...
21
votes
2answers
664 views

Random permutations of Z_n

In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1): "Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the ...
2
votes
0answers
277 views

Self-avoiding Walk with next-nearest neighbors

Background I study polymer physics and am doing experiments testing the model outlined in this paper. Basically, the polymers fall into an integer number of pits, and we create a partition function ...
3
votes
1answer
710 views

Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
11
votes
1answer
535 views

Perimeters of random-walk polygons

I have a random walk on $\mathbb{Z}^2$ that takes a step with equal probability in the three directions that avoid retracing the previous step. The walk proceeds until it returns to a lattice point ...
6
votes
2answers
525 views

Optimally directing switches for a random walk

If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want? Formal statement More specifically, ...
7
votes
2answers
496 views

Random walks on graphs: Cover time and blanket time

Winkler and Zuckerman conjectured that the blanket time is within a constant factor of the cover time. The conjecture was recently proved. The cover time $C$ is the expectation of the first time $t$ ...
0
votes
2answers
1k views

Two dimensional brownian motion first passage time

Hello, I am looking for information on how to solve/compute first passage time for two dimensional Brownian motion. any papers, references, books or web links for study will be helpful. thanks ...
4
votes
0answers
396 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 ...
15
votes
4answers
610 views

Sweep-segment bot: Will this random walk sweep the plane?

This model is inspired by the random behavior of the Roomba sweeping robot. Let a unit segment $ab$ in the plane be placed initially with $a=(0,0)$ and $b=(1,0)$. The segment is first rotated a ...
9
votes
5answers
5k views

When do 3D random walks return to their origin?

The probability of a random walk returning to its origin is 1 in two dimensions (2D) but only 34% in three dimensions: This is Pólya's theorem. I have learned that in 2D the condition of returning to ...
0
votes
1answer
815 views

Random walk question on 2D grid, probability of vertical line vs horizontal line hit

Hi, I have a problem (1) where I need to compute the ratio of probabilities of hitting and stopping at a positive vertical barrier x vs hitting and stopping at a negative horizontal barrier y ...
6
votes
2answers
820 views

Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in $\lbrace -1, \frac{1-p}{p} ...
7
votes
3answers
974 views

How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem : On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}. Is there a rule ...
22
votes
1answer
1k views

Random walk inside a random walk inside…

Let $G=(V,E)$ be a graph and consider a random walk on it. Let $G'=(V',E')$ be a subgraph consisting of the vertices and edges that are visited by the random walk. Question 0: Is there a standard ...
10
votes
3answers
1k views

A random walk on random lines

I am wondering if this random walk remains finite with positive probability. Start with three lines $A,B,C$ that are extensions of an equilateral triangle. Let $p_0$ be one corner. Generate a line ...
14
votes
2answers
675 views

self-avoidance time of random walk

How many steps on average does a simple random walk in the plane take before it visits a vertex it's visited before? If an exact formula does not exist (as seems likely), then I'm interested in good ...