Playing with models.

Immunization in the age of intercontinental travel

Posted in Game theory, Statistics by Alexander Lobkovsky Meitiv on January 18, 2011

People in face masks in China during the flu epidemic

Face masks curtail the spread of the virus during the flu pandemic.

If you have kids in school, you are familiar with how fervently the school administrators enforce the 100% immunization policy. The schools are complying with the local laws which grant exceptions grudgingly. Childhood immunization is a powerful tool against a variety of crippling viruses some of which are extinct (outside the controlled lab environment) as a result of widespread immunizations. Controversy over the possibly harmful side effects (mercury, other preservatives) notwithstanding, is the zeal for reaching the 100% immunization rate justified?

The efficacy of a vaccination program is quantified by the fraction of the non-immunized population that gets sick in an epidemic. This fraction can also be thought as the probability that a particular individual will get sick in an epidemic.

A number of factors determine the probability of infection in an epidemic:

How long is the sick person contagious? What is the probability of infection given the contact with a sick person? What is the average rate of inter-personal contacts? How far does a person travel during the sickness? The answers to these questions depend on the type of virus, and the properties of the population such as its density and the patterns of movement.

The situation seems too complex for predictive modeling. Could a simplified model offer meaningful insight? Yes, if we pick a narrow aspect of the problem to look at. How about this? You probably heard the doomsday scenarios of a deadly virus spread around the world aboard airplanes. Is a this kind of talk just fear-mongering or a realistic prediction?

Let us construct a model to study whether the doomsday scenario is plausible. Let’s start with a 2D square lattice, or a board, whose sites (spaces) can be empty of occupied by “people” — let’s call them “entities.” The entities could be in three states: immune, vulnerable, and sick. The sick entities can infect the vulnerable but not the immune ones. We need to decide what to do with the sick entities. For example, some fraction of them can “die”–be removed from the board. The simplest thing is to just let them become immune after the disease has run its course. This is what is done in our model.

The entities can move around the board. The movement models the short range everyday movement of the population: commute, shopping, going to and from school, etc. I will use a turn based (like the Conway’s game of life) set of movement rules that are often used in simulating fluid-vapor interfaces. The result is a collection of dense clusters of varying sizes that float in a sparsely inhabited sea. There is little exchange of entities between the clusters. Since the infection is acquired on contact, global epidemics are impeded by the limited inter-cluster movement. One could think of these semi-isolated clusters as communities, cities, or even continents depending on your perspective.

Below is the movie of the model simulation in which the sick entities (red) infect the vulnerable entities (blue) and after a while become immune (green). A fraction of the population is already immune at the onset of the epidemic. Observe how the disease propagates quickly across the clusters and makes infrequent jumps between the clusters. In this particular simulation, 37% of the vulnerable population got sick before the epidemic fizzled out.

You probably noticed that the immunization rate in the above example is rather low, 30% to be exact. Since most entities are vulnerable, the epidemic has no trouble spreading. When the immunization rate is more than doubled to 70%, most epidemics fizzle out early. As you can see in the PDF (probability density function) plot below of the total epidemic size (defined as the fraction of the vulnerable population that go sick), all epidemics involve fewer than 4% of the populace. There is simply not enough population movement for the disease to spread.

PDF of the epidemic size in a model without large scale movement

When the movement is local and the immunization rate is high, most epidemics fizzle out without affecting many people.

Time to include airplanes and examine the plausibility of the doomsday scenario!

In addition to the short range movement, let’s allow at each turn a certain small fraction of the population to move anywhere on the board. The second graph below is the PDF of the epidemic size for the same parameters as the one above, but with the additional 5% of the population executing large scale movement each turn. Notice the radical change in the scale of the x axis. When a small fraction of the population travels long distances each turn, most epidemics grow to encompass the majority of the population. The bimodal nature of the epidemic size distribution suggests that there is a threshold size. If the epidemic hits a cluster that happens to be larger than the threshold, the disease can escape and infect almost all other clusters.

PDF of the epidemic size when macerate large scale movement is allowed

When only 5% of the population execute large scale movement every turn, most epidemics grow to affect a significant fraction of the population.

Let us now quantitatively examine the effect of the large scale movements on the probability of significant epidemics. In the graph below I will plot the probability of occurrence of an epidemic that involves > 10% of the vulnerable populace as a function of the immunization rate for two different magnitudes of the large scale movement. Significant epidemics become rare as the immunization rate increases. However, perhaps not surprisingly, greater immunization rate is required to avoid epidemics for a larger magnitude of large scale population movement.

