Corrupt Official

A corrupted Chinese official brings $10 mln to Macau... and lost $7 mln of it. He'll be executed anyway, so he must win back $7 mln. His strategy is to play a 50/50 game, and bet $1 mln each time (not optimal, but that's not the point here). When are the chances of him winning back $7 mln?

Follow-up: what's the expected number of times this official will be playing this game before he learns his fate? (i.e. either lose it all or win back $7 mln)

Solution:

The gambler's ruin problem. The are many elegant solutions to this, but I like this the most. Based on the martingale stopping time theorem.

The expected value of his money is always the same--$3 mln, no matter when he stops playing the game, i.e. either when he's lost all or now back at $10 mln.

So, E[Money= ] $3 mln = Prob(going bust) * $0 mln + Prob (Get to $10 mln) * $10 mln

provided such probabilities exist (they do!). Prob (Get to $10 mln) = 1 - Prob(going bust), so we have:

3 = p*0 + (1-p)* 10 = 10 - 10p, 10p = 7/10 , p = 0.7.

In general, it's just a/(a+b). In this case, the chances of him getting executed is 70%.


Solution to the follow-up:

Yet another application of martingales. Martingales are just such wonderful animals.

The trick is to find a suitable martingale. You need to know that B²(t)-t is a martingale, where B(t) is a Brownian motion. This martingale is application here because we're dealing with a random walk.

So, we have:

E[B²(t) - t] = 0
E[B²(T) - T] = 0 T is when game ends; this substitution okay thanks to stopping time theorem
E[B²(T)] - E[T] = 0 expectations are linear
E[T] = E[B²(T)] rearrange

t is time. In this context, it's the number of times our corrupt official plays the game.

So, down to evaluating the left hand side. Substituting the numbers in:

E[B²(T)]
= P(win back $7 mln) (7²) + P(lose $3 mln) (3²)
= 3/10 * 49 + 7/10 * 9 = 21

So the expected number of games this official plays would be 21. Notice that we're essentially calculating the variance in the last step.

People Lining up at Bus Station

People line up at a bus station according to a Poisson distribution with 5 people / minute. The next bus will arrive some time in the next 2 minutes, with "some time" being a uniform distribution. How many people will get onto the next bus? What is the standard deviation of the number of people?


Solution:

The expected number of people waiting at time t is: E[Poisson(n)|t] = 5t.
Taking the expectation of this value over t = [0,2] we have: E[ E[Poisson(n)|t] ] = E [ 5t ] = 5.

So expect 5 people to get onto the next bus.

The standard deviation: use the variance formula, Var(Y) = Var( E[Y|X] ) + E[ Var(Y|X) ] with Y = number of people and X = time.

We have: Var(people) = Var ( E[People | t ] ) + E[ Var( People | t ) ]
The first term = Var ( E[Poisson(n, t)] ) = Var ( 5t ) = Int(0,2) { 1/2 * (5t - 5)² }dt = 0.5 * 25 * 1/3 * (t-1)³ | (2, 0) = 25/3.
Second term = E[ Var( Poisson (n,t) | t ] = E[ 5t ] = 5. Variance of Poisson process is just 5 for this case.


Total Variance: 5+ 25/3 = 13 1/3.

So standard deviation is ~ 3.65.

Transformation of Probability Distributions

Given X ~ f(x). What distribution is g(X)?

Solution:

Think in terms of F(x), the CDF, instead of f(x).
Let F_g be the CDF of g(X). Then:


F_g(x) = Prob ( g(X) ≤ x ) = Prob ( X ≤ g^-1(x) )


So the RHS is just: F( g^-1(x) ). Now to get PDF, it's just differentiation of this value.

Examples:

Find the CDF of X², given X ~ f(x), with CDF F(x).

F__x²(x) = Prob (X² ≤ x) = Prob ( -√|x| ≤ X ≤ √|x|) = F(√x) - F(-√x) , noting that domain for X² is [0, ∞).

Taking derivatives, we have:


½ * 1/√x * ( F´(√x) - F´(-√x) ) = ½ * 1/√x * ( f(√x ) - f(-√x ))


Find the CDF of e^X, given X ~ f(x), with CDF F(x).

F__e^X(x) = Prob (e^X ≤ x) = Prob ( X ≤ ln (x) ) = F(ln (x))


Taking derivative of RHS to get PDF:

d/dx (F (ln(x)) = 1/x d/d(ln(x)) F (ln (x)) = 1/x f(ln (x)) (since d/dx F(x) = f(x))