Calculating the Lyapunov Exponent of a Time Series (with python code)

(In a later post I discuss a cleaner way to calculate the Lyapunov exponent for maps and particularly the logistic map, along with Mathematica code.)
I found this method during my Masters while recreating the results of an interesting paper on how some standard tests for chaos fail to distinguish chaos from stochasticity (Stochastic neural network model for spontaneous bursting in hippocampal slices, Biswal and Dasgupta, 2002).
Procedure
The Lyapunov exponent is a measure of sensitive dependence on initial conditions, i.e. how quickly two nearby states diverge.
Now consider two points in the time-series, ti and tj, whose values are very close. That means the system reached near the same state at the ith and jth iterations. Now consider the two sequences  ti,  ti+1,  ti+2 … and  tj,  tj+1,  tj+2 … We wish to know how these two sequences diverge from each other. For this, consider the distance between the two sequences after k steps: d(k) = | ti+ktj+k |. (This is for a 1D time series. For higher dimensions, you can define this to be the Euclidean distance and modify the code accordingly.) If the system is chaotic, d(k) will initially rise exponentially with k. For this, one can plot ln d(k) vs k and apply a linear fit. The slope will be an estimate for the Lyapunov exponent.
(Since the system is bounded, the two nearby states will not diverge indefinitely though. Their exponential divergence will stop after some length. We must fit the straight line only within this region.)
Now, this was for a single pair of initial states. The Lyapunov exponent is an average of this divergence exponent over all nearby initial pairs. So for this, define d(k)>, where is averaging over all starting pairs  ti,  tj, such that the initial distance d(0) = | t– tj | is less than some fixed small value. The program finds all such initial pairs, calculates d(k)>, plots it against k, and the slope of the initial linear part gives us the Lyapunov exponent.
Python Code
The following code takes a text file with the time series, ‘timeseries.txt’, as the argument. The text file must contain only the time series values in a single column, no serial numbers or any other text before or after. It asks for the starting diameter within which to limit the initial pairs. It displays how many such pairs it is finding in the time series, so you can vary the diameter based on this.
It outputs a text file, ‘lyapunov.txt’ with two columns, k and d(k)>, which you can then plot and fit in the correct region by visual inspection.
from math import log

def d(series,i,j):
    return abs(series[i]-series[j])

f=open('timeseries.txt', 'r')
series=[float(i) for i in f.read().split()]
f.close()
N=len(series)
eps=input('Initial diameter bound: ')
dlist=[[] for i in range(N)]
n=0 #number of nearby pairs found
for i in range(N):
    for j in range(i+1,N):
        if d(series,i,j) < eps:
            n+=1
            print n
            for k in range(min(N-i,N-j)):
                dlist[k].append(log(d(series,i+k,j+k)))
f=open('lyapunov.txt','w')
for i in range(len(dlist)):
    if len(dlist[i]):
        print>>f, i, sum(dlist[i])/len(dlist[i])
f.close()

The following is the plot and fit of the resulting data from a logistic map series with an appropriately chosen initial diameter.

Lyapunov Exponent of Logistic Map

I deliberately did not automate the plotting and fitting part, because a. it’s tedious and hard to write the code in a way that runs on most installations, and b. human eyes will do a much more reliable job of identifying where the linear portion ends.

The Butterfly Effect

For want of a nail, the shoe was lost

For want of a shoe, the horse was lost

For want of a horse, the battle was lost

For want of a battle, the kingdom was lost

And all of this, for want of a nail.

My cousin met his long time girlfriend on a bus, a chance encounter. They got talking. This eventually resulted in a long, long relationship which finally ended because of some factors that are not my jurisdiction to discuss here. Anyway, so this fact that they got on the same bus together and saw each other and talked with each other were not very huge predictable things and could easily have happened otherwise. But that small thing eventually resulted in something big in their lives.

