Can the Hurst Exponent Be Used to Detect Levy Flights in Random Walks?
A Project Summary for CVEN-6833 Fall Semester 2005
Nate Bradley
Submitted Dec. 19, 2006
The Hurst Exponent (H) is a measure of the degree of randomness in a time series. H ranges between zero and one. A value of one-half indicates that the steps in a time series are completely independent of one another. The auto-correlation function for a random time series decays exponentially. Values greater than one-half indicate that there is some long-term auto-correlation in the time series. The auto-correlation function for these data has a very heavy-tailed, power law decay, suggesting that the effect of an event in the time series can be felt long after the event ends. Time series displaying long-term correlation generally appear smoother, with fewer abrupt changes of direction. Hurst exponents with values greater than one-half have been observed in geophysical time series, suggesting that these processes are less random than they may appear. An example of two long-memory time series can be seen in slide 8 of my presentation where I show my estimation of the Hurst exponent for suspended sediment concentrations in the Colorado and Mississippi Rivers.
The motivation for examining the Hurst exponent as a tool for analyzing random walks in this project comes from my research on sediment dispersion. In it’s simplest form, the question we wish to answer is “Can the motion of a sudden input of sediment to a river be described mathematically as a dispersive process?” We think there is reason to believe that the answer to this question is a conditional “no.” In some fluvial systems, we suspect that sediment doesn’t disperse according to the classic Fickian advection-diffusion equation, but instead moves according to a fractional order differential equation. Such behavior is known as anomalous diffusion. In the geophysical realm, anomalous diffusion has been observed in the transport of pollutants in groundwater (see Benson et al. 2001, Fraction Dispersion, Levy Motion and the MADE Tracer Tests). We suspect that some fluvial systems may exhibit anomalous dispersion because some sediment grains may become trapped for very long periods of time.
It is reasonable to ask why a few grains of sediment becoming trapped for long periods of time can lead to anomalous dispersion and what all this has to do with random walks and the Hurst exponent anyways. Many dispersive processes have been successfully modeled using the Continuous Time Random Walk (CTRW) framework. In this model, particle is either in motion or it is at rest. The travel distance for an episode of motion and duration of a rest are governed by probability density functions (PDFs). When both PDFs have finite first and second moments, particle motion is Fickian. Another way to put this is that when the probability of an extremely long step or an extremely long rest is sufficiently low, the resulting motion is normal dispersion. But when either or both PDFs of motion are heavy-tailed, meaning that a long hop or rest is so likely that first and/or second moments diverge, the resulting motion cannot be described as Fickian.
The classic tool for identifying the nature of dispersion is the scaling of the second moment of the spatial distribution with time. This is easiest to understand in terms of an example. Let’s imagine a computer simulation where 10,000 particles each take their own random walks and we measure the mean square displacement (or the related quantity, the variance) of the position of all particles at each time step. The variance will grow with time as the particle spread out and the slope of the variance vs. time plot in log-log space indicates the mode of dispersion. This plot for normal, Fickian dispersion will have a slope of 1. Any other scaling of the variance with time indicates anomalous dispersion.
When I first worked on this project in the fall of 2005, I was only considering the effect of heavy-tailed hop length distribution on the nature of sediment dispersion and for a variety of reasons, many related to my poor understanding of the topic, I was having difficulty using only the scaling of the variance as the indicator of dispersion. Random walks governed by heavy-tailed hop length distributions are called Levy Flights. In a Levy Flight, the position of the particle is dominated by the rare, long hop. Particles tend to mull about in nearly the same place, taking small steps here and there but occasionally a particularly large hop is drawn from the travel distance distribution moving the particle to a completely different place, where it is likely to remain for a while. An example of a Levy Flight random walk can be seen on slide 5 of my presentation. Since the time series of particle position is dominated by long hops, it seemed reasonable to suspect that the type of random walks that lead to anomalous dispersion, those governed by a heavy-tailed distribution of hop lengths, might display a Hurst Exponent greater than one-half. If so, the Hurst exponent could be another tool for detecting anomalous dispersion.
To this end, I developed a Matlab function to estimate the Hurst exponent for a time series based on the rescaled range algorithm as described in Bras and Rodriguez-Iturbe (Random Functions in Hydrology) and notes generously provided to me by Balaji. The algorithm is outlined on slide 9 of the presentation, so I will merely summarize it here. The rescaled range is essentially the minimum and maximum values of the cumulative departure from the mean, measured over different size subsets of the data. When plotted in log-log space, the slope of a line fit to the rescaled range measurements is an estimation of the Hurst exponent.
I performed twenty trials each of two different kinds of random walk simulations. In each, the particle moved 5000 randomly chosen steps, but one was governed by a normal distribution of hop lengths and the other governed by a power law distribution so heavy-tailed that the first and second moments diverge. I computed the rescaled range of the particle position time series for each trial, plotted all the results in log-log space, and fit a line to the data. The slope of the least squares linear fit is my estimate of the Hurst exponent. The results are shown in slide 11 of my presentation. As expected, the random walk governed by the normal distribution has Hurst exponent close to one-half, as we expect for normal dispersion. Unfortunately, the Levy Flight random walks also have a Hurst exponent of one-half. This result was unexpected. My explanation at the time was that the rescaled range contains the standard deviation of the data in the denominator, which for anomalous super-dispersion grows as time to a power greater than one-half (standard deviation is the square root of variance, which will scale faster than linearly). This may or may not be correct. I still suspect that anomalous dispersion should exhibit a Hurst exponent other than one-half.
Since completing this project, I have found another, even more compelling reason to be interested in the Hurst exponent. I have lately been focusing on the role of the resting time PDF in sediment dispersion. As mentioned previously, heavy-tailed PDFs of resting time, those where long rests are sufficiently likely that either or both of the first two moments of the PDF diverge, can also cause anomalous dispersion. Since grains can become trapped in sedimentary deposits for extremely long periods of time, it seems possible that the distribution of times between episodes of entrainment might be heavy tailed. Unfortunately, the residence time distribution for fluvial sediment is extremely difficult to measure. The age distribution of sediment can sometimes be measured by dating trees in a flood plain or radiocarbon dating of organic material in sediment (see Dietrich et al. 1982 Construction of Sediment Budgets for Drainage Basins and Lancaster, 2006 Debris-Flow Deposition, Valley Storage, and Fluvial Evacuation in Headwater Valleys (AGU Poster)), but the relationship between the age and the ultimate residence time distribution is not always clear. It is typically assumed that all particles in the flood plain have an equal probability of erosion, leading to an exponential distribution of residence times, but this assumption is clearly not always correct.
Because measuring the residence time is difficult we have developed a model for the residence time distribution in a simple system based on the mathematical concept of Gambler’s Ruin. A randomly fluctuating process that ends when its value reaches zero is a Gambler’s Ruin process and the PDF of times to ruin for is given by where H is the Hurst Exponent of the randomly fluctuating process. This distribution of return times is interesting because for all values of H, it has divergent first and second moments.
In our model, a meandering stream moves by cut bank erosion and point bar deposition with no net aggradation or incision. The randomly fluctuating quantity is the distance of a particle from the channel. When the particle’s distance from the channel reaches zero, it is eroded. Another way to look at it is that the channel is taking a random walk across the flood plain, but the origin is fixed on the meandering channel. From the frame of reference of the channel the stationary particles in sedimentary deposits are taking a random walk. If a Hurst exponent can describe the random walk of the channel, this model makes a prediction of the residence time distribution of fluvial sediment that is at odds with what others have assumed and should lead to anomalous dispersion if the CTRW framework is appropriate for describing the motion of fluvial sediment. One of the things we hope to do soon is to estimate the Hurst exponent of meandering channel motion.