11.5 Capacity and transience of random walks

Capacity and transience are key concepts in potential theory, linking mathematical properties of sets to the behavior of random processes. These ideas help us understand how random walks and Brownian motion interact with their environment.

Capacity measures a set's "size" in terms of energy, while transience describes a random walk's tendency to escape to infinity. Together, they reveal deep connections between analysis, probability, and geometry, shedding light on the structure of space and the nature of randomness.

Definition of capacity

• Capacity is a fundamental concept in potential theory that assigns a non-negative number to sets, quantifying their size or significance
• Provides a way to measure the "smallness" or "thinness" of sets in a way that is compatible with the underlying potential-theoretic structure
• Capacity is particularly useful for studying exceptional sets, such as polar sets or sets of zero potential, which may be negligible in terms of other measures like Lebesgue measure

Capacity of a set

Top images from around the web for Capacity of a set

• 

  Potential Energy Diagrams and Stability – University Physics Volume 1 View original

  Is this image relevant?

• 

  Non-Backtracking Random Walks and a Weighted Ihara’s Theorem View original

  Is this image relevant?

• 

  Potential Energy Diagrams and Stability – University Physics Volume 1 View original

  Is this image relevant?

• 

  Non-Backtracking Random Walks and a Weighted Ihara’s Theorem View original

  Is this image relevant?

1 of 2

Top images from around the web for Capacity of a set

• 

  Potential Energy Diagrams and Stability – University Physics Volume 1 View original

  Is this image relevant?

• 

  Non-Backtracking Random Walks and a Weighted Ihara’s Theorem View original

  Is this image relevant?

• 

  Potential Energy Diagrams and Stability – University Physics Volume 1 View original

  Is this image relevant?

• 

  Non-Backtracking Random Walks and a Weighted Ihara’s Theorem View original

  Is this image relevant?

1 of 2

• For a set $E \subset \mathbb{R}^n$, the capacity of $E$, denoted by $\operatorname{cap}(E)$, is defined using the energy integral of a certain class of functions
• The capacity of a set $E$ is given by $\operatorname{cap}(E) = \inf\{\int_{\mathbb{R}^n} |\nabla u|^2 dx : u \in C_c^\infty(\mathbb{R}^n), u \geq 1 \text{ on } E\}$
• Intuitively, the capacity measures how much energy is required to "fill up" the set $E$ with a function that is at least 1 on $E$ and has compact support

Properties of capacity

• Capacity is monotone: if $E_1 \subset E_2$, then $\operatorname{cap}(E_1) \leq \operatorname{cap}(E_2)$
• Capacity is subadditive: for any countable collection of sets $\{E_i\}_{i=1}^\infty$, we have $\operatorname{cap}(\bigcup_{i=1}^\infty E_i) \leq \sum_{i=1}^\infty \operatorname{cap}(E_i)$
• Capacity is translation invariant: for any set $E$ and vector $h \in \mathbb{R}^n$, $\operatorname{cap}(E + h) = \operatorname{cap}(E)$
• Sets of zero capacity, called polar sets, play a crucial role in potential theory as they are often negligible in terms of potential-theoretic properties

Relation to Hausdorff measure

• Capacity and Hausdorff measure are both ways to quantify the size of sets, but they capture different aspects of the set's structure
• While Hausdorff measure is a geometric measure that depends on the set's local dimension, capacity is an analytic concept that is more closely related to the underlying potential theory

Hausdorff measure vs capacity

• Hausdorff measure $\mathcal{H}^s(E)$ depends on a parameter $s$, which represents the dimension, and is defined using coverings of the set $E$ by small balls
• Capacity $\operatorname{cap}(E)$ is defined using the energy integral of functions and does not directly depend on a dimension parameter
• In some cases, sets of zero $s$-dimensional Hausdorff measure may have positive capacity, and vice versa, highlighting the difference between these two concepts

Criteria for positive capacity

• A set $E$ has positive capacity if and only if there exists a non-zero positive measure $\mu$ supported on $E$ such that the energy integral $\int_E \int_E \frac{d\mu(x) d\mu(y)}{|x-y|^{n-2}}$ is finite
• For compact sets $K \subset \mathbb{R}^n$, $\operatorname{cap}(K) > 0$ if and only if there exists a non-zero positive measure $\mu$ supported on $K$ such that the potential $U^\mu(x) = \int_K \frac{d\mu(y)}{|x-y|^{n-2}}$ is bounded on $K$
• These criteria provide a way to determine whether a set has positive capacity by constructing an appropriate measure supported on the set

Capacity and hitting probabilities

• Capacity is closely related to the concept of hitting probabilities in stochastic processes, particularly for Brownian motion and random walks
• The hitting probability of a set $E$ by a stochastic process $X_t$ is the probability that the process visits the set $E$ at some time $t > 0$

Hitting probabilities of sets

