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.

Thanks for your help!

Answer

Summary:

The expected number of survivors after a shootout given as lim 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.

Original answer:

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

Trial example test[20] (code below):

enter image description here

anim[20,8]:

enter image description here

For 1000 trials, 1\leq n\leq 40 est[40,10^3]:

enter image description here

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:

enter image description here

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:

enter image description here

while further simulations, using 2\cdot 10^6 trials for n=30 and n=100 yielded the following results:

enter image description here

with the final averages after 2\cdot 10^6, compared to Tao/Wu’s result, being:

\begin{align}
&n=30:&0.284090\dots\\
&n=100:&0.284066\dots\\
&\text{Tao/Wu:}&0.284051\dots\\
\end{align}

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

enter image description here

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:

enter image description here

and by employing the same method, upper bounds for larger n can be constructed:






enter image description here

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:

enter image description here

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:

enter image description here

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:

enter image description here

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}];

Attribution
Source : Link , Question Author : John Smith , Answer Author : Community

Leave a Comment