Lyapunov Function Proof Transience Simple Symmetric Random Walk In 3D

Jul 24, 2025 by JurnalWarga.com 70 views

Lyapunov Function Proof of Transience for Simple Symmetric Random Walk in Three Dimensions

Introduction

The simple symmetric random walk (SSRW) is a fundamental concept in probability theory, describing a process where a particle moves randomly on a lattice. A key property of SSRWs is their behavior in different dimensions. Specifically, SSRWs are recurrent in dimensions 1 and 2, meaning the particle will return to its starting point with probability 1. However, in dimensions 3 and higher, SSRWs are transient, implying there's a non-zero probability the particle will never return to its starting point. Guys, understanding this difference is crucial in many areas, from physics to finance! This article dives deep into the fascinating world of proving the transience of SSRWs in three dimensions, focusing on the elegant approach using Lyapunov functions. We'll explore how Lyapunov functions provide a powerful tool for demonstrating stability or, in this case, instability (transience) in stochastic systems.

The transience of the simple symmetric random walk in three dimensions is a well-established result, but the proofs can sometimes feel a bit abstract. The aim here is to make things clearer by exploring the use of Lyapunov functions. These functions act like energy functions in physics, providing a way to understand the long-term behavior of the walk. If we can find a Lyapunov function that tends to increase as the walk moves away from the origin, that's strong evidence for transience. We'll break down the concepts, the math, and the intuition behind this approach, making it accessible and, dare I say, even fun! So, buckle up, and let's get started on this exciting journey into the world of random walks and Lyapunov functions.

Why are we focusing on Lyapunov functions? Well, they offer a particularly insightful way to prove transience. Instead of directly calculating probabilities of return, we'll construct a function that reflects the "distance" of the walk from the origin. By showing that this function tends to increase on average, we can demonstrate that the walk drifts away from the origin and is therefore transient. It's like showing that a ball rolling on a hill will eventually roll off the edge – a powerful and intuitive analogy. This approach not only gives us a proof but also provides a deeper understanding of why transience occurs in higher dimensions. We'll be using tools from stochastic processes and real analysis, but don't worry if those terms sound intimidating; we'll explain everything along the way. By the end of this article, you'll have a solid grasp of how Lyapunov functions can be used to prove transience and a newfound appreciation for the elegance of this mathematical technique. Remember, guys, math isn't just about formulas; it's about understanding the underlying principles and seeing how they connect to the world around us.

What is a Simple Symmetric Random Walk?

Let's start with the basics. A simple symmetric random walk in d dimensions is a sequence of random steps taken on a d-dimensional lattice. Imagine a particle starting at the origin. At each time step, the particle moves one unit in a randomly chosen direction along one of the coordinate axes. In a symmetric walk, each direction is chosen with equal probability. For example, in three dimensions, there are six possible moves: one unit in the positive or negative x, y, or z direction. Each of these moves has a probability of 1/6.

To be more precise, let's define the walk mathematically. Let X_n represent the position of the particle at time n. The walk starts at the origin, so X_0 = 0. Each step is determined by a random vector Z_i, which can take on values like (±1, 0, 0), (0, ±1, 0), and (0, 0, ±1) in three dimensions, each with probability 1/6. The position at time n is then given by the sum of these random steps:

X_n = Z_1 + Z_2 + ... + Z_n

The key here is the "symmetric" part. The probabilities of moving in opposite directions are equal. This symmetry is crucial for many of the properties of the walk, including its recurrence or transience. Now, let's talk about what recurrence and transience actually mean.

Recurrence and transience describe the long-term behavior of the walk. A walk is recurrent if it returns to its starting point infinitely often with probability 1. Think of it like a wandering soul that always finds its way back home. On the other hand, a walk is transient if there's a non-zero probability that it will never return to its starting point. It's like a traveler who sets off on a journey and never looks back. The classic result is that SSRWs in 1 and 2 dimensions are recurrent, while those in 3 or more dimensions are transient. This difference in behavior is quite remarkable and has deep connections to the geometry of the space the walk is taking place in. Understanding this dichotomy is essential for grasping the significance of proving transience in three dimensions. Guys, it's like the walk has enough space to get lost in three dimensions, but it's too confined in lower dimensions to avoid coming back!

Lyapunov Functions: A Tool for Analyzing Stochastic Systems

Now, let's introduce the star of our show: Lyapunov functions. These are powerful tools for analyzing the stability of dynamic systems, both deterministic and stochastic. In our context, we'll use them to show the "instability" of the SSRW in the sense that it tends to move away from the origin.

