# Recurrence Relations – A Simple Explanation And Much More

Recurrence relations are a powerful tool for mathematical modeling and numerically solving differential equations (no matter how complicated). And as luck would have it, they are relatively easy to understand and apply. So let’s dive right into it using a purely mathematical example (for clarity) before looking at a real-world application.

This equation is a typical example of a recurrence relation:

x(t+1) = 5 * x(t) + 2 * x(t-1)

At the heart of the equation is a certain quantity x. It appears three times: x(t+1) stands for the value of this quantity at a time t+1 (next month), x(t) for the value at time t (current month) and x(t-1) the value at time t-1 (previous month). So what the relation allows us to do is to determine the value of said quantity for the next month, given that we know it for the current and previous month. Of course the choice of time span here is just arbitrary, it might as well be a decade or nanosecond. What’s important is that we can use the last two values in the sequence to determine the next value.

Suppose we start with x(0) = 0 and x(1) = 1. With the recurrence relation we can continue the sequence step by step:

x(2) = 5 * x(1) + 2 * x(0) = 5 * 1 + 2 * 0 = 5

x(3) = 5 * x(2) + 2 * x(1) = 5 * 5 + 2 * 1 = 27

x(4) = 5 * x(3) + 2 * x(2) = 5 * 27 + 2 * 5 = 145

And so on. Once we’re given the “seed”, determining the sequence is not that hard. It’s just a matter of plugging in the last two data points and doing the calculation. The downside to defining a sequence recursively is that if you want to know x(500), you have to go through hundreds of steps to get there. Luckily, this is not a problem for computers.

In the most general terms, a recurrence relation relates the value of quantity x at a time t + 1 to the values of this quantity x at earlier times. The time itself could also appear as a factor. So this here would also be a legitimate recurrence relation:

x(t+1) = 5 * t * x(t) – 2 * x(t-10)

Here we calculate the value of x at time t+1 (next month) by its value at a time t (current month) and t – 10 (ten months ago). Note that in this case you need eleven seed values to be able to continue the sequence. If we are only given x(0) = 0 and x(10) = 50, we can do the next step:

x(11) = 5 * 10 * x(10) – 2 * x(0) = 5 * 10 * 50 – 2 * 0 = 2500

But we run into problems after that:

x(12) = 5 * 11 * x(11) – 2 * x(1) = 5 * 11 * 2500 – 2 * x(1) = ?

We already calculated x(11), but there’s nothing we can do to deduce x(1).

Now let’s look at one interesting application of such recurrence relations, modeling the growth of animal populations. We’ll start with a simple model that relates the number of animals x in the next month t+1 to the number of animals x in the current month t as such:

x(t+1) = x(t) + f * x(t)

The factor f is a constant that determines the rate of growth (to be more specific: its value is the decimal percentage change from one month to the next). So if our population grows with 25 % each month, we get:

x(t+1) = x(t) + 0.25 * x(t)

If we start with x(0) = 100 rabbits at month t = 0 we get:

x(1) = x(0) + 0.1 * x(0) = 100 + 0.25 * 100 = 125 rabbits

x(2) = x(1) + 0.1 * x(1) = 125 + 0.25 * 125 = 156 rabbits

x(3) = x(2) + 0.1 * x(2) = 156 + 0.25 * 156 = 195 rabbits

x(4) = x(3) + 0.1 * x(3) = 195 + 0.25 * 195 = 244 rabbits

x(5) = x(4) + 0.1 * x(4) = 244 + 0.25 * 244 = 305 rabbits

And so on. Maybe you already see the main problem with this exponential model: it just keeps on growing. This is fine as long as the population is small and the environment rich in ressources, but every environment has its limits. Let’s fix this problem by including an additional term in the recurrence relation that will lead to this behavior:

– Exponential growth as long as the population is small compared to the capacity
– Slowing growth near the capacity
– No growth at capacity
– Population decline when over the capacity

How can we translate this into mathematics? It takes a lot of practice to be able to tweak a recurrence relation to get the behavior you want. You just learned your first chord and I’m asking you to play Mozart, that’s not fair. But take a look at this bad boy:

x(t+1) = x(t) + a * x(t) * (1 – x(t) / C)

This is called the logistic model and the constant C represents said capacity. If x is much smaller than the capacity C, the ratio x / C will be close to zero and we are left with exponential growth:

x(t+1) ≈ x(t) + a * x(t) * (1 – 0)