• For a set $E \subset \mathbb{R}^n$ and a stochastic process $X_t$ starting at $x \in \mathbb{R}^n$, the hitting probability of $E$ by $X_t$ is defined as $\mathbb{P}_x(X_t \in E \text{ for some } t > 0)$
• Hitting probabilities provide a way to quantify the likelihood that a stochastic process will visit a given set
• The behavior of hitting probabilities is closely related to the potential-theoretic properties of the set, such as its capacity

Capacity and hitting probability

• For Brownian motion $B_t$ starting at $x \in \mathbb{R}^n$, the hitting probability of a compact set $K$ is related to its capacity by the formula $\mathbb{P}_x(B_t \in K \text{ for some } t > 0) = \frac{U^{\mu_K}(x)}{U^{\mu_K}(\infty)}$, where $\mu_K$ is the equilibrium measure of $K$
• Sets of zero capacity are almost surely never hit by Brownian motion, while sets of positive capacity have a positive hitting probability
• The relationship between capacity and hitting probabilities provides a bridge between potential theory and stochastic processes, allowing for the study of exceptional sets and their role in the behavior of stochastic processes

Wiener criterion

• The Wiener criterion is a fundamental result in potential theory that provides a necessary and sufficient condition for a set to be of zero capacity in terms of the behavior of Newtonian potentials near the set
• It is named after Norbert Wiener, who introduced the criterion in his work on potential theory and harmonic analysis

Statement of Wiener criterion

• Let $E \subset \mathbb{R}^n$ be a compact set and $x_0 \in E$. Then $E$ has zero capacity if and only if $\int_0^1 \frac{\operatorname{cap}(E \cap B(x_0, r))}{r^{n-1}} dr = \infty$
• The Wiener criterion relates the capacity of a set to the behavior of the capacities of its intersections with small balls around a point in the set
• Intuitively, the criterion states that a set has zero capacity if and only if its "density" of capacity near a point is sufficiently high

Applications of Wiener criterion

• The Wiener criterion is a powerful tool for determining whether a set has zero capacity, as it reduces the problem to studying the behavior of capacities of intersections with small balls
• It is particularly useful for studying the capacity of sets that are defined in terms of the behavior of functions near a point, such as the set of non-Lebesgue points of a function
• The Wiener criterion has applications in various areas of analysis, including harmonic analysis, partial differential equations, and geometric measure theory, where it is used to study the regularity of solutions and the structure of exceptional sets

Equilibrium potential

• The equilibrium potential is a fundamental concept in potential theory that is closely related to the capacity of a set and the behavior of potentials on the set
• It provides a way to construct a canonical potential that is equal to 1 on the set and harmonic outside the set

Definition of equilibrium potential

• For a compact set $K \subset \mathbb{R}^n$, the equilibrium potential of $K$ is the unique function $u_K$ that satisfies the following properties:
  1. $u_K$ is harmonic on $\mathbb{R}^n \setminus K$
  2. $u_K = 1$ on $K$ (in the sense of Perron-Wiener-Brelot solution)
  3. $u_K(x) \to 0$ as $|x| \to \infty$
• The equilibrium potential can be expressed in terms of the equilibrium measure $\mu_K$ of $K$ as $u_K(x) = \int_K \frac{d\mu_K(y)}{|x-y|^{n-2}}$

Properties of equilibrium potential

• The equilibrium potential is superharmonic on $\mathbb{R}^n$ and harmonic on $\mathbb{R}^n \setminus K$
• The capacity of $K$ is equal to the total mass of the equilibrium measure: $\operatorname{cap}(K) = \mu_K(K)$
• The equilibrium potential minimizes the energy integral among all potentials that are at least 1 on $K$: $\int_{\mathbb{R}^n} |\nabla u_K|^2 dx = \operatorname{cap}(K)$
• The level sets of the equilibrium potential, $\{x : u_K(x) > t\}$ for $0 < t < 1$, can be used to study the fine properties of the set $K$ and its capacity

Transience of random walks

• Transience is a fundamental property of random walks that describes the long-term behavior of the walk and its tendency to escape to infinity
• The study of transience is central to understanding the global structure of random walks and their interaction with the underlying space

Definition of transience

• A random walk $(S_n)_{n \geq 0}$ on a graph or a metric space is called transient if the probability that the walk visits any fixed point infinitely often is zero
• Equivalently, a random walk is transient if it almost surely escapes to infinity, i.e., $\lim_{n \to \infty} d(S_n, S_0) = \infty$ with probability 1, where $d$ is the graph distance or the metric
• Transience is a global property that depends on the large-scale structure of the space and the transition probabilities of the random walk

Criteria for transience

• A random walk on a graph is transient if and only if the Green's function $G(x, y) = \sum_{n=0}^\infty P^n(x, y)$ is finite for some (and hence all) $x, y$, where $P^n(x, y)$ is the $n$-step transition probability from $x$ to $y$
• For random walks on $\mathbb{Z}^d$, the walk is transient if and only if $d \geq 3$, while for $d = 1, 2$, the walk is recurrent (i.e., not transient)
• The transience of a random walk can also be characterized by the capacity of certain sets, such as the capacity of the complement of the range of the walk

