# [Probability] Derangement / gambling problem

Tags:
1. Nov 13, 2015

### goraemon

1. The problem statement, all variables and given/known data
Alice proposes to Bob the following game. Bob pays one dollar to play. Fifty balls marked 1, 2, . . . , 50 are placed in a big jar, stirred around, and then drawn out one by one by Zori, who is wearing a blindfold. The result is a random permutation (let's call it s) of the integers 1, 2, . . . , 50. Bob wins with a payout of two dollars and fifty cents if the permutation s is a derangement, i.e., s(i) =/= i for all i = 1, 2, . . . , n. Is this a fair game for Bob? If not, how should the payoff be adjusted to make it fair?

2. Relevant equations
Derangement formula: ∑(k=from 0 to n) [(-1)^k * C(n,k) * (n-k)!]

3. The attempt at a solution
I got this far:
Probability that any given random permutation is a derangement:
(num of all derangements) / (num of all permutations) = ∑(k=from 0 to n) [(-1)^k * C(n,k) * (n-k)!] / 50! ≈ 1/e

Then, computing the expected win/loss, given that he gains $2.50 (for a net profit of$2.50 - $1 -$1.50) if he wins, and is out \$1.00 if he loses:
1.5(1/e) - 1(1-1/e) ≈ -0.08. (so on average, he'll lose roughly 8 cents per play)

Solving for the adjusted payment amount so that he'll break even in the long run...
(p-1)(1/e) - 1(1-1/e = 0
Solving for p, we get: p ≈ e

First, is the above correct? Right now I settled for an approximate answer (e) as the derangement equation seemed too messy to compute an exact answer. Is there a simpler way to get an exact answer? Thanks.

2. Nov 13, 2015

### Ray Vickson

As Feller (Introduction to Probability Theory, Vol. I) points out, the probability that in a permutation of $n$ numbers exactly $k$ of the numbers match (that is, we have $s(i) = i$ for $k$ of the numbers from $1$ to $n$) is
$$P(k \; \text{matches}) = \frac{1}{k!} \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots \pm \frac{1}{(n-k)!} \right).$$
In particular, for $k = 0$ and $n = 50$ we get your probability of a derangement (0 matches) as
$$P(\text{derangement}) = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{1}{50!}$$
This, of course, is the first 51 terms in the series expansion of $e^{-1} = 1/e$, and because you have an alternating series, the error made in stopping the computation of $1/e$ at $1/50!$ is smaller than $1/51! \approx 0.6446959640\, 10^{-66}$. So, your error in replacing the answer by $1/e$ is not too bad. Admittedly, this is an approximation, but the error would only show up at the 66th or 67th decimal place, if that is what you were worrying about.

Last edited: Nov 14, 2015