A Lyapunov function is essentially a scalar function that provides information about the "energy" or "distance" of a system from a particular state. For a deterministic system, if we can find a function that decreases along trajectories of the system, we can conclude that the system is stable, meaning it tends to stay near a certain point. For stochastic systems, like our random walk, we look for a function that decreases in expectation. However, to prove transience, we'll be looking for a function that increases in expectation as the walk moves away from the origin.

Formally, let's say we have a stochastic process X_n. A Lyapunov function V(x) is a real-valued function that satisfies certain properties. The key property for our purposes is the expected change in V:

E[V(X_{n+1}) − V(X_n) | X_n = x]

If this expected change is positive for large |x|, it suggests that the walk is drifting away from the origin. This is the core idea behind using Lyapunov functions to prove transience. We want to find a function V(x) that measures the distance from the origin in some sense and show that this distance tends to increase as the walk progresses.

The beauty of Lyapunov functions lies in their flexibility. There isn't a single "correct" Lyapunov function for a given problem. Instead, we have the freedom to choose a function that suits our needs. For the SSRW in three dimensions, a common choice is a function related to the inverse of the distance from the origin. This function will decrease as the walk moves further away, and we'll show that, on average, the walk does indeed move further away. It's like we're creating a potential field that pushes the walk outwards. Guys, the trick is to find just the right function that captures the essential behavior of the walk!

Constructing a Lyapunov Function for the 3D SSRW

Okay, let's get down to the nitty-gritty. To prove the transience of the 3D SSRW using a Lyapunov function, we need to construct a suitable function V(x). As mentioned earlier, a common choice is a function related to the inverse of the distance from the origin. This is because we expect the walk to drift away from the origin, so the inverse distance should, on average, decrease over time. Thus, the Lyapunov function itself, which we want to show increases in expectation, will be related to the negative of the inverse distance.

Let x = (x_1, x_2, x_3) be a point in three-dimensional space. Define the Euclidean norm (distance from the origin) as:

|x| = √(x_1^2 + x_2^2 + x_3^2)

Now, let's consider a candidate Lyapunov function of the form:

V(x) = 1/|x|

This function decreases as the distance from the origin increases, which is what we want to exploit. However, to make the math work out nicely, we'll actually use a modified version of this function. We'll consider V(x) = 1/r, where r is a "smoothed" version of the distance. Specifically, we define:

r = √(|x|^2 + a^2)

where a is a positive constant. This smoothing is important because it avoids any singularities when the walk is near the origin. It's like putting a little cushion around the origin so the function doesn't blow up. Now, our Lyapunov function becomes:

V(x) = 1/√(|x|^2 + a^2)

This is the function we'll work with. Our goal is to show that the expected change in this function is positive for large |x|. This will demonstrate that the walk tends to move away from the origin and is therefore transient. The next step involves calculating the expected change, which requires some careful calculations involving the steps of the random walk and the properties of our chosen Lyapunov function. It might sound a bit daunting, but we'll break it down step by step, guys! The key is to remember that we're trying to show that, on average, the walk is moving further away from its starting point.

Calculating the Expected Change in the Lyapunov Function

Now comes the crucial part: calculating the expected change in our Lyapunov function. This will involve some Taylor series expansions and careful approximations, but don't worry, we'll take it slow and explain each step. Remember, our goal is to show that E[V(X_{n+1}) − V(X_n) | X_n = x] is positive for large |x|, where V(x) = 1/√(|x|^2 + a^2).

Let X_n = x, and let Z be the random step taken at time n + 1. In three dimensions, Z can take on six values: (±1, 0, 0), (0, ±1, 0), and (0, 0, ±1), each with probability 1/6. Then, X_{n+1} = x + Z. The expected change in V is:

E[V(X_{n+1}) − V(X_n) | X_n = x] = E[V(x + Z) − V(x)]

To calculate this expectation, we need to consider each possible step Z and its corresponding probability. This is where the Taylor series expansion comes in handy. We'll expand V(x + Z) around x using a Taylor series up to the second order:

V(x + Z) ≈ V(x) + ∇V(x) ⋅ Z + (1/2) Z^T H(x) Z

where ∇V(x) is the gradient of V and H(x) is the Hessian matrix of V. Now, we can plug this approximation into our expectation:

E[V(x + Z) − V(x)] ≈ E[∇V(x) ⋅ Z + (1/2) Z^T H(x) Z]

Since the walk is symmetric, the expected value of Z is zero, so the first term vanishes:

E[∇V(x) ⋅ Z] = ∇V(x) ⋅ E[Z] = 0

