N people in a pit are required to press their kill buttons one at a time, what percentage of the initial population is expected to live on?

Question

I posed this problem for myself based on a simpler problem I saw on reddit, here is the more detailed version of my problem:

The game master traps N people in a pit and equips them with a sort of kill button. When the button is pressed for the first time it will kill a random person, possibly even killing the button presser. The button cannot be pressed a second time (it simply wont do anything). The game master has each person take a turn pressing their button (if they are still alive). What percentage of the initial group of N people will remain?

I am more specifically after $\lim_{n\to \infty} \frac{F(n)}{n}$ Where F(n) is the number of people who remain from an initial population of n people.

I made a basic computer simulation of this scenario for an initial population of n people. As I plugged in bigger n values it became obvious that the percentage remaining was approaching 1/e.

I've been trying to show on paper that $\lim_{n\to \infty} \frac{F(n)}{n} = \frac{1}{e}$ and can't seem to get it, help would be appreciated.

Some useful information:

1. A person can only press their button once.
2. The people press their buttons one at a time.
3. The button will always kill someone. (It will not try to kill an already dead person)
4. The button can kill the button presser.
5. Every living person has an equal chance of being chosen by the button.

Information that I have gathered on the problem:

1. The best case scenario happens when the kill buttons always choose to kill someone who has yet to use their button. Resulting in a remaining population of n/2.

2. The worst case scenario is when the kill button kills the user every time, resulting in a remaining population of 0.

3. The functional equation $$f(n,p) = \left(\frac{n}{p}\right)f(n-2,p-1)+\left(1-\frac{n}{p}\right)f(n-1,p-1)$$ With base cases: $$f(0,p)=p$$ $$f(1,p)=p-1$$ Represents the expected number of survivors for a given initial population of p where only the first n are assigned kill buttons. For which $f(n,n)$ is the same as $F(n)$ that I defined earlier.

Easier reddit question: n people in a room randomly vote for $1$ person to be killed. When the voting period is over anybody with $1$ vote or more gets killed. What percentage of the initial n people survive?

Important info:

1. Multiple people can vote for the same person.
2. Everyone gets $1$ vote.
3. All of the deaths happen at the same time.

Answer: The probability that someone votes for you is $\frac 1n$, so the probability that someone does not vote for you is $1-\frac 1n$. Then the probability that nobody votes for you is $\left(1-\frac{1}{n}\right)^n$. The limit as n goes to infinity of that expression is also $\frac 1e$.

Why do these problems seem to have the same answer? My problem seems to be fundamentally different from the reddit one as:

1. In my scenario one person kills one person, multiple people can't be responsible for a single death.
2. In my scenario it is possible for someone to die before or after they kill someone themselves, where that isn't true in the case of the reddit problem.

Answer 1

Just some input on the relationship between the two scenarios

Consider the following scenario that is related, but not quite equivalent (see comments) to the scenario described in the OP:

In a group of $n$ people, each person randomly casts a vote for someone in the group (possibly themselves). A permutation of this group of people is chosen, and they are executed in that order. The conditions for their execution is still that they need to have at least one vote, and another condition is added that whoever voted for them must still be alive.

Given a specific voting $\mathcal{V}$ and a specific person $i$(a function from $[n] \to [n]$), define $f_i(\mathcal{V})$ to be the number of permutations of execution in which the person gets killed. The probability that they get killed as a function of $n$ is then

$$P(n,i) = \frac{1}{n^n}\sum_{\mathcal{V}} \frac{f_i (\mathcal{V})}{n!} $$

$n^n$ is just the number of votings (number of functions from $[n]\to [n]$)

The idea then is that we can write $f_i(\mathcal{V})$ as a difference of two functions. Define $g_i(\mathcal{V})$ as $n!$ if person $i$ was voted for at all (if $i$ is in the range of $\mathcal{V}$) and 0 otherwise. If you replace $f_i$ with $g_i$ in the above sum, it gives you the probability that a person gets executed in the simultaneous execution scenario, then define $h_i(\mathcal{V})$ as the number of permutations of $[n]$ in which a person gets saved by the order in which the execution takes place corresponding to that permutation. It should then be clear that

$$f_i(\mathcal{V}) = g_i(\mathcal{V}) - h_i(\mathcal{V}) $$

($h_i(\mathcal{V})$ is $0$ when $i$ is not in the range of $\mathcal{V}$)

So

$$P(n,i) = \frac{1}{n^n}\left(\sum_{\mathcal{V}} \frac{g_i (\mathcal{V})}{n!} - \sum_{\mathcal{V}} \frac{h_i (\mathcal{V})}{n!} \right)$$

Note that

$$ \frac{1}{n^n}\sum_{\mathcal{V}}\frac{h_i(\mathcal{V})}{n!} \to 0$$

If and only if

$$P(n,i) \to \frac{1}{e} $$

So it is this $h_i$ function that relates these two situations, and it seems reasonable that the expected value of $h_i(\mathcal{V})$ should become relatively small, since for $i$ to be saved, every person that voted for them needs to have themselves survived the voting process for that permutation up to the point where $i$ appears in the permutation. But I failed to compute an expression for $\mathbb{E}[h_i(\mathcal{V})]$ so this is as much as I can contribute.