Arrival Times in Random Environments - Adam Oberman Math

Arrival Times in Random Environments

Motivated by works by probabilists on by Random Walks in Random Environments this note explores what can be learned by Partial Differential equation methods. The main tool is the arrival time:

  • the expected arrival time for the random walk leads to an elliptic Partial differential equation, and
  • the arrival time for the percolation problem leads to a Hamilton-Jacobi equation for the distance on the largest cluster.

Contents

References

Random Walks in a bounded domain

Let U be convex bounded domain in Rn. The expected arrival time of a diffusion, with scalar coefficient a − 1(x), starting from the point x to the boundary is given by the solution of

\frac 1 {a(x)} \Delta u = 1, \quad \text{ in } U
u(x) = 0, \quad \text{ on } \partial U

In the special case of constant coefficient \bar a, and the ball of radius R, the solution is simply u(x) = \bar a d(x,\partial U)^2/2 a quadratic function of the distance to the boundary.

A variable coefficient diffusion can be homogenized by averaging again the invariant measure, see

For complicated operators, we may not get a scalar multiple of the laplacian, but in the current, scalar, setting, we do. Knowing this fact, we can simply extract the homogenized coefficient by solving the least time problem, and setting \bar a = 2u(0)/R^2 which converges in the limit R \to \infty

In general the homogenized operator may be isotropic. Then we would like to find the characteristic ellipsoid, this is more complicated, since we are then dealing with unbounded domains.

Optimal Walks in a domain

Let U be convex bounded domain in Rn. The arrival time from the point x to any point on the boundary, moving at local speed 1/a(x) is given by the solution of

\frac 1 {a(x)} | \nabla u(x)| = 1, \qquad \text{ in } U
u(x) = 0, \qquad \text{ on } \partial U

In the special case where U is the ball of radius R, and a is constant , \bar a the solution is simply

u(x) = \bar a d(x,\partial U)

the distance to the boundary.

In contrast to the random walk case, an isotropic problem can homogenize to an anisotropic operator. See

So we instead solved, in an unbounded domain, the arrival time function,

\frac 1 {a(x)} | \nabla u(x)| = 1, \qquad \text{ in } U
u(0) = 0, \qquad \text{ on } \partial U

Then the isotropic distance function can be approximated values of u on the ball of radius R.

If it was known that homogenized distance was isotropic, we could homogenize by solving for the arrival time to the boundary in the ball or radius R and define

\bar a = u(0)/R

Optimal walk on the largest percolation cluster

Consider a percolation cluster on a grid, and let

C = set of nodes in the largest connected component

We are interested in computing the homogenized distance to the boundary on this cluster, or the homogenized distance to the center point, as a function of p, the probability that nodes are connected.

We are interested in relating this distance to the Euclidean distance. A couple interesting cases are

p = p *

the critical probability. At subcritical probabilities, the problem breaks down, and we can't define a distance. Also, due to the lattice structure,

p = 1

is not the euclidean distance, it is the Manhattan norm distance

d(x,0) = \|x\|_1 = \sum_{i=1}^n |x|_i

For other lattices (e.g. the hex lattice) we get other polyhedral distances.

We expect that the distance is a continuous function of p. We also expect to get nearly isotropic distances when p is further from 1. So some interpolation is possible.

A much cleaner problem

Life would be much simpler if we could design a different percolation cluster where for the range of

p_c \le p \le 1

the distance is a scalar function times the Euclidean distance

d(x,0) = f(p) | x |

Notice that this is the case for the homogenized random walk, (but apparently not for the percolation distance).

It is certainly possible to do this in an approximate way:

  • percolation on a hex lattice has better symmetry
  • we could do percolation on a wide stencil lattice, where the cost to jump is proportional to the distance.

As the stencil gets wider, the distance function gets closer to the Euclidean distance.

It would be even better if there was an analytic function which gave probabilities on the complete graph, decreasing as a function of the distance, and resulted in the distance being a scalar multiple of the euclidean distance.

Random walk on the largest percolation cluster

Consider a percolation cluster on a grid, and let

C = set of nodes in the largest connected component

Now consider a diffusion on C, where the probability of moving from one node to it's neighbors is equal for each neighbor. Call this a random walk on C.

We make the ansatz that the random walk on C converges, in the limit that the size of the underlying grid grows, to an isotropic diffusion on the grid (only on the connected parts, which is a volume fraction).

We are interested in saying this is a diffusion, but only on the largest connected part of the domain. We are unable to use standard homogenization, since it is the topology of C that makes the problem interesting.

Instead, motivated by the results of the previous section, we solve the least time problem to a circle, and read off the coefficient from the solution to the least time problem.

L u = 1, \quad \text{ in } \|x \| < 1 \cap C

where L is the operator with for the weighted diffusion on C

u(x) = 0, \quad \text{ on } \|x \| = 1 \cap C

and the read off the coefficient as before.

The homogenized coefficient is defined to be We are interested in

a(p) = u(0)

where 0 is shorthand for the node at the center of the largest cluster. We are interested in this value as a function of p, the probability of edges connected.

Conjecture

If we have set up the percolation cluster so that we get a multiple of the euclidean distance for the optimal walk, then will we get the same multiple for the random walk?

Retrieved from "http://www.divbyzero.ca/oberman/wiki/Arrival_Times_in_Random_Environments"