Probability of a significant epidemic as a function of immunization rate

Greater large scale movement requires a higher immunization rate to avoid a significant epidemic

Predicting how epidemics spread in the real world is a tricky business. However, the general conclusion of the simple model, I think, will stand. While 100% immunization rate is not strictly required to stem epidemics, as the extent of long distance travel increases, we will need a higher immunization rate. It would be unwise to be lax about immunization requirements to discover one day that not enough of the population is immunized.

The real issue, I think, is that the small fraction of people who refuse to be immunized are shielded from infection by those who took the risk of immunization (albeit a small risk). But that is a can of worms, I don’t really want to open…

The waiting game.

Posted in Game theory, Transportation by Alexander Lobkovsky Meitiv on December 20, 2010
People waiting at a bus stop.

When two buses can take you where you need to go should you let the slow bus pass and wait for the fast bus?

The Metro has changed the bus schedule this morning with no prior notice whatsoever. The 9 am J1 bus, I usually take, did not come. As I found out later, it was dropped from the schedule altogether. For about 20 minutes I was assuming (with diminishing conviction) that the J1 was merely late. While waiting for the J1, I let two J2’s go by. The J2’s take about 15 minutes longer to reach my destination. While I was waiting, I began to wonder what the best waiting strategy would be if there were two modes of transport with different travel times and different service frequencies. There is a math problem in there with a clear cut answer.

It is simpler to consider the situation in which buses do not have a fixed schedule but arrive at a fixed rate per unit time \mu. Intervals between consecutive buses in this situation obey Poisson statistics, which means that no matter when I arrive at the stop the average waiting time before the bus arrives is 1/\mu.

In what follows I will present a few results without much derivation. If you are interested in the nitty-gritty, contact me for details.

Suppose there are two buses A and B that arrive at a stop with rates \mu_A and \mu_B. The probability that A arrives before B is

P(A\mathrm{\ before \ } B) = \displaystyle{\frac{\mu_A}{\mu_A + \mu_B}}.

The mean waiting time for bus A provided that A has arrived first is

t_A =\displaystyle{\frac{\mu_A}{(\mu_A + \mu_B)^2}}.

Now if the travel times to destination on buses A and B are \tau_A \geq \tau_B, we can compute the expected travel time if the traveler boards the first bus that comes to the stop. We will call it T_0 because the strategy is to let zero buses pass (even if they take longer).

T_0 = \displaystyle{\frac{\mu_A \tau_A}{\mu_A + \mu_B} + \frac{\mu_A}{(\mu_A + \mu_B)^2} + \frac{\mu_B \tau_B}{\mu_A + \mu_B)} + \frac{\mu_B}{(\mu_A + \mu_B)^2} = \frac{1 + \mu_A \tau_A + \mu_B \tau_B}{\mu_A + \mu_B}}.

We can interpret this formula as follows. The total bus arrival rate is \mu_A + \mu_B and therefore the mean waiting time for a bus, any bus is 1/(\mu_A + \mu_B). Then with probability \mu_A/(\mu_A + \mu_B) the A bus has arrived and the travel time is \tau_A. Likewise, with probability \mu_B/(\mu_A + \mu_B) the B bus arrives so that the travel time is \tau_B.

It is a inly marginally trickier to derive the mean trip duration (will call it T_1) when we are willing to let one A bus pass by in the hopes that the next bus will be the faster B bus. The answer is

T_1 = \displaystyle{\frac{1}{\mu_A + \mu_B} + \frac{\mu_A T_0}{\mu_A + \mu_B} + \frac{\mu_B \tau_B}{\mu_A + \mu_B}}.

The explanation of the second term in the above formula is that if A arrives first, we let it pass and we are back to the “let zero buses pass” strategy. The rest of the terms in the equation for T_1 are the same as before.

In general, for any n \geq 1 we have a recursion relation:

T_{n+1} = \displaystyle{\frac{1}{\mu_A + \mu_B} + \frac{\mu_A T_n}{\mu_A + \mu_B} + \frac{\mu_B \tau_B}{\mu_A + \mu_B}}.

We can now start asking questions like: “Under what conditions does letting the slow bus pass make sense (i.e. results in a shorter expected trip)?” What about letting two buses pass? When does that strategy pay off?

