# Expected number of people to not get shot?

Suppose $n$ gangsters are randomly positioned in a square room such that the positions of any three gangsters do not form an isosceles triangle.

At midnight, each gangster shoots the person that is nearest to him. (A person can get shot more than once but each person can only shoot one person)

How many people are expected to survive? (I.e. what is the expected value of the number of people who do not get shot?)

E.g. For one person, the expected value is 1. For two people, it is zero since they both get shot. For three, the value is 1 since they form the vertices of a scalene triangle. I’m just interested in what happens as $n \rightarrow \infty$.

Thanks for your help!

# Summary:

The expected number of survivors after a shootout given as is, if not correct, almost certainly very close to being correct (see update 2).

However, this is disputed by Finch in Mathematical constants (again, see below for details). The results from Finch are easily replicable in Mathematica or similar, but I was not able to replicate even the partial results in Tao/Wu’s paper (despite leaving out the absolute values of $\alpha$ and $\beta,$ which Finch points out as being incorrect – see below for futher details), leaving me unsure as to whether I am missing something in my “translation” of the problem into Finch’s more modern notation. I should be most grateful if someone could illuminate me further in this matter.

Based on numerical tests, I would say the expected number of survivors for $n>3 \approx n/3.5$

Trial example test (code below): anim[20,8]: For $1000$ trials, $1\leq n\leq 40$ est[40,10^3]: Note

Using RandomReal it is very unlikely that any two distances will be exactly equal, thereby fulfilling the no isosceles triangle requirement.

# Update 1

History of the problem

Robert Abilock proposed in American Monthly The Rifle-Problem (R. Abilock; 1967),

$n$ riflemen are distributed at random points on a plane. At a signal,
each one shoots at and kills his nearest neighbor. What is the expected
number of riflemen who are left alive?

This was reposed as the Vicious neighbor problem (R.Tao and F.Y.Wu; 1986), where the answer of $\approx 0.284051 n$ remaining riflemen (or $\approx n/3.52049$) was given as the solution in $2$ dimensions.

This agrees distinctly with tests of sample-size $10^5:$ ListLinePlot[{const[#, 100000] & /@ Range@40}, GridLines -> {{}, {1/0.284051}}]


However, in Mathematical Constants Nearest-neighbor graphs (S.R.Finch; 2008), Finch states that

In [Vicious neighbor problem], the absolute value signs in the definitions of $\varphi$ and $\psi$ were mistakenly omitted.)$\dots$

Given the discrepancy between our estimate $\dots$ and their estimate $\dots$,
it seems doubtful that their approximation $\beta(2) = 0.284051\dots$ is entirely correct.

So the question (for the bounty) is then reduced to:

Has any progress been made since 2008 on the problem? In short, is Tao and Wu’s calculation incorrect, and if so, is a more precise estimate of $\beta(2)$ known?

# Update 2

I have also tested the problem in other regular polygons (circle, triangle, pentagon, etc.) for $10^5$ trials, $1\leq n \leq 30$, and it seems that the comment by @D.Thomine below is in agreement with the data gathered, in that the constant for any bounded $2$ dimensional region appears to be the same for large enough $n,$ ie, independent of the global geometry of the domain: while further simulations, using $2\cdot 10^6$ trials for $n=30$ and $n=100$ yielded the following results: with the final averages after $2\cdot 10^6,$ compared to Tao/Wu’s result, being:

indicating that the Tao/Wu result of $\lim_{n\rightarrow\infty}\operatorname{E}[n]\approx 0.284051\ n$ is, if not correct, almost certainly very close to being correct.

# Upper and lower bounds

Following up on @mathreadler’s suggestion that it may be interesting to study the spread of data, I include the following as a minor contribution to the topic:

Since arrangements like this are possible (and their circular counterparts, however unlikely through random point selection), clearly the lower bound for odd $n$ is $1$ and for even $n$ it is $0$ (since the points can be paired).

Finding an upper bound is less obvious though. Looking at this sketch proof for upper bound $n=10$ provided by @JohnSmith in the comments, it is easy to see that the upper bound is $7:$ and by employing the same method, upper bounds for larger $n$ can be constructed:       Assuming one can repeat this process indefinitely, it is likely that an upper bound for $n\geq 6$ then is $n-\lfloor n/3\rfloor:$ which has been set against the data for $2\cdot 10^4$ trials (red dots – see data below).

Regarding density of spread, (again with $2\cdot 10^4$ trials) produces the following plot: ListPlot3D[Flatten[data, 1], ColorFunction -> "LakeColors"]


(courtesy of @AlexeiBoulbitch here), and regarding max. density of spread along $x/z$ axes from above plot, produces the following: With[{c = 0.284051},
Show[ListLinePlot[Max@#[[All, 3]] & /@ data, PlotRange -> All],
Plot[{(1 + c)/(n - (1 + c)^2)^(1/2)}, {n, 0, 100}, PlotRange -> All,
PlotStyle -> {Dashed, Red}]]]


It is tempting to conjecture max height of distribution to be $\approx (c+1)/\sqrt{n-(c+1)^2},$ but of course this is largely empirical.

test[nn_] := With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]], aa[[#]]]}
& /@ Range@nn)},
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]},
With[{ee = Complement[Range@nn, dd]},
Column[{StringJoin[ToString["Expected: "], ToString[nn/3.5]],
StringJoin[ToString["Survivors: "], ToString[Length@ee], ToString[": "],
ToString[ee]], Show[Graphics[{Gray, Line@# & /@ cc}, Frame -> True,
PlotRange -> {{0, 1}, {0, 1}}, Epilog -> {Text[Style[(Range@nn)[[#]],
30/Floor@Log@nn], aa[[#]]] & /@ Range@nn}], ImageSize -> 300]}]]]]]

est[mm_, trials_] := ListLinePlot@({Quiet@With[{nn = #},
(N@Total@(With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]],
aa[[#]]]} & /@ Range@nn)},
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]},
With[{ee = Complement[Range@nn, dd]},Length@ee]]]]
& /@ Range@trials)/trials)] & /@ Range@mm, Range@mm/3.5})

anim[nn_, range_] := ListAnimate[test@nn & /@ Range@range,
ControlPlacement -> Top, DefaultDuration -> nn]

const[mm_, trials_] := With[{ans = Quiet@With[{nn = #},
SetPrecision[(Total@(With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]],First@Nearest[DeleteCases[aa, aa[[#]]],
aa[[#]]]} & /@ Range@nn)},
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]},
With[{ee = Complement[Range@nn, dd]},
Length@ee]]]] & /@ Range@trials)/trials), 20]] &@ mm}, mm/ans]

act[nn_, trials_] := With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]], aa[[#]]]} & /@
Range@nn)}, With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]},
With[{ee = Complement[Range@nn, dd]}, Length@ee]]]] & /@ Range@trials

data = Quiet@ Table[With[{tt = 2*10^4},
With[{aa = act[nn, tt]}, With[{bb = Sort@DeleteDuplicates@aa},
Transpose@{ConstantArray[nn, Length@bb], bb, (Length@# & /@
Split@Sort@aa)/tt}]]], {nn, 1, 100}];