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.