• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,064 questions , 2,215 unanswered
5,347 answers , 22,734 comments
1,470 users with positive rep
818 active unimported users
More ...

  Random Walk Randomly Reflected

+ 12 like - 0 dislike

Hi I am not specialist in probability so I will not be surprised if the answer for this question is just a simple consequence of well known results from the random walk theory. In this case, I will be happy if you can tell me the "magic words" to find the material related to this problem.

Let $\sum_{i=1}^n X_i$ a random walk in $\mathbb{Z}^d$ defined in the following way: In each step, the walker look at your current position and as long as its distance to the origin does not belong to the set $\{d_1,d_2,\ldots\}$ ( we assume that $d_n\in\mathbb{N}$ and $d_i<d_{i+1}$ ) it jumps for one of its nearest neighbor with probability $1/2d$. For the other hand if $\|\sum_{i=1}^n X_i\|\in \{d_1,d_2,\ldots\}$ then the walker toss a biased coin if the result is head, which occurs with probability $p$, it goes back to the previous position, that is, $\sum_{i=1}^{n-1} X_i$. If the result is tails it chose randomly one of its neighbors with probability $1/2d$.

I would like to know if there exist a non-trivial $p_c$ such that this random walk is transient for $p<p_c$ in dimension $d=3$. Of course, for this question to be well posed we have to define the sequence $(d_n)$. I would like to chose it randomly but I have no idea for what kind of distribution this problem is tractable. So at this time we can assume that $d_n$ is deterministic sequence and, for example, has a polynomial growth as $d_n=n^2$.

Any references or comments are very welcome.

PS: Could an user with more rep. place random walk tag for this question ?

This post has been migrated from (A51.SE)
asked Oct 6, 2011 in Theoretical Physics by Leandro (155 points) [ no revision ]
retagged Apr 19, 2014 by dimension10
How are you measuring distance from the oracle? Is it the Euclidean norm?

This post has been migrated from (A51.SE)
Hi Joe you right, I should fixed a norm in $\mathbb{Z}^d$. So I will pick the $\ell^1$ norm, that is, $\|(x_1,\ldots,x_d)\|=|x_1|+\ldots+|x_d|$.

This post has been migrated from (A51.SE)
Thanks for the tag Piotr.

This post has been migrated from (A51.SE)
You want your walk to be reflected both when it hits the barrier coming from inside or from outside, or just when coming from inside?

This post has been migrated from (A51.SE)
Good point Velenik. I guess that just inner reflection it was how I initially thought about this problem. But maybe both reflections create more symmetries and helps one give an argument.

This post has been migrated from (A51.SE)

2 Answers

+ 7 like - 0 dislike

If $p=1$ and $d$ is non-empty, then clearly the random walk is not transient, because since you use the $\ell^1$ norm, there is a closed surface which always reflects the walker back into the enclosed finite region. If, however, $p = 0$ then the walk is transient, since simple random walks in 3 dimensions are transient.

Now, if there is a $p_c<1$ its existence is dependent on the specifics of the set $d$. Certainly, there exist some choices for $d$ which are transient: if the set $\{d_n\}$ is finite, then clearly there is a finite probability of ending up outside the final shell (unless $p=1$). Since the random walk on the region external to this shell is transient, then the probability of returning to the interior of the shell infinitely many times is zero, since the shell has a finite boundary, and the probability of returning to a specific site on the boundary site an infinite number of times is zero. Thus $p_c = 1$.

Further in the case where $d_n = n$, then every site is reflective and hence it acts as a random walk on a 3d lattice with a finite probability not to hop for two steps (a hop plus a hop back are the same to simply waiting two time steps), and is hence still transient, unless $p_c = 1$.

Indeed, this seems to be a very general principle (that there is no $p_c < 1$). One way to see why this should be true is to consider what happens when the walker enters the region between $d_i$ and $d_{i+1}$. The walker will be constrained to the region for longer, but this both keeps it from returning to the origin, and from jumping to the next level. When $p$ is extremely high, we expect the walker to have encountered each site within the region roughly an equal number of times before it eventually manages to exit the region. In this case the transition probability is given by the ratio of the surface areas of the two relevant reflecting surfaces, and hence it's probability of jumping to the region between $d_{i+1}$ and $d_{i+2}$ is linearly greater than the probability of jumping back into the region closer to the origin. This is exactly the same probability as we get when we consider the walker to start from a random position within that region when $p=0$. Thus, the reflection term is only increasing the amount of time spent in a region, not the probability of returning to it. At the increase in time spent in a region is constant for fixed $p \neq 1$, the walk remains transient.

Thus I believe there is no choice of $d$ such that $p_c < 1$. Conversely if $p=1$ then the walk is not transient unless $d$ is empty. Lastly, if $d$ is empty, then there is no $p_c$.