x(t+1) ≈ x(t) + a * x(t)

So this admittedly complicated looking recurrence relation fullfils our first demand: exponential growth for small populations. What happens if the population x reaches the capacity C? Then all growth should stop. Let’s see if this is the case. With x = C, the ratio x / C is obviously equal to one, and in this case we get:

x(t+1) = x(t) + a * x(t) * (1 – 1)

x(t+1) = x(t)

The number of animals remains constant, just as we wanted. Last but not least, what happens if (for some reason) the population gets past the capacity, meaning that x is greater than C? In this case the ratio x / C is greater than one (let’s just say x / C = 1.2 for the sake of argument):

x(t+1) = x(t) + a * x(t) * (1 – 1.2)

x(t+1) = x(t) + a * x(t) * (- 0.2)

The second term is now negative and thus x(t+1) will be smaller than x(t) – a decline back to capacity. What an enormous amount of beautiful behavior in such a compact line of mathematics! This is where the power of recurrence relations comes to light. Anyways, let’s go back to our rabbit population. We’ll let them grow with 25 % (a = 0.25), but this time on an island that can only sustain 300 rabbits at most (C = 300). Thus the model looks like this:

x(t+1) = x(t) + 0.25 * x(t) * (1 – x(t) / 300)

If we start with x(0) = 100 rabbits at month t = 0 we get:

x(1) = 100 + 0.25 * 100 * (1 – 100 / 300) = 117 rabbits

x(2) = 117 + 0.25 * 117 * (1 – 117 / 300) = 135 rabbits

x(3) = 135 + 0.25 * 135 * (1 – 135 / 300) = 153 rabbits

x(4) = 153 + 0.25 * 153 * (1 – 153 / 300) = 172 rabbits

x(5) = 172 + 0.25 * 172 * (1 – 172 / 300) = 190 rabbits

Note that now the growth is almost linear rather than exponential and will slow down further the closer we get to the capacity (continue the sequence if you like, it will gently approach 300, but never go past it).

We can even go further and include random events in a recurrence relation. Let’s stick to the rabbits and their logistic growth and say that there’s a p = 5 % chance that in a certain month a flood occurs. If this happens, the population will halve. If no flood occurs, it will grow logistically as usual. This is what our new model looks like in mathematical terms:

x(t+1) = x(t) + 0.25 * x(t) * (1 – x(t) / 300)    if no flood occurs

x(t+1) = 0.5 * x(t)    if a flood occurs

To determine if there’s a flood, we let a random number generator spit out a number between 1 and 100 at each step. If it displays the number 5 or smaller, we use the “flood” equation (in accordance with the 5 % chance for a flood). Again we turn to our initial population of 100 rabbits with the growth rate and capacity unchanged:

x(1) = 100 + 0.25 * 100 * (1 – 100 / 300) = 117 rabbits

x(2) = 117 + 0.25 * 117 * (1 – 117 / 300) = 135 rabbits

x(3) = 135 + 0.25 * 135 * (1 – 135 / 300) = 153 rabbits

x(4) = 0.5 * 153 = 77 rabbits

x(5) = 77 + 0.25 * 77 * (1 – 77 / 300) = 91 rabbits

As you can see, in this run the random number generator gave a number 5 or smaller during the fourth step. Accordingly, the number of rabbits halved. You can do a lot of shenanigans (and some useful stuff as well) with recurrence relations and random numbers, the sky’s the limit. I hope this quick overview was helpful.

A note for the advanced: here’s how you turn a differential equation into a recurrence relation. Let’s take this differential equation:

dx/dt = a * x * exp(- b*x)

First multiply by dt:

dx = a * x * exp(- b * x) * dt

We set dx (the change in x) equal to x(t+h) – x(t) and dt (change in time) equal to a small constant h. Of course for x we now use x(t):

x(t+h) – x(t) = a * x(t) * exp(- b * x(t)) * h

Solve for x(t+h):

x(t+h) = x(t) + a * x(t) * exp(- b * x(t)) * h

And done! The smaller your h, the more accurate your numerical results. How low you can go depends on your computer’s computing power.

# The Ebook Market in Numbers

Over the years the ebook market has grown from a relatively obscure niche to a thrilling billion-dollar mass market. The total ebook revenues went from 64 million \$ in 2008 to about 3 billion \$ in 2012. That’s a increase by a factor of close to 50 in just a few years.

