Ceasar's Mind

Here’s an interesting problem that might be useful to know in the future.

Ten hunters are waiting for ducks to fly by. When a flock of ducks flies overhead, the hunters fire at the same time,, but each chooses his target at random, independently of the others. If each hunters independently hits his target with probability p, compute the expected number of ducks that escape unhurt when a flock of size 10 flies overhead.

Solution

Let X_i equal 1 if the i-th duck escapes unhurt, and 0 otherwise, for i = 1, 2, …, 10. The expected number of ducks to escape can be expressed as:

E[X_1 + ... + X_10] = E[X_1] + … + E[X_10]

To compute E[X_i] = P{X_i = 1], we note that each of the hunters will independently, hit the the i-th duck with probability p/10, so: P{X_i=1} = (1 – (p / 10)) ^ 10 (that is, the chance that the duck escapes unharmed is equal to the chance that none of the hunters hit it). Hence, E[X] = 10 * (1 – (p / 10)) ^ 10.

(Just for reference, if p = 1, E[X] = 3.49.)

More generally, E[X] = T * (1 – (p / T)) ^ S, where T represents the number of targets, and S the number of shooters.

This is pretty cool in my opinion, as the problem shows up a lot in various games (although a lot of games use algorithms to determine which unit to fire at rather than chance), Tower Defense games perhaps being the most obvious.

So in Stat class a short while ago, we learned about the Gambler’s Ruin. The idea goes like this,

Two gamblers, Alice and Bob, bet on the outcomes of successive flips of a coin. On each flip, if the coin comes up heads, Alice collects $1 from Bob, whereas if it comes up tails, Bob collects $1 from Alice. They continue to do this until one of them runs out of money. If it assumed that the sucessive flips are independent and each flip results in a head with probability p, what is the probability that Alice ends up with all the money if she starts with $A and Bob starts with $B?

The solution, in all its glory, is explained here for the statistically inclined. For those who’d rather just know the answer though, it ends up working out to be that Alice will beat Bob with probability 1 – (q/p)^A / ( 1 – (q/p)^(A + B) ) if her probability of winning a flip isn’t 1/2, and simply A / (A + B) if the game is fair.

Eight examples of the way the game could go.

This is an interesting result with fairly straightforward implications. Since your chance of cleaning the other player out is equal to the amount of money you bring over the total amount of money at the table then if your opponent is a casino you lose. It’s also interesting to note that even if you always bet $2, $5, or any number of dollars for that matter at each flip, the end result is the same.

It’s far more interesting to note however that using a Martingale betting strategy completely nullifies what we have here. In an earlier post, I explained how a Martingale strategy always has an expected value of $0. However, since both Alice and Bob are playing for finite amounts of money, it’s possible that Alice could enter with less money than Bob and still clean him out! Unfortunately, I don’t know the math behind this and when I asked the professor about it he only said we might cover the answer later in the course and referred me to studying stochastic processes, so expect a post on that soon!