One day I happened to look at my computer screen at a certain time. I was about to close a browser window when something there caught my eye that wouldn’t be on that webpage a minute before or a minute later. This resulted in a 11-month long affair and a very hard break-up which haunted me for more than a year afterwards. I’ll tell you the story briefly. I had opened a tab that was an international chat site. I was mostly on other tabs at that time, but then I decided to close the chat tab. When I was about to, I saw a comment by someone that got me a little interested. Turned out it was a girl from my school I hadn’t met before. (My school has a huge population so it’s impossible to know everyone.) Now there are astronomical odds against that happening. Then I eventually got into a relationship with this girl.

When I was in the relationship, I always used to wonder how something so big had such a small, chance beginning, and saw it as some kind of miracle. My cousin, too, looked at his chance coincidence in the same way.

Then yesterday I wondered, in the loo as usual, and I realized that most things that become big in life don’t have big, predictable beginnings. For example, I met most of my present friends just because some authority in school made some routine decisions so that we ended up in the same section. This could easily have been otherwise, because we have sixteen sections in each class. Okay, for those not familiar with these terms, there were sixteen divisions in each standard, meaning sixteen separate classrooms. (Ours is a large school. It once held the record for being the largest school in Asia in terms of student strength.)

Now should I stare at each of my friends in turn, and calculate the miraculous odds of having met them and made friends with them, then take the product for all my friends, end up with a miniscule fraction, and go crazy contemplating how it ever even happened?

Many people do just that. I used to do that, too, for example when I was in that relationship. But think. Almost everything begins with a tiny chance. Let’s start with you, for example.

You are here because the sperm that carried half of your genes swam a tiny bit faster than the rest. Now, trust me, there are a lot of sperms there that got released in that tract. According to Roald Dahl in My Uncle Oswald, some hundred million. Divide 1 by that number, and you get a tiny fraction. That is the odds for your being here today. No, actually, that fraction is just the first term in a long product of a lot of fractions, which make the odds smaller still. If it had been another sperm, you would have looked different. You might have been the opposite sex.

Imagine if you were born the opposite sex. Okay, slight logical anomaly there. If the sperm were a different one, one of the opposite sex, it wouldn’t be you, of course, but someone else. Anyway, I am sure that being the sex that you are is a big thing for you.

So should you fall to your knees now and thank the lord for your birth? Some people do.

Every. Goddamn. Thing had astronomical odds against it. Everything you can think of. Even physics today is hinting that the universe only exists because of some very tiny, chance quantum fluctuation that led to the Big Bang.

Beginnings have to be small. But some of these small things tend to get bigger in a snowball effect and produce something impactful.

This is the Butterfly Effect. The name comes from the famous observation that some scientists made, like Edward Lorenz in the meteorological sciences: a butterfly fluttering its wings in Brazil can set off a tornado in Tokyo.

What I think is that most things are generated by the Butterfly Effect. It’s just that we don’t notice it because we don’t follow the sequence of events that go on around us. One of the projects that I have thought of doing is to follow such sequences without affecting them to see the Butterfly Effect in action. But probably, due to the Butterfly effect itself, my following the sequence might eventually end up affecting it greatly. Anyway, it’s patient work, but I guess nobody’s done it before.

Obviously, the Butterfly Effects in our lives may not be expressible very well using physics or mathematics. But it is still the Butterfly Effect, which is the sensitive dependence of events on initial conditions. Only, it’s not the weather or population growth or some such thing that scientists usually study. It’s all the events that happen around us and with us. It is not very surprising that the Butterfly Effect should be dominant here because our lives and the tapestry of events in the world are a complex interplay of rules and dependences that are very nonlinear (in the mathematical sense). It’s just like weather modelling, only with 17 million nonlinear equations instead of 17, and a thousandfold number of interdependent variables.

