Test Limsup Numerically: LIL Simulation

Hey guys! Ever wondered how to actually see the Law of Iterated Logarithm (LIL) in action? I mean, we've all seen the formulas, the theorems, and the proofs, but what about a good ol' numerical simulation? Today, we're diving deep into how to numerically test a limsup, using the Law of Iterated Logarithm as our playground. We'll take a random walk, $S_n$, where the steps are like flipping a coin – heads you go up (+1), tails you go down (-1), each with a 50/50 chance. The Law of Iterated Logarithm is a fascinating concept in probability theory. It helps us understand the long-term behavior of random walks and other stochastic processes. Specifically, it gives us a way to describe the upper limit of how far a random walk will stray from its starting point as time goes to infinity. This might sound a bit abstract, but it has real-world applications in areas like finance, physics, and computer science. To truly grasp its essence, we need to move beyond the theoretical and see it in action. That's where numerical simulation comes in. By simulating a random walk and observing its behavior, we can gain a deeper intuition for what the Law of Iterated Logarithm actually means. Now, you might be thinking, "Limsup? That sounds intimidating!" But trust me, we'll break it down into bite-sized pieces. We'll explore what limsup means in plain English, and then translate that into code. We'll walk through the process of generating a random walk, calculating the relevant quantities, and plotting the results. By the end of this article, you'll not only understand how to numerically test a limsup, but you'll also have a working simulation that you can play with and explore on your own. So, buckle up, and let's get started on this exciting journey into the world of probability and simulation!

Okay, before we jump into the code, let's make sure we're all on the same page about the Law of Iterated Logarithm. The LIL, in a nutshell, tells us how the maximum fluctuations of a random walk grow over time. Imagine our random walk, $S_n$, as a drunkard's stroll. Each step is random, but overall, where does the drunkard tend to wander? The LIL gives us a precise answer. It states that, for our random walk with $\pm 1$ steps, the limsup (that's the limit superior, the largest limit point) of the normalized random walk is equal to 1 with probability 1. Mathematically, it looks like this:

$$\limsup_{n \rightarrow \infty} \frac{S_n}{\sqrt{2n \log \log n}} = 1$$

Woah, math! But don't worry, let's break it down. The $S_n$ is our random walk after $n$ steps. The $\sqrt{2n \log \log n}$ is the crucial scaling factor. It tells us how quickly the typical fluctuations grow. Notice the double logarithm – that's what makes the LIL so subtle and interesting. It grows slower than a single logarithm, but still faster than a constant. Now, the limsup is the trickiest part. It's not just the regular limit, which might not even exist for a random walk (it keeps bouncing around!). Instead, the limsup looks at the largest value the sequence approaches infinitely often. Think of it as the highest peak the random walk keeps revisiting, even as time goes to infinity. So, the LIL is saying that, with probability 1 (meaning almost surely), the largest normalized fluctuation of the random walk will approach 1. This is a much stronger statement than saying the random walk grows like $\sqrt{n}$ – the LIL precisely pins down the largest fluctuations. To truly understand the LIL, it's helpful to contrast it with the simpler Law of Large Numbers and the Central Limit Theorem. The Law of Large Numbers tells us that the average of the steps converges to zero. The Central Limit Theorem tells us that the distribution of $S_n$ (after proper scaling) approaches a normal distribution. But the LIL gives us even finer-grained information about the extremes of the random walk's behavior. This makes it a powerful tool in various fields, from understanding stock market volatility to analyzing the behavior of physical systems. So, with a solid grasp of the LIL under our belts, we're ready to start thinking about how to test it numerically.

Alright, let's get our hands dirty and start coding! The first step in numerically testing the Law of Iterated Logarithm is to simulate a random walk. Remember, our random walk, $S_n$, starts at 0, and at each step, it either goes up by 1 (with probability 1/2) or down by 1 (with probability 1/2). We'll be using Python for this, because it's awesome for numerical stuff and has libraries that make our lives way easier. First, we'll need to import the numpy library, which is the king of numerical computation in Python. We'll also import matplotlib.pyplot for plotting our results, because visualizing the data is super important. Here's the basic setup:

import numpy as np
import matplotlib.pyplot as plt

Now, let's write a function to generate our random walk. This function will take the number of steps, n, as input and return an array containing the cumulative sum of the steps. This array will represent our random walk, $S_n$. Inside the function, we'll use numpy.random.choice to generate a sequence of random steps, either +1 or -1, with equal probability. Then, we'll use numpy.cumsum to calculate the cumulative sum, which gives us the position of the random walk at each step. Here's the code:

def generate_random_walk(n):
 steps = np.random.choice([-1, 1], size=n)
 return np.cumsum(steps)

This function is the heart of our simulation. It efficiently generates a random walk of any length we desire. Now that we have our random walk, we need to calculate the quantity that the Law of Iterated Logarithm talks about: $\frac{S_n}{\sqrt{2n \log \log n}}$. We'll write another function to do this. This function will take the random walk array as input and return an array containing the normalized values. We'll use numpy's element-wise operations to make this calculation efficient. We need to be a bit careful here: the formula involves log log n, and we need to avoid taking the logarithm of 0 or negative numbers. We'll start our calculation from $n=2$ to avoid this issue. Here's the code:

