Diffusion of the dead - Epilogue. Part 2, The results.

Last time, I presented a question that I had been given by PrettyGreen, a PR company that asked me to get involved with their Halloween publicity campaign for the mobile network operator GiffGaff. We also saw how I modelled the problem and this week I present the results and also the Matlab codes that I used, should you want to recreate, or play around, with the solutions.

The advert presenting the characters involved can be found below.

________________________________________________________________

________________________________________

Results

The survival time of each character in ascending order can be found in the table below. This is further complemented by Figure 1, in which we illustrate the health of each combatant over a 60 minute time span.

The first two characters to die are the Dead Girl and Skin Face. Although these two characters are relatively strong their low initial healths mean that the other combatants are able to dispatch them with relative ease. Thus, neither of them last longer than a minute demonstrating that neither of them are able to use their aggression to its fullest. Similarly, Baby Man is next to die, because although he is able to defend himself better, lasting just over a minute, the combatants once again go after the weakest.

Name	Survival time
Dead Girl	3 secs
Skin Face	13 secs
Baby Man	1 mins 44 secs
Pumpkin Head	7 mins 9 secs
Tall Guy	10 mins 7 secs
Hero Girl	55 mins 37 secs
Evil Clown	Survivor

The next two to die are quite interesting, these are Pumpkin Head and Tall Guy, lasting approximately 7 and 10 minutes respectively. Up until this point the group has simply been killing the current weakest. At the five minute marker this would be Tall Guy, however, as seen in Figure 1, he is able to outlast Pumpkin Head because Tall guys higher agility allows him to defend better.

Eventually, only Evil Clown and Hero Girl are the surviving combatants. This is interesting as it is often the plot of a horror film to have the heroine survive up until the last few moments, when the final kill is unleashed during extended scenes of heightening tensions. This is exactly what is seen in Figure 1. Initially, things are looking good for Hero Girl as she begins the final battle with much more health than Evil Clown. Furthermore, the agility of the Hero Girl and Evil Clown are equal and the highest out of the group. This has kept them safe up until this point because they were able to run away from danger. Similarly, for the 30 minutes after Tall Guy’s death the two characters are able to capably defend themselves and escape each others attacks.

These tropes are used in many horror films: although the heroine is no physical match for the villain, she is able to make up for the lack of strength in terms of speed. It is also a standard horror trend that it should look like the heroine will survive, but then she is subjected to escalating bouts of terror. Although she is able to put up a valiant fight Hero Girl’s life is slowly drained by Evil Clown’s higher strength, ultimately leading to his victory after 55 minutes and with 45 health remaining.

Who'd have thought that the Evil Clown was so dangerous?! And who could have foreseen where such a simple piece of mathematics, based on the modelling of zombies, would take us?

This brings us to the end of this current set of posts. Next time: something completely different.

________________________________________________________________

________________________________________

function Battle_Royale
%Clear computer memory and plots.
clear
close all
clc

options = odeset('RelTol',1e-4,'AbsTol',1e-5); %Options set for the ODE solver.

S=[9  7  6  8  3  8  9]; %Vector of strength values.
A=[7  8  4  3  8  6  3]; %Vector of agility values.
H=[45 65 60 40 90 10 20];%Vector of initial health.
C=S.*A; %The interaction function is scaled by the strength multiplied by the agility.

[T,Y] = ode45(@(t,y) ODES(t,y,C),[0 7000],H,options); % Solve the ODE.

cc=lines(7); % Set the legend colours.
for i=1:7
    %Find the last moment alive.
    YY=Y(:,i);
    YY(YY<0.1)=0;
    index=find(YY,1,'last');
    YY(YY==0)=nan;
    YY(index)=0;

    plot(T/60,YY,'linewidth',3,'color',cc(i,:)); %Plot results.
    t(i)=T(index)/60;
    hold on
end
t %Print out the times of death.
axis([0 60 0 90]) %Set axes.

%Make the plot look nice.
legend('Tall guy','Evil Clown','Pumpkin Head','Baby Man','Hero Girl','Dead Girl','Skin Face','location','northoutside','orientation','horizontal')
xlabel('Time in minutes')
ylabel('Combatant Health')

