AHOY! The Pirate Story Solution

University Mathematics

So I posted up a question titled “AHOY! The Pirate Story Problem” which can be found here.

Here is the solution!

We begin with a more intuitive idea.
Consider only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates (his vote will be the decisive vote), the proposal has to be accepted leaving Pirate 1 with nothing.

Now, we increase it by 1 more pirate by considering 3 pirate. Since Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Well, you may argue that Pirate 1 can demand more. However, Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

Next what if there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the coin distribution will be {0, 1, 0, 99}. Getting the hang out it?

Now 5 pirates! Pirate 5 needs 2 votes to get his proposal accepted and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

Here our approach uses backward induction, a very useful tool in Game Theory. 🙂

Question of the Day #13

JC Mathematics, University Mathematics

A student asked me this question recently. I think this is from AMC.

There are 42 points P_1, P_2, P_3, \ldots , P_{42} placed on a straight line so that each distance from P_i to P_{i+1} is \frac{1}{i} where 1 \le i \le 41. What is the sum of the distances between every pair of these points?

AHOY! The Pirate Story Problem

University Mathematics

So here is an interesting question. This actually appeared in a job interview at Google too. 🙂 So give it a shot if you’re keen. There are many ways to solve this, one can solve it mathematically using optimisation, or using Game Theory’s Backward Induction.

There are five pirates who have to split 100 gold coins. They all line up and proceed as follows:
1. The first pirate in line gets to propose a way to split up the gold coins (for example: everyone gets 20 gold coins).
2. The pirates, including the one who proposed, vote on whether to accept the proposal.
3. If the proposal is not accepted by more than half the number of pirates, the pirate who made the proposal gets killed, and the next pirate in line then makes his proposal for voting.
4. If the proposal is accepted by a majority, they then split the gold coins according to the proposal and enjoy them.
5. The process continues until a proposal is accepted or there is only one pirate left.
6. Assume that
(a) every pirate above all wants to live;
(b) if a pirate will be alive, he wants to get as much gold as possible;
(c) if a pirate will receive a same amount of gold, he prefers to see any other pirate killed, just for fun;
(d) each pirate knows his exact position in line;
(e) all of the pirates are excellent puzzle solvers.

What proposal should the first pirate make in order to maximize his share while live to enjoy it?

The solutions will be posted in a few days here.

Financial Engineering (I)

Financial Engineering (I)

University Mathematics

Before attempting to read what we have here, students should revise their basic probability and linear algebra first.

Financial Engineering (I) #1 – Overview
Financial Engineering (I) #2 – Introduction to No Arbitrage
Financial Engineering (I) #3 – Interest rates and fixed income instruments
Financial Engineering (I) #4 – Floating Rate Bonds and Term Structure of Interest Rates
Financial Engineering (I) #5 – Forward Contracts
Financial Engineering (I) #6 – Swaps
Financial Engineering (I) #7 – Futures
Financial Engineering (I) #8 – Options
Financial Engineering (I) #9 – Options Pricing
Financial Engineering (I) #10 – The 1-Period Binomial Model
Financial Engineering (I) #11 – Option Pricing in the 1-Period Binomial Model
Financial Engineering (I) #12 – The Multi-Period Binomial Model
Financial Engineering (I) #13 – Pricing American Options
Financial Engineering (I) #14 – Replicating Strategies
Financial Engineering (I) #15 – Dividends, Pricing in the Binomial Model
Financial Engineering (I) #16 – Black-Scholes Model
Financial Engineering (I) #17 – Introduction to Term Structure Lattice Models
Financial Engineering (I) #18 – Cash Account and Pricing Zero-Coupon Bonds
Financial Engineering (I) #19 – Fixed Income Derivatives (1)
Financial Engineering (I) #20 – Fixed Income Derivatives (2)
Financial Engineering (I) #21 – The Forward Equation
Financial Engineering (I) #22 – Model Calibration
Financial Engineering (I) #23 – Pricing in a Black-Derman Toy Model
Financial Engineering (I) #24 – Modelling and Pricing Default-able bonds
Financial Engineering (I) #25 – Credit Default Swaps and Pricing Credit Default Swaps
Financial Engineering (I) #26 – Mortgage Mathematics and Mortgage-Backed Securities
Financial Engineering (I) #27 – Prepayment Risks and Pass-Throughs
Financial Engineering (I) #28 – Principal-Only and Interest Only Mortgaged-Backed Securities
Financial Engineering (I) #29 – Collateralised Mortgage Obligations
Financial Engineering (I) #30 – Pricing Mortgage-Backed Securities

Geometric Brownian Motion

JC Mathematics, University Mathematics

This is really important for anyone interested in Finance Modelling. As what the movie Wolf on Wall Street says:

Fugazi. Source: AZ Quotes
Fugazi. Source: AZ Quotes

They are referring to a geometric brownian motion.

Firstly, we will begin with the definitions.

We say that a random process, X_t, is a geometric Brownian motion (GBM) if for all t \ge 0
X_t = e^{(\mu - \frac{\sigma^2}{2})t} + \sigma W_t
where W_t is a Standard Brownian Motion
Here \mu is the drift and \sigma is the volatility. We write X_t \sim GBM (\mu, \sigma)