def normalize_random_walk(random_walk):
 n = len(random_walk)
 normalized_walk = np.zeros(n)
 for i in range(2, n):
 normalized_walk[i] = random_walk[i] / np.sqrt(2 * (i + 1) * np.log(np.log(i + 1)))
 return normalized_walk

Notice that we're using i + 1 instead of i inside the loop. This is because Python indexing starts from 0, but we want our n to start from 1. Now we have all the pieces we need to generate and normalize our random walk. We're ready to move on to the next step: numerically estimating the limsup.

Okay, we've got our random walk, we've normalized it, but how do we actually test the Law of Iterated Logarithm? Remember, the LIL talks about the limsup, the largest limit point. We can't calculate the limit as $n$ goes to infinity on a computer (sadly, we don't have infinite time!), so we need to approximate it. A common way to numerically estimate the limsup is to look at the running maximum of the sequence. We calculate the maximum value seen so far, up to each point in the sequence. Then, we see if this running maximum tends to a certain value as $n$ gets large. If the Law of Iterated Logarithm holds, we expect this running maximum to approach 1. Let's write a function to calculate the running maximum of our normalized random walk. We can use numpy.maximum.accumulate to do this efficiently. This function takes an array as input and returns an array of the same size, where each element is the maximum of the elements up to that point in the input array. Here's the code:

def calculate_running_maximum(normalized_walk):
 return np.maximum.accumulate(normalized_walk)

This function is super simple, thanks to numpy! Now, the fun part: putting it all together and plotting the results. We'll generate a long random walk (say, 10,000 steps), normalize it, calculate the running maximum, and then plot both the normalized random walk and its running maximum. This will give us a visual feel for how the limsup behaves. Here's the code to do the plotting:

n = 10000
random_walk = generate_random_walk(n)
normalized_walk = normalize_random_walk(random_walk)
running_maximum = calculate_running_maximum(normalized_walk)

plt.figure(figsize=(12, 6))
plt.plot(normalized_walk, label='Normalized Random Walk')
plt.plot(running_maximum, label='Running Maximum')
plt.xlabel('Step (n)')
plt.ylabel('Value')
plt.title('Numerical Simulation of the Law of Iterated Logarithm')
plt.legend()
plt.grid(True)
plt.show()

When you run this code, you'll see a plot with two lines. The blue line is the normalized random walk, bouncing around like crazy. The orange line is the running maximum, which starts low and gradually increases, but then flattens out as $n$ gets large. If the Law of Iterated Logarithm is doing its thing, you should see the running maximum tending towards 1. But here's a crucial point: it won't exactly reach 1. It'll fluctuate around 1, sometimes going a bit above, sometimes a bit below. This is the nature of the limsup – it's the largest value the sequence approaches infinitely often, not necessarily a value it ever actually reaches and stays at. So, by plotting the running maximum, we get a visual estimate of the limsup. We can see if it's behaving as the Law of Iterated Logarithm predicts. To get an even better estimate, we can run the simulation multiple times and average the running maximums. This will help smooth out the fluctuations and give us a more stable estimate of the limsup. We'll explore that in the next section.

Okay, we've got a single simulation, and we can kind of see the Law of Iterated Logarithm in action. But, as any good scientist (or engineer, or data enthusiast) knows, one run is never enough! To get a more reliable estimate of the limsup, we need to run our simulation multiple times and average the results. This will help smooth out the random fluctuations and give us a clearer picture of the underlying behavior. So, instead of running our simulation just once, we'll run it, say, 100 times. For each run, we'll generate a random walk, normalize it, calculate the running maximum, and then store the running maximum. Finally, we'll average the running maximums across all the runs. This will give us an average running maximum, which should converge more closely to 1 than the running maximum from a single simulation. Let's modify our code to do this. We'll wrap our simulation code in a loop that runs num_simulations times. Inside the loop, we'll generate a random walk, normalize it, and calculate the running maximum, just like before. But instead of plotting the results directly, we'll accumulate the running maximums in an array. After the loop finishes, we'll divide the accumulated running maximums by num_simulations to get the average running maximum. Here's the code:

num_simulations = 100
n = 10000

running_maximums = np.zeros(n)
for _ in range(num_simulations):
 random_walk = generate_random_walk(n)
 normalized_walk = normalize_random_walk(random_walk)
 running_maximums += calculate_running_maximum(normalized_walk)

average_running_maximum = running_maximums / num_simulations

plt.figure(figsize=(12, 6))
plt.plot(average_running_maximum, label='Average Running Maximum ({} simulations)'.format(num_simulations))
plt.xlabel('Step (n)')
plt.ylabel('Value')
plt.title('Numerical Simulation of the Law of Iterated Logarithm')
plt.legend()
plt.grid(True)
plt.show()