This post has been migrated from (A51.SE)
answered Oct 11, 2011 by Joe Fitzsimons (3,575 points) [ no revision ]
Hi Joe thanks for have thought about the problem. I start reading your answer and it seems nice. Anyway I will give you another feedback tomorrow, now it is around 04:00am in Brazil and I need to rest a little bit.

This post has been migrated from (A51.SE)
@Leandro: No problem.

This post has been migrated from (A51.SE)
The fourth paragraph gave me the intuition of what one need for do not have a trivial model. It seems that we have to launch the walker back more than one site. Anyway this requires another question. Thanks Joe.

This post has been migrated from (A51.SE)
@Leandro: No problem. As far as I can see this question actually amounts to a random walk on a weighted graph with a certain structure. The most obvious generalization would be a walk on a weighted directed graph, which would give you the direction dependent reflectors.

This post has been migrated from (A51.SE)
@Leandro: The argument in this answer is using the symmetric reflection condition. You do not need to modify the question. I gave a separate answer.

This post has been migrated from (A51.SE)
@RonMaimon: I have an answer for the asymmetric case too (somewhat different to yours), but it might make more sense to wait for the other question, since it is a completely different argument.

This post has been migrated from (A51.SE)
+ 6 like - 0 dislike

Your walk is always transient when you use the symmetric condition of reflection in both directions, and the argument is essentially given in the previous answer. But when the condition of reflection is asymmetric, so that you have reflection only when you are going out, an infinite number of reflectors will give recurrent behavior for arbitrarily small reflection probability in Euclidean space (LATER EDIT: so long as the $R_k$ do not grow exponentially fast--- in this case, you can have a transition--- you also have a good transition on the Cayley graph).

Electrostatic criterion for recurrence

The recurrence/nonrecurrence of a random walk is a time-independent problem, and can be solved by finding a steady-state solution. This has a simple electrostatic analog, see this answer: http://physics.stackexchange.com/questions/8149/collision-time-of-brownian-particles/14837#14837

The basic principle is as follows: consider a small sphere and a large sphere which absorb Brownian particles. Inject particles at a random position in a sphere of unit radius, and ask what is the probability that they are absorbed by the large sphere as opposed to the small one. Recurrence is when the small sphere always absorbs first, in the limit of an infinite large sphere.

In steady state, the particle density obeys Laplace's equation with the boundary condition that the potential function is zero on the small inner sphere, and on the outer sphere, with a kink on the unit sphere which represents the incoming flux of injected particles.

The flux of particles which are first absorbed at infinity is given by the integrated gradient of the potential (the electric flux) at large distances, and the flux which is first absorbed by the small sphere is given by the gradient of the potential at small distances (the electric flux at small distances). The flux is normalized by the values of the electrostatic potential at the small and large radius (because the potential has to vanish on these two spheres, because they are absorbing).

The upshot of this is that the walk is recurrent if and only if the potential from a small sphere is divergent at infinity (Later edit: this is true for homogenous lattices--- see below). This is true in 1d, where it is linearly divergent, and in 2d, where it is log divergent, but fails in 3d and above, where you approach a constant asymptotic limit at long distances. The constant limit makes the flux at infinity nonzero, because the normalization from the zero potential metal boundary condition is not infinite.

One Way Reflectors

When you add two-way reflectors, the steady state distribution is unchanged, because if you have an infinitesimally thin reflecting plane, in order for there to be zero flux through it, the density of walkers on the left and on the right of the plane have to be equal. This means that the plane does not change the flux, and there is no difference from the no-reflector case. The walk is still transient with two-way reflectors (this is the content of the previous answer).

When you have a one way reflector, however, the condition is different. Now the density on the interior has to be bigger right on the reflector by a ratio of (1/1-p) compared to the exterior to allow the flux through the plane to balance. Call the small ratio $A_p = 1-p$.

In order to have zero flux to infinity in steady state, the distribution of particles with a unit source must have zero r-derivative away from the jumps at the reflectors. This means that all the density falloff must come at the jumps, and the condition that the sphere at infinity is at zero potential gives the restriction:

$$ \prod_k A_{p_k} = \prod (1 - p_k) = 0 $$

When this infinite product is zero the walk is recurrent. When it is not zero, the walk is transient.

EDIT: Or so I thought! The last equation is obviously completely wrong, as pointed out by Peter Shor, and seconded by anonymous downvoters. Thank you for catching the mistake I was blind to.

There is nothing wrong with the method above, it is only that asymptoting to zero potential at large distances does not guarantee that an infinitesimal flux will go to zero at a finite time (this was counterintuitive for me). If you asymptote to zero slowly enough, you can still have a nonzero flux at large radii without ever hitting zero.

The correct condition on the big conductor is that it must have zero flux through it when it is very large. For normal growth rates, to get zero flux, all you need is the potential to go to zero. But for exponentially fast growing $R_k$, to zeroing out the potential on a large sphere, you can still require a nonzero flux even if the sphere starts out at an infinitesimal potential, just because it is so enormously huge (thanks again to Peter Shor for discovering this stupid error--- it does not require a modification to the method, only to the faulty analysis at the very end).

