55
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Scott, how do you know that in your dodging maneuver, you didn't run into other zombies? $\endgroup$ – Joel David Hamkins Jul 29 '14 at 14:46
  • 11
    $\begingroup$ At the start you can pick a direction in which there are no zombies. Then just run in that direction and survive forever. $\endgroup$ – Pablo Lessa Jul 29 '14 at 14:50
  • 20
    $\begingroup$ 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. $\endgroup$ – Joseph Van Name Jul 29 '14 at 15:04
  • 3
    $\begingroup$ 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? $\endgroup$ – Joel David Hamkins Jul 29 '14 at 17:50
  • 5
    $\begingroup$ Countable many zombies, µ zombies/area on average $\endgroup$ – TROLLHUNTER Jul 29 '14 at 18:11
19
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Neat observation. We can also see this by just looking at the triangle formed by two zombies and you. $\endgroup$ – Christian Remling Jul 31 '14 at 19:44
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Paul Levy Jul 29 '14 at 20:02
  • $\begingroup$ 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? $\endgroup$ – Paul Levy Jul 29 '14 at 20:08
  • $\begingroup$ 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. $\endgroup$ – Will Sawin Jul 31 '14 at 17:40
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Christian Remling Aug 5 '14 at 23:43
  • $\begingroup$ One must cross many finite boxes to reach infinite. $\endgroup$ – Brendan Murphy Aug 6 '14 at 0:45
  • $\begingroup$ What do you mean by your third paragraph? You can always escape a finite collection of non-colluding zombies by Pablo Lessa 's method. $\endgroup$ – TROLLHUNTER Aug 6 '14 at 18:32
  • $\begingroup$ 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. $\endgroup$ – Marco Isopi Aug 7 '14 at 7:55
  • 1
    $\begingroup$ @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.) $\endgroup$ – usul Aug 8 '14 at 16:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Jul 29 '14 at 20:38
  • $\begingroup$ It seems that "head down the middle, don't stop, and don't slow down" is indeed an often portrayed strategy :) $\endgroup$ – Hagen von Eitzen Jul 31 '14 at 14:32
2
$\begingroup$

Simple pursuit

Zombies moving towards you will always catch you, but due to their lack of intelligence, your survival time increases exponentially with your relative speed. In $k=O(1)$ dimensional space ($k=2$ in the problem), the expected survival time is $d⋅(1/Θ(μd^k))^{(1+1/v)(1±o(1))/(k-1)}$ if $v$ is bounded below 1 and $μd^k→0$. I conjecture that for fixed $v$, the above $o(1)$ is unnecessary. If $μ$ depended on the distance $r$ from the origin, the threshold value for survival (at large $r$ and constant $v<1$) is $μ(r) = r^{-(k-1)v/(1+v)±o(1)}$ (the $o(1)$ is likely negative and necessary here).

Consider first the continuous field version of the problem: The initial density is $μ$ and the player loses when the mass within distance $d$ of the player reaches (or exceeds) 1. Let $r(t)$ be the trajectory of the player; $r(0) = 0$. If $a$ and $b$ are trajectories of two possible zombies, we have:
- $a'(t) = v \frac{r(t)-a(t)}{|r(t)-a(t)|}$
- $|b(t)-a(t)|$ is nonincreasing
- For small $|b(t)-a(t)|$, $b'(t) = a'(t) - \frac{v}{|a(t)-r(t)|} (b(t)-a(t))_⊥ + O(\frac{|b(t)-a(t)|}{|r(t)-a(t)|})^2$ where the orthogonal projection $(b(t)-a(t))_⊥ = b(t)-a(t)-(b(t)-a(t))⋅(r(t)-a(t)) \frac{r(t)-a(t)}{|r(t)-a(t)|^2}$.
- If $f_T(a(0)) = a(T)$, then the density at time $T$ at $a(T)$ is $μ/\det J_{f_T}$, and by integrating the above $b'$ equation, we get $\log \det J_{f_T} = -(k-1)v \int_0^T \frac{dt}{|r(t)-a(t)|}$.

Now among all $a$ and $r$ with $|a(T)-r(T)|≤d$, the integral (and thus the density) is minimized if $|a(0)|=(1+v)T+d$, which requires moving in a straight line from the origin at maximum speed. Furthermore, in this case, the density at $a(T)$ matches the average density within distance $d$ up to a constant factor, and the precise bounds in the first paragraph follow.

Lower bounds

For the nonfield version, we can get the lower bounds by escaping in a nearly straight line while avoiding traps. This is possible here even if the player velocity is always within $ε$ (if $ε$ is $Θ(1)$) of moving with speed 1 in the positive $x$ direction. Intuitively, on a straight line, the average distance between traps of size $O(d)$ is $O(1/(μ_1 d^{k-1}))$ (where $μ_1$ is the relevant field density; $1-v=Ω(1)$), and using the (approximate) independence, the frequency of larger traps drops exponentially with trap size, with the lower bounds (in the first paragraph) reached with high probability unless the initial position is a trap.