I am obviously not going to attempt an analysis on this Butterfly Effect wrapping around our lives using physics or mathematics, because I simply cannot do it. But I would like to try something else. I told you that everything had huge odds against it happening. And let’s say events A and B together led to C, so that the odds against C are the product of those against A and B. Imagine the number of such events around you that depend on other events, not just two, but many other events, each of which were very improbable themselves. When you are stuck at a traffic signal, look at all the cars around you. What are the odds against exactly those vehicles in the city caught up there with you in that exact configuration? HUGE. Every moment you are in a situation whose exact composition and configuration could be deduced to be fantastically improbable. Even this moment. The fact that you are sitting at a computer reading this now in a particular setting could be traced to very small beginnings. So I repeat, should we gape at every such thing and go crazy just trying to grasp the fantastically miraculous nature of life? No. This awestruck way of looking at things can easily be remedied if we look at it the right way, which is not backwards. This is what I shall take a shot at explaining.

Let’s assume you are male. When you have the pleasant opportunity of making babies with someone, and release your sperm in a reproductive tract, what do you expect will happen? Obviously, if this act of intercourse works, then the egg will get fertilized, usually by one sperm. Is there anything very improbable about that? No. That is what will happen. But now in retrospect if you wonder how improbable it was that that particular sperm would be the first to reach, yes, it might seem miraculous. It could have been some other sperm. But the problem is, if it had been some other sperm, you would have felt similarly awed by its small chance of reaching first. It’s just that there are too many sperm, so that the chances of any one making it first are very small, but one has to reach, right? It’s just a large number of very small probabilities assigned to each sperm, summing up to 1 (assuming that fertilization will take place).

Once this person is born, there are bigger things he could do, like eradicate 6 million Jews off the face of the earth in a World War. In retrospect, all of that will look very astonishingly improbable. But you see, the act of releasing sperm in a reproductive tract is how you can easily set off such a snowball effect. There’s nothing strange or surprising or miraculous about that. It all comes from the nature of the system, that the winning sperm fertilizes the egg, which causes the birth of a person who affects a lot of things in his or her life and leaves descendants to affect more. In such a system, where a small thing gets bigger, it’s obvious that any big thing would have had small, chance beginnings. There’s nothing to worship god about it. If the small beginning had been different, a different big thing would have happened. You just need to get used to this snowball tendency of events, then you’ll see there’s nothing surprising about what’s happening. Perhaps beautiful and interesting, yes, but not unexpected.

If I look at things chronologically, they make sense. If I hadn’t had those people in my section in school, for example, I would only have made different friends. Backwards is not the way to look at it, because backwards is not the way it happened. But yes, it remains a fact that every moment in your life, with its own collection of events, is very, very, very improbable. Surely it is deterministic to some degree, but the determining rules are so complicated that we cannot even begin to find them, let alone use them to manipulate and govern the events in the world or the things that happen to us. Above all, even if we try to, the Butterfly Effect will surely amplify small errors in our manipulations and things will turn out to be very different from what we wanted them to be. The only language we can use to talk about such events is the language of probability. Every moment is the product of a small, small probability, a product over millions of tiny little fractions. If the moment had been different, it would still be equally improbable. Whether the moment could have been different is a question concerning the degree of determinism in the physical world. But I am not talking about that. Even if it is perfectly deterministic, it is not very predictable. The sensitive dependence on initial conditions takes away the predictability completely. We thus live in a world of chance, in which things just turn out to happen in a certain way. Our life is mostly out of our control, in the sense that what we are and what we do today and the people we know and the relationships we cherish are the results of the Butterfly Effect, having their origins in small, chance things we never had any control over, or even access to. We live amidst a storm of uncontrollable events, a raging tornado that forever engulfs our life.

And just out of reach of our eyes lurk the butterflies that cause these tornadoes, fluttering their wings, everywhere and every moment of every day, just out of our reach.

1Life.

Technorati Tags: ,,

Add comment in external guestbook (no need for Windows Live account or sign-in.)