<jupyter_start><jupyter_text>The Riddlerhttps://fivethirtyeight.com/features/who-steals-the-most-in-a-town-full-of-thieves/>A town of 1,000 households has a strange law intended to prevent wealth-hoarding. On January 1 of every year, each household robs one other household, selected at random, moving all of that house’s money into their own house. The order in which the robberies take place is also random and is determined by a lottery. (Note that if House A robs House B first, and then C robs A, the houses of A and B would each be empty and C would have acquired the resources of both A and B.)> > Two questions about this fateful day:> > 1. What is the probability that a house is not robbed over the course of the day?> 1. Suppose that every house has the same amount of cash to begin with — say \$100. Which position in the lottery has the most expected cash at the end of the day, and what is that amount?  Part one> What is the probability that a house is not robbed over the course of the day?We will assume that a house cannot rob itself, so if there are 1000 houses, there are 999 times a house can be robbed.  The probability of being robbed each time is independent from round to round.  The probability of not being robbed in a single round is $\frac{999}{1000}$ and the probability of not being robbed in any given two rounds is $\frac{999}{1000}^2$.  The probability of not being robbed in 999 rounds is $\frac{999}{1000}^{999}$ which works out to 0.368063.We assume a house cannot rob itself, so for 1000 rounds there are only 999 chances of being robbed.<jupyter_code>(999/1000)**999<jupyter_output><empty_output><jupyter_text>Let's plot the probability of any one house not getting robbed if there are N homes.<jupyter_code>%matplotlib inline
import numpy as np
import pandas as pd
import seaborn as sns

idx = range(1, 1001)
s = pd.Series([((i-1)/i)**(i-1) for i in idx], index=idx)
print(s.tail(1))
s.plot()
1/np.e<jupyter_output><empty_output><jupyter_text>Part two> Suppose that every house has the same amount of cash to begin with — say $100. Which position in the lottery has the most expected cash at the end of the day, and what is that amount?Assumption: people do not choose themselves to rob.Some notation:- $N$ is the number of houses.  It is 1000 in this example, but we will consider it a fixed variable.- $X$ is the value that each house starts with.  It is \$100 in this example.- The current round is $r$ and starts at 1 and goes to N.    - There are $r-1$ houses before and $N-r$ houses after.- The probability of not being robbed in $n$ rounds is $P(n)$ where$P(n) = (\frac{N-1}{N})^n$- $E_{r,i}$ is the expected value of the house at position $r$ at the conclusion of turn $i$.- $G_r$ is the expected value of the gain for the turn of the house at position $r$.And some assumptions:- People cannot randomly pick themselves to rob. SolutionThis problem can be broken down into three parts, where we consider a house at position $r$.1. What is the expected value of house $r$ at the beginning of the turn?2. What is the expected value of the gain of house $r$?3. What is the expected value for house $r$ at the end of all rounds?For part one, the expected value of house $r$ at the beginning of the turn is just the starting value times the probability of not being robbed in $r-1$ turns.$E_{r,r-1} = P(r-1)X$For part two, the expected gain is the total amount of money in other houses divided by the number of houses. In the case where the house at position $r$ has not been robbed, the amount of money in other houses is $(N-1)X$, while if the house has been robbed the amount is $NX$.  The probability of not being robbed at the start of this turn is $P(r-1)$ and the probability of being robbed is $1-P(r-1)$.  So the expected value of the gain of this turn is given by$$\begin{eqnarray} G_r &=& P(r-1)\frac{(N-1)X}{(N-1)} + (1-P(r-1))\frac{NX}{(N-1)} \\&=& P(r-1)X + (1-P(r-1))\frac{NX}{(N-1)}\end{eqnarray}$$So the expected value of the house at position $r$ at the conclusion of their turn is given by:$$\begin{eqnarray} E_{r,r} &=& E_{r,r-1} + G_r \\&=& P(r-1)X + P(r-1)X + (1-P(r-1))\frac{NX}{(N-1)}\end{eqnarray}$$And for part three, the expected value at the end of all rounds is the expected value at the end of turn $r$ times the probability of not being robbed in the subsequent $N-r$ rounds.$$\begin{eqnarray} E_{r,N} &=& E_{r,r} * P(N-r) \\&=& (P(r-1)X + P(r-1)X + (1-P(r-1))\frac{NX}{(N-1)}) * P(N-r)\end{eqnarray}$$<jupyter_code>import matplotlib.pyplot as plt
import numpy as np

X = 100
N = 1000

def p(n, N):
    """The probability of not being robbed in `n` turns,given each turn picks one house
    at random from `N` houses."""
    return np.power((N-1)/N, n)

r = np.arange(1, N+1)
# expected value at the start of turn
E_pre = p(r-1, N) * X

# expected gain
G = p(r-1, N)*X + (1-p(r-1, N))*N*X/(N-1)

# exected value at the end of the turn
E_post = E_pre + G

# expected value at the end of all rounds
E = E_post * p(N-r, N)

df = pd.DataFrame(data={'E_pre': E_pre, 'gain': G, 'E_post': E_post, 'E': E}, index=r, 
                  columns=['E_pre', 'gain', 'E_post', 'E'])
df
df.plot.line()<jupyter_output><empty_output><jupyter_text>So we see that the later in the lottery the better the house fares.  And the house at position \1000 has an expected value of \$136.869606.<jupyter_code>from ipywidgets import interact, interactive, fixed, interact_manual
import ipywidgets as widgets

def plot_expected_values(N=1000):
    X = 100
    def p(n, N):
        """The probability of not being robbed in `n` turns,given each turn picks one house
        at random from `N` houses."""
        return np.power((N-1)/N, n)

    r = np.arange(1, N+1)
    # expected value at the start of turn
    E_pre = p(r-1, N) * X

    # expected gain
    G = p(r-1, N)*X + (1-p(r-1, N))*N*X/(N-1)

    # exected value at the end of the turn
    E_post = E_pre + G

    # expected value at the end of all rounds
    E = E_post * p(N-r, N)
    
    df = pd.DataFrame(data={'E_pre': E_pre, 'gain': G, 'E_post': E_post, 'E': E}, index=r, 
                  columns=['E_pre', 'gain', 'E_post', 'E'])
    ax = df.plot.line()
    ax.set_title('N = {}'.format(N), fontsize=18)
    ax.set_ylim(bottom=0)
    plt.show()


interact(plot_expected_values, N=widgets.IntSlider(min=2,max=1000,step=1,value=100));<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11684441656210791, 'fraction_numerical': 0.027760351317440403, 'mean_word_length': 3.8019578313253013, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '523064', 'license': 'MIT', 'n_tokens_mistral': 2219, 'n_tokens_neox': 2056, 'n_words': 941, 'path': 'fivethirtyeight/2017-06-30 Who steals the most in a town full of theives.ipynb', 'repo_name': 'dennisobrien/PublicNotebooks', 'size': '6376'}