Transience in different dimensions

• The transience of random walks depends crucially on the dimension of the underlying space
• In dimensions $d \geq 3$, random walks are typically transient, as the space is "large enough" for the walk to escape to infinity without returning to its starting point
• In dimensions $d = 1, 2$, random walks are typically recurrent, as the space is "too small" for the walk to escape without frequently returning to its starting point
• The difference in transience between low and high dimensions reflects the fundamental role of dimension in the global structure of random walks

Capacity and transience

• The concepts of capacity and transience are closely related, as the capacity of certain sets can be used to characterize the transience of random walks
• In particular, the capacity of the complement of the range of a random walk determines whether the walk is transient or recurrent

Capacity of visited sites

• For a random walk $(S_n)_{n \geq 0}$ on a graph or a metric space, the range of the walk is the set of all visited sites, i.e., $\mathcal{R} = \{S_n : n \geq 0\}$
• The capacity of the complement of the range, $\operatorname{cap}(\mathcal{R}^c)$, provides information about the transience of the walk
• If $\operatorname{cap}(\mathcal{R}^c) > 0$, then the walk is transient, as it implies that the walk has a positive probability of escaping to infinity without returning to the visited sites

Relation between capacity and transience

• A random walk $(S_n)_{n \geq 0}$ on a graph or a metric space is transient if and only if the capacity of the complement of its range is positive, i.e., $\operatorname{cap}(\mathcal{R}^c) > 0$
• This characterization provides a direct link between the potential-theoretic concept of capacity and the probabilistic notion of transience
• The capacity of the complement of the range can be used to study the fine properties of transient random walks, such as the rate of escape to infinity and the distribution of the visited sites

Capacity of the range of transient walks

• For transient random walks, the capacity of the range itself, $\operatorname{cap}(\mathcal{R})$, is also of interest
• In many cases, the range of a transient walk has zero capacity, indicating that the walk visits a "small" set of sites despite escaping to infinity
• The capacity of the range can provide insights into the local structure of transient walks and the distribution of the visited sites
• In some cases, such as for random walks on certain fractals, the range may have positive capacity, reflecting the presence of a "large" set of visited sites

Pólya's theorem

• Pólya's theorem is a classic result in the theory of random walks that characterizes the transience of simple random walks on $\mathbb{Z}^d$ in terms of the dimension $d$
• The theorem is named after George Pólya, who proved the result in 1921, establishing a fundamental connection between the dimension of the lattice and the long-term behavior of random walks

Statement of Pólya's theorem

• Let $(S_n)_{n \geq 0}$ be a simple random walk on $\mathbb{Z}^d$, i.e., a random walk that jumps to one of the $2d$ nearest neighbors with equal probability at each step. Then:
  1. For $d = 1, 2$, the walk is recurrent: $\mathbb{P}(S_n = 0 \text{ for infinitely many } n) = 1$
  2. For $d \geq 3$, the walk is transient: $\mathbb{P}(S_n = 0 \text{ for infinitely many } n) = 0$
• Pólya's theorem shows that the transience of simple random walks depends crucially on the dimension of the lattice, with a sharp transition from recurrence to transience occurring at $d = 3$

Proof of Pólya's theorem

• The proof of Pólya's theorem relies on the analysis of the Green's function $G(x, y) = \sum_{n=0}^\infty P^n(x, y)$, where $P^n(x, y)$ is the $n$-step transition probability from $x$ to $y$
• For $d = 1, 2$, the Green's function is infinite for all $x, y$, implying that the walk is recurrent
• For $d \geq 3$, the Green's function is finite for all $x, y$, implying that the walk is transient
• The proof involves estimating the asymptotic behavior of the transition probabilities $P^n(x, y)$ using Fourier analysis and the local central limit theorem

Consequences of Pólya's theorem

• Pólya's theorem has far-reaching consequences in the theory of random walks and related areas of probability and potential theory
• The theorem provides a complete classification of the transience of simple random walks on $\mathbb{Z}^d$, serving as a starting point for the study of more general random walks and stochastic processes
• The recurrence of simple random walks in dimensions $d = 1, 2$ has important implications for the study of two-dimensional statistical physics models, such as the Ising model and percolation
• The transience of simple random walks in dimensions $d \geq 3$ is closely related to the behavior of Brownian motion and the potential theory of the Laplace operator in higher dimensions

Capacity of Brownian motion

• Brownian motion is a continuous-time stochastic process that plays a central role in probability theory and its applications
• The capacity of sets related to Brownian motion, such as the capacity of Brownian paths and the capacity of the Brownian range, provide important insights into the fine properties of the process

Brownian motion and capacity

• Brownian motion $(B_t)_{t \geq 0}$ in $\mathbb{R}^d$ is a continuous-time stochastic process with independent, stationary increments and paths that are almost surely continuous
• The capacity of sets related to Brownian motion, such as the