### Question of the Day #14

All possible straight lines joining the vertices of a cube with mid-points of its edges are drawn. At how many points inside the cube do two or more of these lines meet?

### AHOY! The Pirate Story Solution

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

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?
Note: EVERY PAIR.

### AHOY! The Pirate Story Problem

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.

### Integrating Trigonometric Functions

Trigonometric functions can be difficult to handle. So here is some intuition and idea on what to do when dealing with certain trigonometric functions.

### Financial Engineering (I)

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

### Arithmetic Problem #7

I came across this interesting algebra/ arithmetic problem the other day.

$(1 \times 2 \times 3) + 2 = 8 = 2^3$
$(2 \times 3 \times 4) + 3 = 27 = 3^3$
$(3 \times 4 \times 5) + 4 = 64 = 4^3$

Do you think this will always work?

Hint: We can use algebra to prove this cool sequence easily.

### Geometric Brownian Motion

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

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_{t+s}$
$= 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 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)$ 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$ ### Sampling & Survey # 9 – Regression Estimation Today, we shall look at regression estimation. We will begin by looking at the usual & simple straight line regression model: $y = B_0 + B_1 x$. Let $\hat{B_1}$ and $\hat{B_0}$ by the ordinary least squares (OLS) regression coefficients of the slope and intercept. $\hat{B_1} = \frac{\sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^n (x_i - \bar{x})^2}$ = $\frac{s_{xy}}{s_x^2}$ = $\frac{r s_y}{s_x}$ $\hat{B_0} = \bar{y} - \hat{B_1} \bar{x}$ Precision is increase, that is$latex SE(\hat{\bar{y}}_{reg}) < SE(\bar{y})\$ [caption id="attachment_2634" align="alignnone" width="300"] Different estimators for population total[/caption]

We conclude here by observing that ratio or regression estimators give greater precision that $\hat{t_y}$ when $\sum_{i=1}^n e_i^2$ for the method is smaller than $\sum_{i=1}^n (y_i - \bar{y})^2$

Sampling & Survey #1 – Introduction
Sampling & Survey #2 – Simple Probability Samples
Sampling & Survey #3 – Simple Random Sampling
Sampling & Survey #4 – Qualities of estimator in SRS
Sampling & Survey #5 – Sampling weight, Confidence Interval and sample size in SRS
Sampling & Survey #6 – Systematic Sampling
Sampling & Survey #7 – Stratified Sampling
Sampling & Survey # 8 – Ratio Estimation
Sampling & Survey # 9 – Regression Estimation
Sampling & Survey #10 – Cluster Sampling
Sampling & Survey #11 – Two – Stage Cluster Sampling
Sampling & Survey #12 – Sampling with unequal probabilities (Part 1)
Sampling & Survey #13 – Sampling with unequal probabilities (Part 2)
Sampling & Survey #14 – Nonresponse