function dy = ODES(t,y,C)
Terms=y.*C'; %The value of the each combatant's attack.
dy=zeros(7,1); %Preallocation of the variables.
for i=1:7
    indices=[1:i-1,i+1:7]; %Indices to be summed over.
    dy(i)=-heaviside(y(i))/((1+y(i)^2)*2*C(i))*sum(Terms(indices)); %Differential equation.
end

Diffusion of the dead - Epilogue. Part 1, Horror Battle Royale.

Having written and published the article on zombie invasion I thought the story would end there. Of course the media picked it up and I had my 15 minutes of fame on the radio and TV. However, it appears I was very wrong. A PR company, PrettyGreen, contacted me about getting involved with their Halloween publicity campaign for GiffGaff, a mobile network operator. 

Their question was: suppose seven stereotypical characters from horror movies are released in an arena leading to a battle royale, who would survive? The characters are:

• Tall Guy – A very tall (6,9 ft) escaped convict;
• Evil Clown – An evil, twisted clown;
• Pumpkin Head – A man with a pumpkin as a head;
• Baby Man – A somewhat mental man who has spent is life trapped in a basement;
• Hero Girl – A normal young girl;
• Dead Girl – A dead bride;
• Skin Face – A man with excess skin stapled over his face.

My first thought was how was I going to do this? As mentioned when we first started this set of posts there are many different ways mathematics could answer this question. I decided to use differential equations to model the health of each character. As the characters interact their health would reduce depending on certain factors. Thus, I asked PrettyGreen to provide me with a strength, agility and initial health for each combatant and I used these to simulate who will be the last person standing. They were even kind enough to send me a picture to use with this post.

Figure 1. Hero Girl, Evil Clown, Dead Girl, Tall Guy and Pumpkin Head all having a nice jog in London. Image courtesy of PrettyGreen.

This post is a little more mathematical then normal as I present all the gory equation details. However, do not let this scare you. Hopefully, I provide all the intuitive details you should need in the text. If you just want the brief that appeared in the news, then please look here.

________________________________________________________________

________________________________________

Method

The battle simulation is based on the reduction of each combatant’s initial health at a rate proportional to their meeting with an opponent. Once a combatant’s health has dropped to zero, they are immediately removed from the conflict, whilst the survivors fight on.

The interaction outcome is based on a scaled form of the empirical rule known as the “Law of Mass Action”. Explicitly, the rate of reduction in health is proportional to the attacker’s health, scaled by an inverse square of the defender’s health. Intuitively, this simply means that a reduction in health can only occur when the attacker and defender meet. Moreover as the attacker gets weaker, their attacks do less damage. Equally, as the defender becomes weaker their defence is less effective. The precise form of the interaction term is,
\begin{equation}
\frac{H_a}{1+H_d^2},
\end{equation}

where $H_a$ is the health of the attacker and $H_d$ is the health of the defender. It should be understood that this interaction term is known as a "constitutive equation". This means that it is not based on any fundamental law, but it is postulated because it produces the right kind of dynamics that we would expect. There are many other functions I could have used in its place, however, in using this equation, I am hoping that it is simple enough to capture the general outcomes of the system and, thus, the results will be robust to any small changes that might occur.

From these assumptions we can construct a coupled set of ordinary differential equations that will evolve the battle and predict who will win. The exact form of the equation for combatant $i=1,2,…,7$ is

\begin{equation}
\tau\frac{dH_i}{dt}=\frac{-1}{1+H_i^2}\frac{1}{S_iA_i}\sum_{j\neq i}S_jA_jH_j.
\end{equation}
Note that the equation is only active while $H_i>0$. Also notice that we have scaled the terms with the strength parameter, $S_i$, and agility parameter, $A_i$. Thus, speed is, potentially, just as important as strength. Parameters can be found in the Table 1, below. Finally, we define the initial condition as:
\begin{equation}
H_i{0}=H_{i0}.
\end{equation}

Name and variable	Strength, $S_i$	Agility, $A_i$	Initial health, $H_{i0}$
Tall Guy, $H_1$	9	7	45
Evil Clown, $H_2$	7	8	65
Pumpkin Head, $H_3$	6	4	60
Baby Man, $H_4$	8	3	40
Hero Girl, $H_5$	3	8	90
Dead Girl, $H_6$	8	6	10
Skin Face, $H_7$	9	3	20