Also note that
= X_0 e^{(\mu - \frac{\sigma^2}{2})(t+s) + \sigma W_{t+s}}
= X_0 e^{(\mu - \frac{\sigma^2}{2})(t+s) + \sigma W_{t} + (\mu - \frac{\sigma^2}{2})s + \sigma (W_{t+s} - W_t)}; This is a common technique for solving expectations.
= X_t e^{(\mu - \frac{\sigma^2}{2})(s) + \sigma (W_{t+s} - W_t)}. This is very useful for simulating security prices.

Consider \mathbb{E}_t [X_{t+s}]

\mathbb{E}_t [X_{t+s}]
= \mathbb{E}_t [X_{t}e^{(\mu - \frac{\sigma^2}{2})s + \sigma(W_{t+s} - W_t)}]; Notice this expansion is similar to before.
= X_t e^{(\mu - \frac{\sigma^2}{2})s} \mathbb{E}^t [e^{\sigma (W_{t+s} - W_t)}]
= X_t e^{(\mu - \frac{\sigma^2}{2})s} e^{\frac{\sigma^2}{2}s}
= e^{\mu s} X_t
This result tells us that the expected growth rate of X_t is \mu.

From the definitions of Brownian Motion introduced earlier, we extend them to Geometric Brownian motion.
1. Fix t_1, t_2, \ldots , t_n. Then \frac{X_{t_2}}{X_{t_1}}, \frac{X_{t_3}}{X_{t_2}}, \ldots \frac{X_{t_n}}{X_{t_{n-1}}} are mutually independent.
2. Paths of X_t are continuous as function of t, meaning they do not jump.
3. For s > 0, \mathrm{log}(\frac{X_{t+s}}{X_t}) \sim \mathrm{N}((\mu - \frac{\sigma^2}{2})s, \sigma^2 s)

So now lets try to do some modelling of stock prices as a geometric brownian motion.

Suppose X_t \sim GBM(\mu, \sigma). Clearly
1. X_t > 0 \Rightarrow X_{t+s} > 0 for any s > 0
This tells us that the limited liability of stock price is not violated.
2. The distribution of \frac{X_{t+s}}{X_t} only depends on s and not on $latex X_t.
We will look at the Black-Scholes option formula next time and will come back to review the geometric brownian motion for the underlying model.

Introduction to Brownian Motion

JC Mathematics, University Mathematics

Lets look at brownian motion now. And yes, its the same as what our high school teachers taught about the particles moving in random motion. Here, we attempt to give it a proper structure and definition to work with.

A Brownian Motion is a random process \{ X_t : t \ge  0 \} with parameters (\mu, \sigma) if
For 0 \textless t_1 \textless t_2 \textless \ldots \textless t_{n-1} \textless t_n, (X_{t_2} - X_{t_1}), (X_{t_3} - X_{t_2}), \ldots, (X_{t_n} - X_{t_{n-1}}) are mutually independent. This is often called the independent increments property.
For s > 0, X_{t+s} - X_t \sim \mathrm{N} ( \mu s, \sigma^2 s)
X_t is a continuous function of t.
We say that X_t is a \mathrm{B} (\mu, \sigma) Brownian motion with drift \mu and volatility \sigma.

For the special case of \mu = 0 and \sigma = 1, we have a standard Brownian motion. We can denote it with W_t and assume that W_0 = 0
If X_t \sim \mathrm{B}(\mu, \sigma) and X_0 = x then X_t = x + \mu t + \sigma W_t where W_t is a standard brownian motion. Thus, X_t \sim \mathrm{N}(x+\mu t, \sigma^2 t)

Random Paths of Brownian Motion. Source: Columbia University
Random Paths of Brownian Motion. Source: Columbia University

The next concept is important in finance, that is, Information Filtrations.
For any random process, we will use \mathcal{F}_t to denote the information available at time t.
– the set \{\mathcal{F}_t\}_{t \ge 0} is then the information filtration.
\mathbb{E}[.|\mathcal{F}_t] denotes an expectation conditional on time t information available.

Note: The independent increment property of Brownian Motion implies that any function of W_{t+s} - W_t is independent of \mathcal{F}_t and that (W_{t+s}-W_t) \sim \mathrm{N}(0,s).

So let us do a bit of math to obtain \mathbb{E}_0[W_{t+s}W_s] for instance.

Using condition expectation identity, we have
\mathbb{E}_0 [W_{t+s}W_s]
= \mathbb{E}_0 [(W_{t+s} - W_s + W_s)Ws]
= \mathbb{E}_0 [(W_{t+s}-W_s)W_s] + \mathbb{E}_0 [{W_s}^2]
= \mathbb{E}_0 [\mathbb{E}_s[(W_{t+s} - W_s)W_s]] + s
= \mathbb{E}_0 [W_s \mathbb{E}_s[(W_{t+s} - W_s)]] + s
= \mathbb{E}_0 [W_s 0] + s
= 0 + s
= s