Exercising American option before expiration

Why is it never optimal to exercise an American option on a stock that pays no dividends before expiration?

Reason. Let ct be the price of the American option, K be the strike, St be the stock price, and r be a risk-free rate. Now suppose that the call option is in the money, so you decide to exercise it and lock in the profit St – K at time t. The claim is that you can do better than that by not exercising. Indeed, sell short a share of the stock and put the proceeding in the money market account. Then at time T, you will have made

cT – ST + St er(T-t) = er(T-t) (St – K) + (K – ST)+ + (er(T-t) – 1) K

which is at least as good as the exercising strategy. If the stock trades below the strike, you will actually make more money even if the risk-free rate is zero.

May 12, 2015 – 04:04 Categories: Mathematical Finance | Post a comment

Tagged |

Integer solutions

Find all positive integer solutions of the system

\displaystyle \left\{ \begin{aligned} a^2 + b^2 &= c^2, \\ a + b + c &= 40. \end{aligned} \right.

Solution. From the first equation, we deduce that a = c cos θ and b = c sin θ for some θ. Therefore, the second equation implies that

\displaystyle c = \frac {40}{1 + \cos\theta + \sin\theta} = \frac {40}{1 + \sqrt 2\, \sin(\theta + \pi/4)} \geqslant \frac {40}{1 + \sqrt 2}

and hence 17 ≤ c.

The first equation also gives (a + b)2 = c2 + 2ab, so that a + b > c. In view of the second equation, this implies 2c < 40 and hence c ≤ 19. Summarizing, we have the estimates

17 ≤ c ≤ 19.

One verifies that c = 17 is the only option. Hence, our system has exactly two positive integer solutions,

(8, 15, 17) and (15, 8, 17).

May 3, 2015 – 00:29 Categories: Brain Teasers | Post a comment

Tagged |

Recursive relation for the binomial coefficients

Without doing any arithmetics, prove the binomial recursion:

\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Solution. Fix an element, x, among our n elements. There are \binom{n-1}{k-1} k-element subsets that contain x and \binom{n-1}{k} k-element subsets that do not. Hence the formula.

April 16, 2015 – 08:23 Categories: Uncategorized | Post a comment

Tagged |

No two girls sit next to each other

There are n boys and m girls in the room. In how many ways can they be seated so that no two girls sit next to each other?

Solution. Each of the first m – 1 girls must have a boy to the right. So, we need to place the m – 1 gb‘s and an g somewhere among n – (m – 1) + m = n + 1 places, and the number of such combinations is equal to \binom{n+1}{m}. Therefore, as far as permutations are concerned, the answer must be

\displaystyle \binom{n+1}{m} m!\, n!

April 11, 2015 – 09:29 Categories: Brain Teasers | Post a comment

Tagged |

Risky ball in a backet

There are m blue, n green, and 1 red balls in a basket. You can pick up balls without replacements, and you will get $1 for each green ball while picking up the red ball will make you lose all money you have made. Picking up a blue ball neither makes you money nor does it take money from you. What is the optimal strategy?

Solution. We can assume that there are no blue balls in the basket as they do not change anything. It is clear that you should draw a ball at least once. Assuming that you have already picked up x green balls, the next draw would earn you (n – x)/(n + 1 – x) – x/(n + 1 – x) dollars, on average. This quantity is nonnegative iff x \le \lfloor n/2 \rfloor. Hence, the optimal strategy is to pick up balls until either x \le \lfloor n/2 \rfloor green balls are picked up or the red ball has been drawn.

February 21, 2015 – 07:34 Categories: Brain Teasers, Probability | Post a comment

Passengers on a bus

There are n passengers in a bus that will make k > n stops. Every paggengers gets off at some station. What is the probability that no more than one passenger will get off at each station?

Solution. There are kn different ways in which passengers can choose their stops, and there are (k)n ways in which no more that one passenger will get off an each station. So, the answer is (k)n / kn.

February 15, 2015 – 09:30 Categories: Brain Teasers, Probability | Post a comment

Breaking eggs optimally

You have two identical eggs and an n-storey building. Each of the eggs will be broken when dropped from the n-th floor. You need to find the smallest floor that would break the eggs. What is the optimal strategy?

Solution. Any possible strategy is characterized by a sequence (hk) of positive integers such that you will be done after k + hk – 1 drops for some k. So, in the worst case scenario, you will have to make

maxk (k + hk – 1)

drops to figure out the right floor. We need to minimize this worst case scenario, which will happen when k + hk – 1 = const. In other words, we must have

hk = hk-1 – 1.

Since the sum of hk‘s must be equal to n, we deduce that h1(1 + h1)/2 = n. Consequently,

\displaystyle h_1 = \left\lceil \frac{\sqrt{1+8n} - 1}2 \right\rceil.

So, the strategy is to start with floor number h1 and continue until we find a number k such that floor number min(Hk, n) breaks the egg, where Hk := h1 + … + hk and hk = hk-1 – 1. We then take the second egg and drop it starting from floor Hk-1 + 1 and going up at most hk – 1 floors util the second egg is broken.

Note: This solution is not rigorous but one can easily make it so.

October 28, 2014 – 05:33 Categories: Brain Teasers | Post a comment

Tagged |

How many uniform random variables to sum up?

Let (Xn) be an i.i.d. sequence of random variables uniformly distributed on [0,1]. How many of these random variables does one need to sum up, on average, in order to get the sum exceeding 1?

Solution 1. Let N denote the number of the random variables we need to sum up. Since N is N-valued, we must have

\displaystyle \mathsf EN = \sum_{n=0}^\infty \mathsf P(N>n).

Let Sn := X1 + … + Xn. Then P(N > n) = P(Sn ≤ 1) = 1/n!, the volume of the n-simplex. We conclude that EN = e.

Solution 2. Given x ∈ (0,1), let

\displaystyle N_x := \min\left\{ n\in\mathbf N \left|\, S_n > x \right. \right\}.

Then denoting m(x) := E[Nx],

\displaystyle \begin{aligned} m(x) = \int_0^1 \mathsf E[N_x \mid X_1=u]\,du &= 1 - x + \int_0^x (1 + m(x-u))\,du \\ &= 1 + \int_0^x m(u)\, du. \end{aligned}

Since m(0) = 1, we conclude that m(x) = ex.

August 9, 2014 – 09:32 Categories: Brain Teasers, Probability | Post a comment

Laplace Transform of the First Passage Time in Birth-Death Process

How do you compute distribution of the first passage time from state i to state i-1 of a birth-death process? Laplace transform could be useful.

Let σi,i-1 be the first passage time in question, and let birth and death rates in state i be λi and μi, respectively.

Then

\begin{aligned} \hat f_i(s) &= \frac {\mu_i}{\lambda_i+\mu_i} \mathsf P[e^{-s\sigma_{i,i-1}} \mid i\to i-1] + \frac {\lambda_i}{\lambda_i+\mu_i} \mathsf P[e^{-s\sigma_{i,i-1}} \mid i\to i+1] \\ &= \frac {\mu_i}{\lambda_i+\mu_i}\, \frac {\lambda_i+\mu_i}{\lambda_i+\mu_i+s} + \frac {\lambda_i}{\lambda_i+\mu_i}\, \mathsf E[e^{-s(\sigma_{i,i+1}+\sigma_{i+1,i-1})} \mid i\to i+1] \\ &= \frac {\mu_i}{\lambda_i+\mu_i}\, \frac {\lambda_i+\mu_i}{\lambda_i+\mu_i+s} + \frac {\lambda_i}{\lambda_i+\mu_i}\, \frac {\lambda_i+\mu_i}{\lambda_i+\mu_i+s}\, \mathsf E[e^{-s\sigma_{i+1,i-1}}]. \end{aligned}

But

\mathsf E[e^{-s\sigma_{i+1,i-1}}] = \mathsf E[e^{-s(\sigma_{i+1,i} + \sigma_{i,i-1})}] = \hat f_i(s) \hat f_{i+1}(s),

which, after pluggin in in the previous formula, gives

\displaystyle \hat f_i(s) = \frac {\mu_i}{\lambda_i+\mu_i+s-\lambda_i \hat f_{i+1}(s)} = -\frac 1{\lambda_{i-1}} \Phi_{k=i}^\infty \frac {\lambda_{k-1}\mu_k}{\lambda_k+\mu_k+s}

where the term on the HRS denotes the corresponding generalized continuous fraction.

So, the density function of σi,i-1 can be found by applying the inverse Laplace transform.

June 29, 2014 – 05:29 Categories: Probability | Post a comment

First Nonzero Digit Is One

Let a and b be independent uniformly distributed on (0, 1] random variables. What is the probability that the fist nonzero digit in the decimal expansion of a / b is 1. (For example, the first non-zero digit in .01234 is 1)

Solution. We need to find the probability that

10^{-n} b \leqslant a \leqslant 2\cdot10^{-n} b

for some n ∈ Z. So the answer is

\displaystyle \sum_{n=-1}^\infty \frac 12\cdot 10^n + \sum_{n=0}^\infty \frac 14\cdot 10^{-n} = \frac 13.

April 5, 2014 – 02:46 Categories: Mathematics, Probability | Post a comment