The parameters were chosen such that strength and agility were on a scale from 1 to 10, such that higher numbers represent higher strengths and speeds, respectively. The health parameter is on a scale of 0 to 100, with the relative size determining how healthy each character is. It should be noted that in the original data Dead Girl’s health was 0. Understandably, this would make her “dead”, however, it would also suggest that she was unkillable, resulting in her inevitable win. To ensure such a case does not occur I changed her initial health to 10.

Next time I will present the results of the above simulations and demonstrate that although this is only a simple model it produces an outcome that you would expect to see in any good (or bad) horror film. In the mean time, have a go at simulating the system yourself and perhaps vary the interaction rule to see how the results are influenced by this equation.

Diffusion of the dead - The maths of zombie invasions. Part 9, The complete strategy.

Over the past 8 posts we have investigated the mathematical implications of a zombie invasion. If you really can't be bothered to read all of the details, please see part 1, where you'll find some links to presentations that I have done and I'll give you all the details inside of one hour!

For the more patient reader, we began in parts 2, 3 and 4 where we discussed the philosophy of modelling, the assumptions that would make up the zombie invasion model and some basic mathematical simulation techniques. Although important for the recreational mathematician if you're really in a pinch you'll want to skip right to the results.

In particular, in parts 5 and 6 we showed that running away from zombies increases the initial interaction time far more than trying to slow the zombies down. Thus, fleeing for your life should be the first action of any human wishing to survive. However, we cannot run forever; interaction with zombies is inevitable.

In part 8 we showed that the best long-term strategy is to create a fortified society that can sustain the population, whilst allowing us to remove the zombies as they approach. This, in effect, reduces the risk to zero and we will survive.

In the event of the apocalypse, it is unlikely that we would be able to support such a commune without raiding parties scavenging for medicine, food and fuel. Thus, in this case, we fall back on the maxim of being more deadly than the zombies which allows us to survive as shown in part 7.

Over all, it is difficult for us to survive simply because zombies do not have a natural death rate, and by biting us, they are able to increase their own ranks whilst reducing ours. Thus reinforcing our greatest fear that human allies could quickly become our biggest nightmares.

Our conclusion is grim, not because we want it to be so but because it is so. It had always been the authors' intention to try and save the human race. So to you, the reader, who may be the last survivor of the human race, we say: run. Run as far away as you can get; an island would be a great choice. Only take the chance to fight if you are sure you can win and seek out survivors who will help you stay alive.

Good luck.
You are going to need it.

Diffusion of the dead - The maths of zombie invasions. Part 8, Surfing the infection wave.

Last time we considered the interaction rules

1. humans kill zombies;
2. zombies kill humans; and
3. zombies can transform humans into zombie,

and produced the following system of equations,

\begin{align}\frac{\partial H}{\partial t}&=D_H\frac{\partial^2 H}{\partial x^2}-\alpha HZ\label{Human_PDE}\\\frac{\partial Z}{\partial t}&=D_Z\frac{\partial^2 H}{\partial x^2}+\beta HZ\label{Zombie_PDE},\end{align}

which predicts the evolution of the human population, $H$, and the zombie population, $Z$.

To see how quickly the infection moves through the human population, we look for a particular type of solution, known as a "Fisher wave". This type of wave travels at a specific speed and does not change its shape as its travels. Such a solution can be seen below.

 Movie: The black line represents the human population. The red dashed line represents the zombie population. Initially, there are only a small number of zombies, but over time the infected population spreads out and transforms the susceptible population.

By manipulating the equations we can show that the wave speed, $v$, has a value of

\begin{equation}
v^2=4D_Z\beta H_0,
\end{equation}

where $D_Z$ is diffusion rate of the zombies, $\beta$ is the net-rate of zombification (a.k.a how quickly the zombie population grows) and $H_0$ is the initial human population. Critically, note that the left-hand side of the equation is positive, because it is a squared value.

In order to slow the infection, we should try to reduce the right-hand side of the above equation.

