Does Crime Pay in the Den of Thieves? [Solution]

Solution for the week of 2/2/25

Our problem from 2/2/25 was

[…] we will explore a game I’ve been calling Den of Thieves. In this game we have n thieves that each have $1. The game proceeds in rounds where every thief simultaneously and anonymously selects a target. If a player has been selected by at least one thief, they lose the money they had at the start of the round (but they will still gain the money for their theft for the round). Each thief will gain the amount money of their victim unless other thieves also selected this target. In this case, all the thieves split the money evenly (in this game world, there is some honor among thieves). To clarify, all of the money loses occur before collecting your ill-gotten gains so even if you are stolen from, you will still end the round with whatever amount you stole from your victim.

Our first question is, what is the distribution of money a thief has after round 1 if there are 10 thieves and each starts with a dollar? How about if n is very large?

For this game there’s only one decision each thief needs to make; who to steal from. In the case of the first round, this is pretty straightforward given that everyone starts with the same amount of money. They will just pick any player except themselves with uniform probability. Since we don’t know who everyone else is picking, there’s a chance multiple thieves will select the victim. Again, given that every target’s starting amount is equal, our payout in the first round depends only on the number of other thieves targeting our same victim, we can determine our gain by determining the distribution of T_j other thieves targeting the same victim j that we selected.

In particular, if we assume we are player i and we target player j, then there is a

\(P[v_k = j] = \frac{1}{n-1}\)

chance that player k has also selected j as a victim (let v_i be the victim selected by player i). The n-1 simply comes from the fact that a thief has no incentive to select themself as a target.

Since each thief behaves in the same way, we can model T_j—the the number of other thieves targeting j—to be binomially distributed.

\(T_j = \binom{n-2}{t-1} \left( \frac{1}{n-1}\right)^{t-1} \left( \frac{n-2}{n-1} \right)^{(n-2)-(t-1)} = \binom{n-2}{t-1} \left( \frac{1}{n-1}\right)^{t-1} \left( \frac{n-2}{n-1} \right)^{(n-t-1)}\)

The n-2 comes from the fact that we have assumed (i) targets j, so we ignore that possibility, and j won’t target itself. The t-1 is also to account for the fact that we have assume i is targeting j.

So now we have an expression for distribution of the number of other thieves that will target our selected victim. As such our expected payout is 1/T. The other key part of our wealth after 1 round depends on if we robbed and lose our current wealth. We avoid this outcome if all n-1 other players select someone other then us (and they won’t select themselves of course)

\(P[T_i=0] = \left( 1 - \frac{1}{n-1} \right)^{n-1} = \left( \frac{n-2}{n-1} \right)^{n-1}\)

This is actually the same is T_j evaluated at t=0, which makes sense since T_j at t=0 represents the probability of 0 people targeting a player j and all players are symmetric at this point in the game.

So we can pull both of these together into a slightly messy form

\(W = \begin{cases} 1 + \frac{1}{1+t}, & \text{with probability } P(T=0) \text{ i.e. }\left(\frac{n-2}{n-1}\right)^{n-1} \\[1.5ex] \frac{1}{1+t}, & \text{with probability } P(T \neq 0) \text{ i.e. } \left(1 - \left(\frac{n-2}{n-1}\right)^{n-1}\right) \end{cases}\)

where

\(P[T=t] = \binom{n-2}{t-1} \left( \frac{1}{n-1}\right)^{t-1} \left( \frac{n-2}{n-1} \right)^{(n-t-1)}\)

t goes from 1 to n-1. I wasn’t exactly sure how to neatly deal with the t-1 index without rewriting the equation so I kinda left it as is without writing it explicitly as a Binomial function even though it is. If we plug in 10 into this equation we get the following distribution.

Now what happens when the number of players get’s very large. Well, our whole equation is governed by the same distribution, just applied to two different ways. So if we can determine what happens to the distribution as n get’s large, that should tell us everything we need to know.

So what happens to a binomial distribution as n get’s large

\(\lim_{n \rightarrow \infty} \text{Binomial}(n,p) = \lim_{n \rightarrow \infty} \binom{n}{k} p^k (1-p)^{n-k}\)

This part is a bit involved/unintuitive you aren’t already familiar with the result but there’s an interesting result that as you let n go to infinity, the binomial distribution converges on the Poisson distribution where λ=np

\(\lim_{n \rightarrow \infty} \binom{n}{k} p^k (1-p)^{n-k}\)

If we recall some of our standard limit identities, we can recognize that this looks pretty similar in form to

\({\displaystyle \lim _{x\to +\infty }\left(1+{\frac {k}{x}}\right)^{mx}=e^{mk}}\)

So let’s see if we can get it into something like this.

Letting λ=np, writing the binomial coefficient a little unconventionally and rearranging terms a little, we can get

\(\lim_{n \rightarrow \infty} \left( \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{n^k} \right) \left( \frac{\lambda^k}{k!} \right) \left( 1-\frac{\lambda}{n} \right) ^{n-k} \)

The first term converges to 1 as n get’s large so we can simplify it out of the equation. Also, the “minus k” of n-k becomes unimportant.

\(\lim_{n \rightarrow \infty} \left( \frac{\lambda^k}{k!} \right) \left( 1 - \frac{\lambda}{n} \right) ^n \)

And just like that, the second term is in the form of the identity above.

\(= \left( \frac{\lambda^k}{k!} \right) e^{-\lambda}\)

Which is exactly the form of the Poisson distribution. The last remaining question is, what parameter of λ does our distribution converge to? Recall that in or case “n” of the standard binomial distribution was n-2 and “p” was 1/(n-1)

\(\lim_{n \rightarrow \infty} \lambda = \lim_{n \rightarrow \infty} (n-2) \frac{1}{n-1} = 1\)

So for large n, the wealth distribution is given by

\(W = \begin{cases} 1 + \frac{1}{1+t}, & \text{with probability } P(T=0) \text{ i.e. } \frac{1}{e} \\[1.5ex] \frac{1}{1+t}, & \text{with probability } P(T \neq 0) \text{ i.e. } 1 - \frac{1}{e} \end{cases}\)

where

\(P[T=t] = \frac{1}{e \cdot t!}\)

Plotting this we get

And there we have it!

As always, please comment with any thoughts or feedback you had on this problem or if you approached it differently. Thanks for reading!