Notice how we're using running_maximums += calculate_running_maximum(normalized_walk) to accumulate the running maximums. This is a concise way to add the elements of one array to another in numpy. When you run this code, you'll see a plot of the average running maximum. You should notice that it's much smoother than the running maximum from a single simulation. It should also converge more closely to 1, as the Law of Iterated Logarithm predicts. The more simulations you run, the smoother and more accurate your estimate of the limsup will be. This technique of running multiple simulations and averaging the results is a powerful tool in numerical analysis. It's often used to reduce the variance of an estimate and get a more reliable result. So, we've successfully refined our estimate of the limsup by running multiple simulations. But we can go even further! In the next section, we'll explore some more advanced techniques for analyzing our results and testing the Law of Iterated Logarithm even more rigorously.

We've come a long way! We've simulated a random walk, normalized it, estimated the limsup visually, and refined our estimate by running multiple simulations. But, sometimes, seeing isn't enough. We want to put some numbers on our observations and do some quantitative analysis. How can we measure how close our estimated limsup is to the theoretical value of 1? One way is to look at the final value of the average running maximum. After running many simulations and averaging the results, what's the value of the average running maximum at the very last step? If the Law of Iterated Logarithm is holding up, we expect this value to be close to 1. We can easily extract this value from our average_running_maximum array. It's simply the last element of the array: average_running_maximum[-1]. Let's add this to our code and print it out:

num_simulations = 100
n = 10000

running_maximums = np.zeros(n)
for _ in range(num_simulations):
 random_walk = generate_random_walk(n)
 normalized_walk = normalize_random_walk(random_walk)
 running_maximums += calculate_running_maximum(normalized_walk)

average_running_maximum = running_maximums / num_simulations

plt.figure(figsize=(12, 6))
plt.plot(average_running_maximum, label='Average Running Maximum ({} simulations)'.format(num_simulations))
plt.xlabel('Step (n)')
plt.ylabel('Value')
plt.title('Numerical Simulation of the Law of Iterated Logarithm')
plt.legend()
plt.grid(True)
plt.show()

final_value = average_running_maximum[-1]
print('Final value of average running maximum:', final_value)

Run the code, and you'll see the final value printed in the console. It should be somewhere around 1, but it won't be exactly 1. This is because we're still dealing with a finite number of steps and simulations. Another way to quantify our results is to look at the convergence of the average running maximum. How quickly does it approach 1? Does it fluctuate a lot, or does it converge smoothly? We can get a sense of this by plotting the average running maximum as a function of the number of simulations. We'll run the simulation for an increasing number of simulations and see how the final value changes. This will give us a visual indication of how the estimate converges. Here's the code to do this:

max_simulations = 500
n = 10000

final_values = []
num_simulations_list = range(10, max_simulations + 1, 10)

for num_simulations in num_simulations_list:
 running_maximums = np.zeros(n)
 for _ in range(num_simulations):
 random_walk = generate_random_walk(n)
 normalized_walk = normalize_random_walk(random_walk)
 running_maximums += calculate_running_maximum(normalized_walk)
 average_running_maximum = running_maximums / num_simulations
 final_values.append(average_running_maximum[-1])

plt.figure(figsize=(12, 6))
plt.plot(num_simulations_list, final_values)
plt.xlabel('Number of Simulations')
plt.ylabel('Final Value of Average Running Maximum')
plt.title('Convergence of Limsup Estimate')
plt.grid(True)
plt.show()

This code runs the simulation for different numbers of simulations, from 10 to 500 in steps of 10. It then plots the final value of the average running maximum as a function of the number of simulations. You should see a plot that starts with some fluctuations but then gradually converges towards a value close to 1. This gives us more confidence that our simulation is indeed capturing the behavior predicted by the Law of Iterated Logarithm. So, we've gone beyond visual inspection and used some quantitative measures to analyze our results. We've looked at the final value of the average running maximum and the convergence of the estimate. This gives us a more rigorous understanding of how the Law of Iterated Logarithm manifests in our simulation.

Wow, we've covered a lot of ground! We started with the theoretical concept of the Law of Iterated Logarithm, and we ended up with a working numerical simulation that allows us to see it in action. We learned how to generate a random walk, normalize it, estimate the limsup numerically, and refine our estimate by running multiple simulations. We even delved into some quantitative analysis to measure the convergence of our estimate. Numerically testing a limsup, like the one in the Law of Iterated Logarithm, is a powerful technique. It allows us to bridge the gap between theory and practice, and to gain a deeper intuition for abstract mathematical concepts. By simulating random walks and observing their behavior, we can truly appreciate the subtle and beautiful nature of probability theory. But more generally, the techniques we've learned today – generating random samples, calculating running statistics, averaging over multiple simulations – are widely applicable in many areas of science, engineering, and finance. They're essential tools for anyone working with stochastic processes or complex systems. Remember, the Law of Iterated Logarithm is just one example of a fascinating result in probability theory. There are many other limit theorems and asymptotic results that can be tested numerically. So, I encourage you to take the code we've developed today and adapt it to explore other probabilistic phenomena. Play around with different random walks, different normalizations, different ways of estimating the limsup. The possibilities are endless! And most importantly, have fun! Numerical simulation is a great way to learn, to explore, and to discover new things. So go forth, simulate, and see what you can find!