• Reducing $D_Z$ amounts to slowing the zombies down; thus, an effective fortification should have plenty of obstructions that a human could navigate but a decaying zombie would find challenging.
• Reducing $\beta$ occurs through killing zombies quicker than they can infect humans. If we are really effective in our zombie destroying ways then we can make $\beta$ negative. This would make the right-hand side of the equation negative, but the left-hand side of the equation is positive. Since we get a contradiction no wave can exist and the infection wave is stopped.
• Reducing $H_0$ involves reducing the human population. This could mean geographically isolating the population on an island because if the zombies are unable to get to you then they can't infect you.

The last tactic of reducing the human populations could also lead to a rather controversial tactic. Suppose you don't live near a deserted fortified island. Rather, you work in an office surrounded by people who would not be able to protect themselves from the oncoming hordes. Then you may consider removing the humans around you in a more drastic and permanent way. This is because everyone that surrounds you is simply a potential infection!

I do not recommend this cause of action, as reducing the human population also reduces the number of people able to fight the zombies and humans sacrificing other humans would only speed the extinction of their own species. The human population will have enough trouble trying to survive the hordes of undead, without worrying about an attack from their own kind!

This, pretty much, brings us to the end of the mathematical zombie story. It's been a long journey, thus, to ensure that you haven't missed any of the critical strategies along the way the next post simply focuses on summarising and concluding what we're been discussing since Halloween. See you then.

Diffusion of the dead - The maths of zombie invasions. Part 7, Face to face with a zombie.

So far we have only considered zombie motion. It has been an incredibly simply model, but it has been able to furnish us with a wealth of information. In particular, we have been able to predict how long it will take the zombies to get to us and we have shown that the best strategy is to run away.

Unfortunately, you can only run so far. At some point you are no longer running away from the living dead, but actually running towards a different mob of zombies. So what should you do when you finally end up having to go hand to hand with a zombie?

To model human-zombie interactions, we suppose that a meeting between the

two populations can have three possible outcomes. Either

1. the human kills the zombie;
2. the zombie kills the human; or
3. the zombie infects the human and so the human becomes a zombie.

These outcomes are illustrated in Figure 1.

Allowing $H$ to stand for the human population and $Z$ to stand for the zombie population, these three rules can be written as though they were chemical reactions:

\begin{align}
H+Z&\stackrel{a}{\rightarrow}H \text{ (human kills zombie)}\\
H+Z&\stackrel{b}{\rightarrow}Z \text{ (zombie kills human)}\\
H+Z&\stackrel{c}{\rightarrow}Z+Z \text{ (human becomes zombie).}
\end{align}

The letters above the arrows indicate the rate at which the transformation

happens and are always positive. If one of the rates is much larger than the

other two, then this "reaction" would most likely happen.

Figure 1. The possible outcomes of a human-zombie interaction. Either (a)

humans kill zombies, (b) zombies kill humans, or (c) zombies convert humans.

To transform these reactions into a mathematical equation, we use the "Law of Mass Action". This law states that the rate of reaction is proportional to the product of the active populations. Simply put, this means that the above reactions are more likely to occur if we increase the number of humans and/or zombies. Thus, we can produce the following equations which govern the population dynamics

\begin{align}\frac{\partial H}{\partial t}&=D_H\frac{\partial^2 H}{\partial x^2}-\alpha HZ\\\frac{\partial Z}{\partial t}&=D_Z\frac{\partial^2 H}{\partial x^2}+\beta HZ.\end{align}

where $b+c=\alpha$ is the net death rate of humans and $c-a=\beta$ is the net creation rate of zombies.

If we ignore the reactions for a second, we have seen the first part of the equations before. Explicitly we are assuming that both the zombies and humans randomly diffuse throughout their domain. Now we have previously justified the zombies' diffusive motion as they are mindless monsters. However, humans are not usually known for their random movement. Here, we use the fact that if the dead should start to rise from their graves, then panic would set in and humans would start to run away and spread out randomly from location of high population density. Thus, human movement could also be described by diffusion, although their diffusion rate is likely to be much larger than the zombies'.

If we now include the interaction formulation once again then the equations immediately highlight some important components of this problem. Firstly, because $b$, $c>0$ and $H$, $Z\geq 0$ then the human interaction term, $-\alpha HZ$, is always negative. Thus, the  human population will only ever decrease over time.