So one asks, given that there is an outward flux $q$, what is the radius of the sphere at which the potential is first zero? If there is no such radius for small enough $q$ (it is allowed to asymptote to zero, so long as it never reaches it--- this was my mistake of before) then the random walk is recurrent.

The outward flux is the electric charge, so the solution going out is of the form

$$ \phi(r) = {q\over r} + A $$

At $R_1$, it is attenuated by $a_1 = 1-p_1$, so that

$$ \phi(R_1) = a_1 ( {q\over r} + A) $$

It continues along for larger r with the same q, but starting at the attenuated height, so that the solution for $r>R_1$ is:

$$ \phi(r) = ({q_1\over r} + A') $$

Where the constant A' is given by

$$ A' = a_1 A + (1-a_1) (- {q\over R_1}) $$

i.e., it is the weighted average of the previous value of A with the negative value in parentheses, with weight given by $a_1$. The q can be factored out if you redefine A multiplicatively to absorb it. The value of A after each of the transitions is given by a similar weighted average

$$ A_{n+1} = a_n A_n + (1-a_n) ( - {1\over R_n} ) $$

This linear difference equation can be solved by standard methods, in particular defining

$$ A_n = B_n \prod_{k=0}^n a_k$$


$$ B_{n+1} - B_n = { (1-a_n)\over \prod_{k=0}^n a_k } ( - {1\over R_n} ) $$

And the condition that A becomes negative after a finite number of steps for arbitrarily small q tells you that the above series is divergent:

$$ \sum_{n=1}^\infty {(1-a_n) \over \prod_{k=0}^n a_k } {1\over R_n} = \infty $$

The divergence of this series is the condition for recurrence. In the special case of constant $a_k = 1-p$, then the series has terms

$$ {p\over (1-p)^n} {1\over R_n} $$

Which is a diverging exponential unless R_n is growing faster than $1\over (1-p)^n$. So for exponentially growing $R_n$, you do get a nontrivial phase transition, contrary to what I wrote initially.


On the Cayley graph (infinite binary tree), instead of 3 space, the problem does have a phase transition in p, because by having every radius be one-way reflecting, and tuning p, you can make the radial walk unbiased after a path-dependent time reparametrization. There is a steady stream outward with probability 2/3, but if p is 1/2, then half of the outgoing 2/3 is brought back on the next step, so that you get a 1/3 probability for going inward, a 1/3 probability for going outward, and a 1/3 probability of coming back after two steps, which is an standard unbiased diffusion after you merge the two steps on the returning path into one.

So for p<1/2 you have transience, and for p>1/2 you have rec

answered Oct 12, 2011 by Ron Maimon (7,730 points) [ no revision ]
Most voted comments show all comments
@PeterShor: this is not correct. The relationship between the steady state distribution and the probability for one particle to be in a given region is nonexistent. The steady state is not normalized. It is just a solution to Laplace's equation which tells you transience, it is not a steady probability distribution for one particle, which doesn't exist already in 1d. Your argument gives that 1d diffusion is transient, in the absence of reflectors.

This post has been migrated from (A51.SE)
@PeterShor: it would help if you said "I was wrong, the answer is correct", because it has been downvoted.

This post has been migrated from (A51.SE)
My argument was indeed total nonsense, but I still think I'm right. The transience of a random walk in 3 and higher dimensions is a fairly robust phenomenon, and should not be spoiled if you put a one-way partially reflecting barrier at positions $2^{2^k}$ for all $k$. Consider the probability that you return to the $k-1$st sphere once you reach the $k+1$st sphere.

This post has been migrated from (A51.SE)
@PeterShor: The clear example is the Cayley graph--- there is a phase transition on this graph. This should clear everything up. I considered the example of fast growing spheres, but these look like planes, and the walk on crossing the k-th sphere many times on these, amplifying their one-way nature, so I dismissed these, but on the Cayley graph, it is obvious that there is a subtlety--- the potential can go to zero without the flux going to zero, if the area of the spheres is growing fast enough (as you said). The correct condition is that the _flux_ is zero at infinity, not the value.

This post has been migrated from (A51.SE)
@PeterShor: Thank you for finding the error, and insisting on your correct intuition. I had the same intuition, but dismissed it, because I could not understand how a decaying solution asymptoting to zero could have a finite flux without crossing zero. The Cayley graph made it obvious that it was possible, and then I see that you were right all along (although your earlier argument was no good, but the intuition was correct).

This post has been migrated from (A51.SE)
Most recent comments show all comments
I am going to disagree with the statement that if all the $p$'s are the same, you always get recurrence. This cannot possibly be true. It will depend on the sequence $d_n$.

This post has been migrated from (A51.SE)
@PeterShor: I originally thought this too, but it doesn't. I am glad somebody noticed that this is counterintuitive!

This post has been migrated from (A51.SE)

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights