Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider zombies placed uniformly at random over $\mathbb{R}^2$ with asymptotic density $\mu$ zombies/area. You are placed at a random point and can move with speed $1$. Zombies move with speed $v\leq 1$ straight towards you, what is the probability $P(\mu,v)$ you can escape to infinity without a zombie catching you?

What if the zombies can move in any direction and might collude to set up a wall of high density or similar tactics?

Lets call it a win for zombies if for every $d>0$, one of them can get within a distance $d$ in finite time.

Addendum: Is there a finite collection of colluding zombies and a player placement, from which escape is impossible? What is the least number of zombies?

share|improve this question
2  
Scott, how do you know that in your dodging maneuver, you didn't run into other zombies? –  Joel David Hamkins Jul 29 at 14:46
11  
At the start you can pick a direction in which there are no zombies. Then just run in that direction and survive forever. –  Pablo Lessa Jul 29 at 14:50
17  
If the zombies can strategize, then regardless of how slow the zombies, walk the zombies can easily form a circle around you of a sufficiently large radius before you make it to the boundary of the circle so that whenever you cross from the inside of the circle to the outside of the circle, the zombies will be in a $d$ distance of you. All the zombies have to do is form a sequence of circles of radius say $2^{n}$ for all $n$ and the zombies are simply commanded to walk to the boundary of the nearest circle. –  Joseph Van Name Jul 29 at 15:04
2  
Could the OP clarify the precise sense of density he or she has in mind? One could imagine "density $\frac12$" meaning that asymptotically Lebesgue measure half the points in the plane are occupied by a zombie (in particular, continuum many zombies, very difficult situation); or one could intend alternatively one zombie per two unit squares on average (countably many zombies, perhaps easier). What is meant exactly? –  Joel David Hamkins Jul 29 at 17:50
4  
Countable many zombies, µ zombies/area on average –  user1708 Jul 29 at 18:11

5 Answers 5

This is not an answer but is too long for a comment. The point is that the distance between any two zombies is non-increasing with time no matter what your strategy.

Change the coordinate system so that you're at the origin at all times and assume that zombies move at speed $1$ (the stupid, non-colluding kind of zombie). If your speed is zero then the zombies move according to the flow of the vector field $$X_0(x,y) = (-\frac{x}{r},-\frac{y}{r})$$ where $r = (x^2 + y^2)^{-\frac{1}{2}}$.

If your velocity at time $t$ is $v(t) = (\alpha(t),\beta(t))$ then the zombies move in the new coordinate system according to the flow of the time dependent vector field $$X(t) = X_0 - v(t).$$

The differential of the vector field $X(t)$ is exactly the same as that of $X_0$. Hence for any choice of $v(t)$ the differential is symmetric, has an eigenvalue $0$ corresponding to the radial direction and an eigenvalue $-1/r$ corresponding to the tangential direction. In particular the divergence is negative so the flow contracts area. Also, the flow is a semi-contraction of distance so that no matter what strategy you use you can never make the pack of zombies less dense.

share|improve this answer
3  
Neat observation. We can also see this by just looking at the triangle formed by two zombies and you. –  Christian Remling Jul 31 at 19:44

Area grows faster than length, so the zombies eat you, as Joseph Van Name said.

It is sufficient for the zombies to form an uncrossable circular barrier enclosing you and then to shrink the circle till the catch you.

To form an uncrossable circular barrier, there need to be $2\pi r/d$ zombies. For the zombies to reach their position on the barrier before you can (taking your original position as the origin), they must have an initial radius between $r(1-v)$ and $r(1+v)$. The number of zombies in this region is $\pi r^2 \mu((1+v)^2-(1-v)^2)=4\pi r^2 \mu v$. Given $d, v, \mu$, take $r$ large enough, and the zombies easily form the circular barrier before you reach it.

EDIT: This does not answer the original question, as it allows the zombies to apply a strategy. In this strategy, all the zombies with initial radius between $(1-v)r$ and $r$, move away from the runner to form the circle, rather than directly towards the runner, as specified in the original question.

share|improve this answer
    
It isn't clear to me that $2\pi r/d$ zombies being within the radii you mention implies that a circle of radius $r$ can be formed in the required time - all this says is that that many zombies can reach the required circle, not that they can spread around it so that all segments of length $d$ contain a zombie. –  Paul Levy Jul 29 at 20:02
    