We could add a birth term into this equation, which would allow the population to also increase in the absence of zombies but, as we have seen previously, the time scale on which we are working on is extremely short, much shorter than the 9 months it takes for humans to reproduce! Thus we ignore the births since they are not likely to alter the populations a great deal during this period.

Interpreting the zombie equation is not so easy. The term $c-a=\beta$ may either be positive or negative. If $(c-a)>0$ then the creation rate of zombies, $c$, must be greater than the rate which we can destroy them, $a$. In this case the humans will be wiped out as our model predicts that the zombie population will grow and the human population will die out. However, there is a small hope for us. If the rate at which humans can kill zombies is greater than the rate at which zombies can infect humans then $(c-a) < 0$. In this case both populations are decreasing, thus our survival will come down to a race of which species becomes extinct first.

Next week we will delve into the equations more and consider the spread of infection. We will then be able to derive expressions that really tell us how to survive, or at least delay, the zombie uprising.

Diffusion of the dead - The maths of zombie invasions. Part 6, Run, don't fight.

Last time I demonstrated how to approximately find the time of your first interaction with a zombie using the diffusion equation and the bisection method. The Time-Distance-Diffusion graph is illustrated below.

Figure 1. Time in minutes until the density of zombies reaches one for various rates of diffusion and distances.

When the apocalypse does happen, we have to ask ourselves the question: do we want to waste time computing solutions when we could be out scavenging? In order to speed up the computational process we consider the diffusive time scale:

\begin{equation}t=\frac{L^2}{\pi^2 D}.\label{Time_scale}\end{equation}

You may recognise this group of parameter, as we saw it back in Part 4. In particular, in the solution to the diffusion equation, we can see that this is the time it takes for the first term of the infinite sum to fall to $\exp(-1)$ of its original value. The factor of $\exp(-1)$ is used due to its convenience.

Only the first term of the expansion is considered because as $n$ increases, the contribution from the term

\begin{equation}\exp\left(-\left( \frac{n\pi}{L} \right)^2Dt\right)\end{equation}

rapidly decreases. Thus, the first term gives an approximation to the total solution and, so, equation \eqref{Time_scale} gives a rough estimate of how quickly the zombies will reach us.

For example, being 90 metres away and with zombies who have a diffusion rate of 100m$^2$/min, $t\approx 26$ minutes, comparable to the solution in Figure 1. We have had to use no more computing power than you would find on a standard pocket calculator. More importantly this parameter grouping also implies a very important result about delaying the human-zombie interaction.There are two possible ways we could increase the time taken for the zombies to reach us. We could:  

1. run away, thereby increasing $L$; or
2. slow the zombies down, thereby decreasing $D$.

Since the time taken is proportional to the length squared, $L^2$ and inversely proportional to the diffusion speed, $D$. This means that if we were to double the distance between ourselves and the zombies, then the time for the zombies to reach us would approximately quadruple. However, if we were to slow the zombies down by half, then the time taken would only double.

Since we want to delay interaction with the zombies for as long as possible then, from the above reasoning, we see that it is much better to expend energy running away from the zombies than it is to try and slow them down. Note that we are assuming that zombies are hard to kill without some form of weaponry. If they weren't difficult to destroy then we need not worry about running away.

These conclusions are confirmed in Figure 1. Slowing a zombie down from 150 m/min to 100 m/min only gains you a couple of minutes when you are 50 metres away. However, running from 50 m to 90 m increases the time by over 10 minutes, even in the scenario of relatively fast zombies.

It should be noted that the time derived here is a lower bound. In reality, the zombies would be spreading out in two dimensions and would be distracted by obstacles and victims along the way, so the time taken for the zombies to reach us may be longer. The fact that this is a conservative estimate though will keep us safe, since the authors would prefer to be long gone from a potential threat rather than chance a few more minutes of scavenging!

Of course, we can't run forever. Next week we will begin to ask what happens when we finally meet this horrific horde!

Diffusion of the dead - The maths of zombie invasions. Part 5, Time of first interaction.