This leaves us with the second term, which involves the Hessian matrix. The Hessian matrix consists of second-order partial derivatives of V. Calculating these derivatives for our chosen V(x) is a bit tedious but straightforward. After doing the math, we find that the trace of the Hessian is:

Tr(H(x)) = ∂^{2*V*/∂*x_1*}2 + ∂^{2*V*/∂*x_2*}2 + ∂^{2*V*/∂*x_3*}2 = (2*|x|^2 − 3a^2) / (|x|^2 + a^2*)(5/2)

Now, we can compute the expected value of the second term. Since each component of Z is either ±1 with probability 1/6, we have:

E[(1/2) Z^T H(x) Z] = (1/12) Tr(H(x))

Plugging in our expression for the trace of the Hessian, we get:

E[V(X_{n+1}) − V(X_n) | X_n = x] ≈ (1/12) (2*|x|^2 − 3a^2) / (|x|^2 + a^2*)(5/2)

This is a crucial result! We see that for large |x|, the term 2*|x|^2 dominates, and the expected change is positive. Guys, this is exactly what we wanted to show! It means that, on average, our Lyapunov function V(x) is increasing as the walk moves away from the origin.

Proving Transience from the Positive Expected Change

Now that we've calculated the expected change in our Lyapunov function and shown that it's positive for large |x|, we're in the home stretch. We need to connect this result to the transience of the random walk. Remember, transience means there's a non-zero probability that the walk will never return to the origin.

From our calculation, we have:

E[V(X_{n+1}) − V(X_n) | X_n = x] ≈ (1/12) (2*|x|^2 − 3a^2) / (|x|^2 + a^2*)(5/2)

For large |x|, this is approximately (1/12) (2/|x|^3), which is positive. This tells us that, on average, V(X_n) tends to increase as the walk moves further from the origin. But how does this translate into a proof of transience?

Let's consider a large sphere centered at the origin with radius R. If the walk is recurrent, it must return to this sphere infinitely often. However, our positive expected change in V suggests that the walk tends to move outwards, away from the sphere. To make this rigorous, we can use a supermartingale argument.

Let's define a stopped process Y_n = V(X_n) ∧ M, where M is a large constant and ∧ denotes the minimum. This process is bounded above by M. Now, consider the stopped process until the walk exits the sphere of radius R. Let τ be the first time |X_n| > R. Then, for n < τ, we have:

E[V(X_{n+1}) − V(X_n) | X_n = x] > c/|x|^3

for some positive constant c, provided |x| is large enough. This implies that V(X_n)* is a submartingale outside the sphere of radius R. By carefully applying the optional stopping theorem and taking limits, we can show that the probability of the walk staying bounded is less than 1. This is a bit technical, but the main idea is that the positive drift of V(X_n)* pushes the walk away from the origin with a non-zero probability.

The intuition here is that if the expected change in V is positive, the walk is biased to move outwards. This outward bias makes it less likely that the walk will return to the origin, thus proving transience. Guys, this is the heart of the proof! We've taken a potentially complex problem and broken it down into manageable steps using the power of Lyapunov functions.

Conclusion

In this article, we've explored the concept of transience in the simple symmetric random walk in three dimensions and, more importantly, how to prove it using a Lyapunov function. We started by defining the SSRW and the notions of recurrence and transience. Then, we introduced Lyapunov functions as a tool for analyzing stochastic systems and showed how they can be used to demonstrate transience. We carefully constructed a suitable Lyapunov function, calculated the expected change, and showed that it's positive for large distances from the origin. Finally, we outlined how this positive expected change leads to a proof of transience.

The use of Lyapunov functions provides a powerful and elegant way to understand the behavior of random walks. It allows us to move beyond direct probability calculations and gain a deeper insight into the underlying dynamics of the system. The key takeaway is that by finding a function that captures the "energy" or "distance" from a particular state and analyzing its expected change, we can draw conclusions about the long-term behavior of the system. Guys, this approach is not limited to random walks; it can be applied to a wide range of stochastic processes and dynamical systems.

This journey into the world of random walks and Lyapunov functions has hopefully given you a new perspective on how mathematical tools can be used to solve interesting problems. The transience of the 3D SSRW is just one example, but the principles we've discussed are applicable in many other areas of mathematics, physics, and engineering. Keep exploring, keep questioning, and keep applying these powerful techniques to unravel the mysteries of the world around us!

Keywords Repair

Original Keyword: Is there a Lyapunov function proof of transience for the simple symmetric random walk in three dimensions?
Revised Keyword: How can a Lyapunov function be used to prove the transience of a simple symmetric random walk in three dimensions?