When does T_1 \leq T_0? Comparing the formulas above we arrive at a simple condition on the arrival rate of the fast bus which is independent of the arrival rate of the slow bus

\displaystyle{\mu_B \geq \frac{1}{\tau_A - \tau_B}} \quad \mathrm{(1)}.

For example, if the slow bus takes 30 minutes and the fast bus takes 20 minutes to arrive at the destination, it makes sense to let the slow bus pass if the fast bus arrives more frequently than once in 10 minutes. No big surprise there, anybody with a modicum of common sense could tell you that.

What is surprising is that the condition (1) does not depend on the arrival rate of the slow bus. Did I make a mistake? It turns out that when T_1 = T_0, the expected travel times for other strategies are exactly the same! I will leave the proof to my esteemed reader as homework :)

Therefore, since it does not matter how frequently the slow bus comes, if the fast bus comes frequently enough (condition (1) is satisfied), it makes sense to wait for the fast bus no matter how many slow buses pass.

Speed bested by agility

Posted in Dynamics, Game theory by Alexander Lobkovsky Meitiv on November 14, 2010

The rabbit relies on superior maneuverability to escape predators.

Next time you see a squirrel fleeing from a cat, notice it’s escape strategy. Instead of bolting straight for the safety of a tree, the squirrel follows a zig-zag trajectory with sharp, frequent turns punctuated by its thrashing tail. The pursuing cat, unable to execute the sharp turns, overshoots and looses ground as it adjusts its trajectory.

The flight behavior of a prey is instinctual and highly sophisticated–after all, predation is a major selective pressure in a Darwinian universe. The variation of escape strategies reflects the intrinsic abilities of the prey. Some prey, like the antelope, rely on superior speed and safety in numbers. Others, like the rabbit, or the squirrel, rely on superior maneuverability. In this post I will illustrate how superior maneuverability can be used to escape from a faster predator.

What is maneuverability? We will define it in a narrow sense as the ability to quickly change the course or direction of motion. The rate of change of the direction of motion is also known as acceleration. The word acceleration is used colloquially when the rate of change of velocity is in the same direction as velocity. More generally, the vector of acceleration could point in any direction. If the acceleration vector points in the direction opposite to velocity, we would say that the moving object decelerates. Circular motion is sustained by a centripetal acceleration which points toward the center of the circle, perpendicular to the velocity vector.

To illustrate how a slower animal can successfully evade a faster one let us consider a simple model of the predator-prey pursuit. Suppose, the only constraint on the motion is the velocity and acceleration caps. The predator’s maximum velocity is greater than that of the prey. Vice versa, the prey can accelerate faster (in any direction) which means, among other things, that it can make sharper turns.

Here are the model pursuit strategies:


  • If traveling slower than the maximum speed, accelerate in the instantaneous direction of the prey at maximum acceleration.
  • When traveling at maximum velocity, project the acceleration vector on the direction perpendicular to the instantaneous velocity. This will insure that speed does not exceed the maximum.


  • If traveling slower than the maximum speed, accelerate away from the predator at maximum acceleration.
  • If traveling at maximum velocity and the predator is a certain distance D away, stay the course.
  • If traveling at maximum speed and the predator is within striking distance, execute a turn away from the predator at the tightest turning radius possible.

Even without doing the simulations of this model we can foresee the qualitative features of the trajectories it yields. When the prey is further than D away from the predator, it will run along a straight trajectory which means that the speedier predator will eventually catch up with it and draw within the distance of caution D. At that point the prey will commence a sharp turn away from the predator. The predator, being less agile, will not be able to turn as sharply and will overshoot the prey and the distance between them will grow and might exceed D. When that happens, the prey will stop turning and run along a straight line again. The cycle will repeat ad infinitum the predator not being able to get closer to the prey than some finite fraction of D.

The movie below shows the trajectories of the prey (green) and predator (red) produced by the simple model when the predator is 50% faster, but the prey is able to achieve twice the acceleration.

Finally, let me point out that the strategies in the simple model are far from optimal. For example, one can imagine that if the predator could anticipate the direction of the prey’s turn (which is possible in the above scenario in which the prey always turns away from the predator), it could potentially intercept the prey. The optimality of a particular escape — pursuit strategies is usually hard to prove and the methods of such proofs are still subject of current research.