Random Walk Randomly Reflected

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 ?

-

How are you measuring distance from the oracle? Is it the Euclidean norm? – Joe Fitzsimons Oct 6 '11 at 6:16
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|$. – Leandro  Oct 6 '11 at 6:54
Thanks for the tag Piotr. – Leandro  Oct 6 '11 at 6:55
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? – Yvan Velenik Oct 6 '11 at 7:21
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. – Leandro  Oct 6 '11 at 12:16

2 Answers

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$.

-

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. – Leandro  Oct 11 '11 at 7:18
@Leandro: No problem. – Joe Fitzsimons Oct 11 '11 at 7:32
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. – Leandro  Oct 12 '11 at 5:09
@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. – Joe Fitzsimons Oct 12 '11 at 6:49
@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. – Ron Maimon Oct 12 '11 at 8:42
show 1 more comment

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$$

Then

$$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.

MORE OF LATER EDIT: Cayley Graph

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 recurrence, and the boundary is exactly at p=1/2. The Cayley graph example shows the approximate strength of constant reflectors--- they counteract exponential growth.

Further, the steady state distribution on the Cayley graph can be analyzed by either merging all the vertices at distance r from the origin into one big vertex, in which case the steady state distribution at zero flux has exponential growth, or by not merging, in which case the steady state distribution at zero flux is constant on all the vertices. The two different descriptions shows clearly that the condition of zero flux at infinity is not just that the steady state distribution decays to zero.

-

1
It would help if you defined $p_k$ in your answer. – Peter Shor Oct 12 '11 at 10:45
@Peter: p_k is the probability of reflection of the k-th concentric sphere (if all the p's are the same, the problem is trivial--- you always get recurrence). I am using Brownian motion, and spherical reflectors, plus a nonzero ratio between the density of the steady-state distribution in the interior and exterior of the sphere. – Ron Maimon Oct 12 '11 at 16:55

2
No, it does. Suppose you choose your $p$ so each sphere is half as dense as the one before it, and you choose $d_n = 2^n$. Then, in the steady state distribution in 3d, the probability that you're in the $k$th sphere is proportional to $4^k$ (8 times the volume, and 1/2 the density of the $k-1$st sphere), which diverges. So there is no steady state distribution. If $d_n$ grows polynomially, you're O.K. – Peter Shor Oct 12 '11 at 17:51

1
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. – Peter Shor Oct 15 '11 at 12:44

1
@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). – Ron Maimon Oct 17 '11 at 20:35
show 5 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 68, "mathjax_display_tex": 10, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.943481981754303, "perplexity_flag": "head"}