Previously, we saw how to simulate the diffusion equation, which we're using to model zombie motion. Critically, the diffusion equation allows us to predict the density of zombies at all places and for all time. 

There are many questions we could answer with this equation; however, the most pressing question to any survivors is, "How long do we have before the first zombie arrives?". The mathematical formulation of this question is, "For what time, $t_z$, does $Z(L, t_z) = 1$?". Unfortunately, this does not have a nice solution that can be evaluated easily. However, we can calculate $t_z$ numerically to any degree of accuracy we choose by using a simple solution searching technique known as the "Bisection Search Algorithm"

The first thing to notice about $Z(L,t)$ is that it is monotonically increasing in time, thus, if $t_1>t_2$ then  $Z(L,t_1)>Z(L,t_2)$. This can be seen in a number of ways. For example, by watching the diffusion simulation from last time we see that as time increases the zombie population on the boundary only ever increases. This makes intuitive sense, because diffusion is causing the zombie population to spread out, so that it becomes uniform everywhere.

Using this knowledge then a simple method of solving $Z(L, t_z) = 1$ would be to substitute in a value of $t$. If $Z(L, t) < 1$ then we double $t$ and consider $Z(L, 2t)$, which will be greater than $Z(L,t)$, because of the monotonic property we discussed above. We keep doubling $t$ until we reach a value such that $Z(L, 2^nt) > 1$. Defining $t_0 = 2^{n-1}t$ and $t_1 = 2^nt$, then we know that there exists some $t_z$ between $t_0$ and $t_1$ such that $Z(L, t_z) = 1$.

To gain better approximations to the value of $t_z$, we start halving this domain and only keep the half that contains the solution. However, how do we know which half contains the solution? We once again rely on the monotonic property and evaluate the function at the midpoint of the domain. Explicitly, if  $Z(L,(t_0+t_1)/2) < 1$ then the solution is in the right half. Alternatively, if $Z(L,(t_0+t_1)/2) > 1$ then the solution is in the left half.

An example illustrating this concept is shown in Figure 1. In the initial setup, $Z(L,(t_0+t_1)/2)>1$, thus, we redefine $t_1 = (t_0 + t_1)/2$ and repeat the process.

Figure 1. Bisection technique. After each iteration, the domain, shown by the dashed lines,
becomes half as long as it was before.

After each iteration, we halve the size of the interval $[t_0, t_1]$, making it smaller and smaller. Thus, by design, since we always have $t_z$ within $[t_0, t_1]$ and by repeating the halving process, we can estimate $t_z$ to any accuracy we like.

The benefit of this method is its simplicity and reliability; it will always work. However, the cost of this reliability comes at the price of speed. If the initial searching region is very big, it may take a large number of iterations before the process produces an answer to an accuracy with which we are happy. There are quicker methods, but these are usually more complex and sometimes they may fail to find a solution altogether.

If the zombies are closing in on you and you need to compute their interaction times more quickly, we direct you to consider Newton-Raphson techniques rather than the bisection method. Although if the zombies really are that close may I suggest you focus on fighting them off before you read any further?

No matter what solution method you use you should end up with a graph like Figure 2, which illustrates the time in minutes we have before we meet a zombie depending on how far away we are and how fast the zombies are diffusing.

Figure 2. Time in minutes until the first zombie arrives for various rates of diffusion and distances.

At this point we can consider two general strategies. Either we run away, or we try and slow the zombie down. Both of these approaches will indeed increase the time it takes for the zombies to get to you. However, Figure 2 clearly shows that we gain much more time by running away compared to the strategy of slowing the zombies down. Next time I will expand on this point and show how to estimate the zombie interaction time much quicker.

________________________________________________________________

________________________________________

My amazing wife on her zombie themed hen do.
Note that the theme had nothing to do with me.

You may be wondering how I chose the variable ranges for Figure 2. Well, the Oxford maths department is approximately 90m away from a graveyard so the distances simply came from a matter of self preservation. The diffusion speed on the other hand was generated with the aid of my loving wife. I got her to wander randomly around, staggering like a zombie. I timed her and measured how far she had moved and, thus, calculated that her zombie diffusion rate was approximately 115m$^2$/minute. Don't worry we did the experiment three times and took an average, which ensures that this value is accurate.