Ok, maybe refine it by saying that since a length $d$ segment of the circle of radius $r$ has angle $d/2\pi r$, and the number of zombies in this sector, between the radii of $r(1-v)$ and $r(1+v)$ is therefore $2rd\mu v$. Now the question is how big do we have to take $r$ so that the probability of having a zombie in every one of these areas is close to 1? –  Paul Levy Jul 29 at 20:08
    
As long as area of each sector grows exponentially, the probability of not having any zombies in the sector falls superexponentially. Since the number of segments grows exponentially, by the union bound you're the probability of each segment having a zombie is close to 1. –  Will Sawin Jul 31 at 17:40

It seems the most reasonable way to formalize the problem is saying that at start the zombies are distributed according to a Poisson process in the plane with density $\mu$. As this is (distributionally) translation invariant we can assume that you start at the origin.

Now we observe that changing the zombie configuration in any finite box will not affect the outcome. This tells us the event "getting caught" belongs to the tail $\sigma$-fleld. So by Kolmogorov's 0-1 law the probability is either 0 or 1.

[EDIT] I wrote "So it suffices to show said probability is positive. As pointed out by other readers it is easy to see that there are ways to position zombies at a short distance from the human as to guarantee capture in a short time. As such configurations have positive probability, we are done." This is wrong. You can indeed escape as pointed out by Pablo Lessa. You will be infinitely many times closer to a zombie than any given distance, but you will make it safely to infinity. [EDIT]

If zombies are allowed to have a strategy then Joseph Van Name's answer already tells the whole story.

share|improve this answer
2  
Could you elaborate on your second paragraph please? If I get caught by some zombies and now remove these, that does seem to affect the outcome. –  Christian Remling Aug 5 at 23:43
    
One must cross many finite boxes to reach infinite. –  Brendan Murphy Aug 6 at 0:45
    
What do you mean by your third paragraph? You can always escape a finite collection of non-colluding zombies by Pablo Lessa 's method. –  user1708 Aug 6 at 18:32
    
Christian Remling: since it is a long way to infinity, if you remove those zombies, sooner or later you will run into a (local) configuration which is as close as you need to the one you disposed of. Not only the monkey types War an Peace if you wait long enough. It will do it many, many times. –  Marco Isopi Aug 7 at 7:55
1  
@Marco, but if you have been moving for a long time, the zombies have been moving for a long time as well and with a coordinated group motion. How do we know that their motion can produce any local configuration after any length of time? (Especially if we do not know the walker's strategy.) –  usul Aug 8 at 16:39

Even if all the zombies do is walk toward you, they will win if they are uniformly distributed and know where you are. Common sense says that you do not walk toward a potential infinity of zombies, each of whom can sense you. If they have nonzero speed, they will converge toward you.

Lets assume zombies know less about pursuit curves than I do, but that they know some geometry as well as being able to determine your velocity. If they are uniformly distributed in a region which excludes a radial section no bigger than 2 arctan(mu/nu) (Edit, I mean 2arctan nu: mu is not a velocity of you) they either follow you or go at a constant rate normal to and intercepting your path. Since there are infinitely many of them, they will have enough time for one of them to reach you. If the radial arc is larger, head down the middle, don't stop, and don't slow down.

share|improve this answer
    
For a finite number of zombies, there may be escape strategies depending on how they are located. If they are arranged just inside the perimeter of a circle and collectively cover enough degrees of arc, you are zombie toast with butter. Better hope they prefer cream cheese. –  The Masked Avenger Jul 29 at 20:38
    
It seems that "head down the middle, don't stop, and don't slow down" is indeed an often portrayed strategy :) –  Hagen von Eitzen Jul 31 at 14:32

Some trivial, perhaps misguided musings:

Start in the direction opposite the nearest zombie. Continue until you are equidistant from $N > 1$ zombies, then go along a direction bisecting the line segment between any pair of them. You have two (nondegenerate) choices: towards or away from the pair. If the pair are sufficiently close to each other, this strategy requires that you go away from the pair.

In this way this strategy can lead to a trap in certain conditions for $N > 2$, but typically $N = 2$. So let's consider this case. The pair effectively merge once they reach the bisector. At (or before) that point you have a new pair, typically with a different bisector (amusing aside: the atypical case is akin to a "pickle" in baseball: http://en.wikipedia.org/wiki/Rundown). Again, you may have two choices, or only one.

It seems to me that the key in a proof would be to show when this strategy (which I think is plausibly optimal in at least some cases) allows you to increase the distance to the nearest zombie.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.