However, formalization of traps is a bit tricky, so we instead observe that we can trace out a trajectory of speed $1+v$ of sufficient clearance against the initial configuration, and then evolve it the same way as the zombies to get the escape trajectory. As long as all tangents of the initial trajectory are at an angle $≤α$ (for $α≤45°$) to the $x$ axis, this property will hold throughout the trajectory evolution, allowing us to ensure that the clearance will not shrink too much. For fixed $v$ ($μ$ does not depend on $r$), we can remove the $o(1)$ from the lower bounds for survival time by choosing a trajectory with variable $α$ with, at each point, $1/α$ at least polynomial in the distance between the point and the final destination.

Also, for $v=1$ (and small $d$) and variable $μ(r) = r^{-k/2+1/6-ε}$, you can survive by making your trajectory increasingly smooth: Zombies following you at a small distance gain on you at a speed proportional to the square of the path curvature (and the square of the distance to you), so with curvature $r^{-0.5-ε}$ you can avoid $d→0$ as $r→∞$ for those zombies. In a straight line path and $d=Θ(1)$, you will encounter zombies at typical intervals $s = Θ(1/(μ(r) r^{(k-1)/2}))$. Avoiding an incoming zombie from a distance $s$ uses correction $O(\sqrt s)$, corresponding to curvature $O(s^{-1.5})$, which is $O(r^{-0.5-ε_2})$ for the above $μ(r)$.

Also, for $v≤1$ and $d=0$, you can survive indefinitely (i.e. not lose at finite time) by simply moving at speed 1 in a straight line in any unoccupied direction — or even, with probability 1, by moving with speed 1 along any curve with bounded curvature, with the curve chosen independently of zombie positions.

Upper bound

For the upper bound, it suffices to consider a single point and a linear approximation to the problem. To escape, for every $R>0$, the player would have to cross (at time $O(R/v)$) an $a(t)$ that starts at the sphere $|a(0)|=R$. A player cannot approach $a(t)$ to within distance $d$ without increasing the field density at $a(t)$ in $ρ =(R/d)^{(k-1)/(1+1/v)}$ times. Furthermore, as long as the increase in density at $a(t)$ is $o(ρ)$ times, the cumulative relative nonlinearity within distance $O(d)$ of $a(t)$ is $o(1)$. (Proof outline: If the remaining density increase is $ρ_1$ times, then the distance of the relevant points to $a$ is $D=O(ρ_1^{1/(k-1)} d)$, and with the player far enough compared to $D^2/d$, the nonlinearity is small enough.) From there, for large enough $R$, $\{b(0):|b(t)-a(t)|≤d|\}$ contains a volume $ω(\log R)$ ellipsoid (contained within distance $O(R)$ from the origin). By a counting argument, with probability $1-o(1)$ all such ellipsoids contain at least one relevant point, as required. For the bounds without $o(1)$, we are off by a factor of $\log(1/(μd^k))$ inside the $Θ(μd^k)$. However, I expect that the $\log$ factor can be eliminated by using the player path rather than a single point $a(t)$ and by analyzing the impact of nonlinearities.

Intelligent pursuit

If zombies (in $k = O(1)$ dimensional space) could strategize and cooperate, and letting $D=\frac{1}{μd^{k-1}v}$, they could surround you with gaps $<d$ in time $O(D)$ and capture you in time $O(D + \frac{\log^{1/k}(1+Dμ^{1/k})}{μ^{1/k}v})$ (and even do this with a strategy independent of your movement; also, the second summand is typically small and stems from random fluctuations in zombie density). You cannot escape for $μ(r) = ω(1/r^{k-1})$. I do not know whether you can escape if $μ(r) = O(1/r^{k-1})$ (and $d$ is small enough and $v<1$); Conway's angel problem has some of the similar subtleties.

At $v<1$, a fixed finite number of zombies cannot capture you at a small enough $d$ since you can perturb your path (with sufficient smoothness and clearance) to avoid the first zombie, use a smaller scale perturbation against the second one, and so on. For the naive implementation, you might have to avoid the $n$th zombie $2^{n-1}$ times, and your clearance drops exponentially with $n$. However, by considering groups of zombies, you can cut off a fraction at each length scale, allowing a polynomial clearance, and you can escape at density $μ(r) = r^{-k+ε}$ for a small enough $ε>0$ dependent on $v$ (and small enough $d$ dependent on $v,ε$).

At $v=1$, $k+1$ well-placed zombies (i.e. 3 for the plane) can win in finite time even at $d=0$. The reason is that a single pursuer can guard a half-space. They can even (deterministically) win if they have nonzero but small enough reaction time proportional to distance (i.e. the speed of light is finite). A single pursuer can guard a slowly receding half-space, allowing 1 (effectively 2) out of $k+1$ pursuers to advance.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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