The number of units sold also increased by the same factor (from 10 million units in 2008 to 457 million in 2012).

(Source)

However, many experts believe that the ebook market has reached a plateau and the numbers for the first half of 2013 seem to confirm that.

From the revenues and units sold we can also extract the development of the average price for sold ebooks. It strongly increased from 6.4 \$ in 2008 to about 8 \$ in 2009. After that, it quickly went back down to 7 \$ in 2010 and 6.7 \$ in 2012. So ebooks have gotten cheaper in the last few years, but are still more expensive than in 2008.

As of 2012, ebooks make up 20 % of the general book market.

21 % of American adults have read an ebook / magazine / newspaper on an e-reader in 2012. This is up from 17 % in the previous year.

A survey, again from 2012, shows that most e-book consumers prefer Amazon’s Kindle Fire (17 %, up from no use) , followed by Apple’s iPad (10 %, same as previous year) and Barnes & Noble’s Nook (7 %, up from 2 %).

# The Internet since 1998 in Numbers

Here’s how the number of websites developed since 1998:

In 1998 there were about 2.4 million websites. This grew to 17.1 million at the turn of the millennium. In 2007 the Internet cracked the 100 million mark and soon after, in 2009, the 200 million mark. 2012 saw a sudden jump to about 700 million websites. 2010 and 2013 were the only years in which the number of sites declined.

The number of users has been steadily increasing at a rate of about 170 million per year. It went from 188 million (3 % of the world population) in 1998 to 2760 million (40 % of the world population) in 2013. A mathematical trend analysis shows that we can expect the 4000 million mark to be cracked in 2017 and the 5000 million mark in 2020.

Very interesting in terms of competition among websites is the ratio of users to websites:

Before 2000 it was relatively easy to draw a large number of visitors to a website. But then the situation drastically changed. The number of users per website dropped from about 88 to 24 and kept on decreasing. Today there are only 4 internet users per website, a tough market for website owners.

Some more numbers: in 1998 there were about 10,000 search queries on Google per day, this grew 1,200,000,000,000 (or 1.2 trillion) per day in 2012. Since Google controls roughly 65 % of the search engine market, the total number of queries per day should be around 1.8 trillion.

All the data is taken from this neat website: Internet Live Stats.

For more Internet analysis check out my post Average Size of Web Pages plus Prediction.

# World Population – Is Mankind’s Explosive Growth Ending?

According to the World Population Clock there are currently about 7.191 billion people alive. This year there have been 118 million births (or 264 per minute) and 49 million deaths (or 110 per minute), resulting in a net growth of 69 million people. Where will this end? Nobody can say for sure. But what we can be certain about is that the explosive growth has been slowing down for the past 40 years. I’ll let the graphs tell the story.

Here is how the world population has developed since the year 1700. The numbers come from the United Nations Department of Economic and Social Affairs. From looking at the graph, no slowdown is visible:

However, another graph reveals that there’s more to the story. I had the computer calculate the percentage changes from one decade to the next. From 1960 to 1970 the world population grew by 22 %. This was the peak so far. After that, the growth rate continuously declined. The percentage change from 2000 to 2010 was “only” 12 %.

Of course it’s too early to conclude that this is the end of mankind’s explosive growth. There have been longer periods of slowing growth before (see around 1750 and 1850). But the data does raise this question.

Talk to me again when it’s 2020 or 2030.

Just by the way: according to estimates, about 108 billion people have been born since the beginning of mankind (see here). This implies that about 101 billion people have died so far and that of all those born, 6.5 % percent are alive today.

Did somebody say dust in the wind?

# Average Size of Web Pages plus Prediction

Using data from websiteoptimization.com I plotted the development of web page sizes over the years. I also included the exponential fit:

As you can see, the 1/2 MB mark was cracked in 2009 and the 1 MB mark was cracked in 2012. Despite the seemingly random fluctuations, an exponential trend is clearly visible. The power 0.3 indicates that the web page sizes doubles about every 2.3 years. Assuming this exponential trend continues we will have these average sizes in the coming years:

2013 – ca. 1600 kb
2014 – ca. 2100 kb
2015 – ca. 2900 kb

So the 2 MB will probably be cracked in 2014 and in 2015 we will already be close to the 3 MB mark. Of course the trend is bound to flat out, but at this point there’s no telling when it will happen.

If you like more Internet analysis, check out The Internet since 1998 in Numbers.