Saturday, November 23, 2013

How do you model the dynamics of asset prices? A self-reflection (2 of 3)

Last time we have set a stage for the discussion on modeling the dynamics of asset prices. Gaussian process is the "canonical" way to go, and we've seen the characteristics/limitations of it. To recap:

       Candidate: Brownian motion
  • Markovian
  • "Tractable"(-ish, depending on how you transform it)
  • Excess kurtosis = 0
  • Market completeness (if number of hedging instruments >= number of sources of randomness)
This view is usually summed up and referred to as "random walk" (or diffusion, if you are from the natural science branch of the academia). But does the financial market really walk? Or does it prefer doing something else?

Poisson
We've already met Gauss last time. Now we'll introduce a contemporary of him, Siméon Denis Poisson. While Brownian motion is a diffusion stochastic process (a random walk down the street), the Poisson process is a counting process that is associated with jumps. When we add a Poisson counting process to the diffusion equation, the stochastic differential equation becomes a jump-diffusion equation that allows for jumps, or "gapping up/down". Why is this desirable or required? Just talk to any trader, and they'll tell you that price jump is a reality, especially for markets with substantial close hours (i.e. the majority of the markets other than FX, S&P futures...). So instead of a random walk down the street, perhaps after all it is more like parkour down the street?

You Jump, I Jump
What are the advantages of modeling asset prices with a jump-diffusion process over a diffusion only process?

       Candidate: Jump-diffusion Process
  • Markovian
  • Not tractable (unless under restrictive assumptions)
  • Excess kurtosis > 0
  • Market incomplete (unless under restrictive assumptions) 
So, only Markovian-ness stays. Derivative prices under jump-diffusion models are generally not tractable unless assumptions are made. For example, Merton's jump-diffusion model assumes that the jump size is lognormally distributed. The possibility of jumps gives the asset return distribution a desired fat tail feature, hence excess kurtosis. Finally, market completeness is in general lost (there are two sources of randomness - diffusion and jump, but only one hedging instrument - the asset itself), and one has to estimate a market price of risk of the jumps. Incidentally, in Merton's model he assumes that such a market price of risk is zero because of diversifiability.

The implementation of jump-diffusion model can be challenging. The numerical calibration is of course more computationally intensive, but the more subtle and fundamental issue is this: how do we identify jumps? When there is a "sudden" gap in the time series, how can one be sure that it is NOT just an extreme value, yet still being drawn from the good old Gaussian distribution?

Friday, November 22, 2013

Monty Hall, extended

The original Monty Hall problem is so famous that pretty much every soul knows the solution by heart (in case you don't: change to the other still closed door and double your winning probability!). Despite (or because of) the fame of this problem, some would learn the answer without really knowing how to solve it. Let's go through the problem in its original setting:

Classic Three Door Monty Hall
There are three doors A, B and C, and only one leads to a prize. After you picked door A, the host (who knows where the prize is) opens door C, which turns out to be not the prize door. What is the winning probabilities of you sticking to door A versus switching to door B?

And of course, the toolkit to invoke is Bayesian statistics:
$$ P(A|C_o) = \frac { P(C_o|A)P(A)}{P(C_o)} $$
where $P(X)$ is the unconditional probability of the prize being behind door X, and $P(Y_o)$ is the probability of door Y being opened by the host. In this case, the entities on the RHS are straightforward, except perhaps for $ P(C_o)$:
$$  P(C_o|A) = 1/2 $$
$$  P(A) = 1/3 $$
$$  P(C_o) = P(C_o|A)P(A) + P(C_o|B)P(B) + P(C_o|C)P(C) $$
$$= \frac 1 2 \times  \frac 1 3 + 1 \times \frac 1 3 + 0 = \frac 1 2$$
So $P(A|C_o) = 1/3$. One can in a similar fashion find that $P(B|C_o) = 2/3$. The reason $ P(C_o|B) = 1$ is of course that if the prize is really behind door B, the host has no choice but to open door C.

Extended Five Door Monty Hall
So far so good. Now we are invited to a "Monty Hall Deluxe" game with a bigger prize, but more doors and more rounds. In round one, you pick a door. The host would open one door, after which you may choose to switch to another. Then once you have decided and acted accordingly, we enter round two where the host would open one more door (so number of closed door drops to 3 at this point). Then you decide on whether to switch for a second time, and if so to which door. What should the optimal strategy be?

Suppose you first pick door A and the host opens door E. The first round of this game is really similar to the Classic version above. Namely,
$$ P(A|E_o) = \frac { P(E_o|A)P(A)}{P(E_o)} $$
with
$$  P(E_o|A) = 1/4$$
$$  P(A) = 1/5$$
$$  P(E_o) =\sum  P(E_o|X)P(X) $$
$$= \frac 1 4 \times  \frac 1 5 + \frac 1 3 \times \frac 1 5 + \frac 1 3 \times  \frac 1 5+ \frac 1 3 \times  \frac 1 5+0 = \frac 1 4$$
So $P(A|E_o) = 3/15$. Similarly, one can show that $P(B|E_o) = P(C|E_o) =P(D|E_o) =4/15$. So once again, it is better for you to switch (and due to symmetry, it doesn't matter to which).

Suppose you switch to door B. Now we are in round two. The host then open door D, which, surprise-surprise, turns out to have no prize behind it too. Now what do you do? What are the probabilities of staying versus switching?

One thing to be careful about is this: since at this point round one is already over, the conditional probabilities we calculated (i.e. $P(A|E_o)$, $P(B|E_o)$, ...) should now be considered unconditional:
$$ P(A)  = 3/15$$
$$ P(B)  = 4/15$$
$$ P(C)  = 4/15$$
We also have the followings:
$$ P(D_o|A) = 1/2$$
$$ P(D_o|B) = 1/3$$
$$ P(D_o|C) = 1/2$$
$$  P(D_o) =\sum  P(D_o|X)P(X) $$
$$= \frac 1 2 \times  \frac 3 {15} + \frac 1 3 \times \frac 4 {15} + \frac 1 2 \times  \frac 4 {15} +0 = \frac {29} {90}$$
Hence $P(A|D_o) = 9/29$, $P(B|D_o) = 8/29$ and $P(C|D_o) = 12/29$. So staying with door B is even worse than switching back to door A, and switching to the untouched door C is the best. Just keep switching!

Sunday, November 17, 2013

How do you model the dynamics of asset prices? A self-reflection (1 of 3)

Having been working on/studying mathematical finance for a while now, I feel like it would be useful to step back and look at one of the most important topics in this area: how does one model asset price dynamics?

Gauß
The canonical account would inevitably begin with Gauss. The Gaussian distribution (or the normal distribution, depending on your academic upbringing) is undeniable the most well-investigated probability distribution in human history. We don't need to go into all the details and properties of it, but it's good to be reminded of a number of facts regarding how the normal distribution is related to some other entities:
  • It is closely related to the phenomenon of diffusion;
  • The Central Limit Theorem says that (under some technical conditions) the sum of many i.i.d. random variables would converge to a normal distribution;
  • Brownian motion is mathematically described by Wiener process, which follows a Gaussian distribution.
I don't want to delve into historical investigation in whether Louis Bachelier is the first person to model financial time series with (arithmetic) Brownian motion, but it's fair to say that he is at least among the first ones who formalize it and apply it in derivative pricing. Later down the road, some would argue that arithmetic Brownian motion is prone to producing negative values and would propose other alternative processes (e.g. geometric Brownian motion for stock prices, O-U process for rates), but those would all be in the same spirit of arithmetic Brownian motion, save some transformations (e.g. taking the natural log as in geometric Brownian motion)

Our  Checklist
Before proceeding further, let's compile a checklist that we will re-visit multiple times in this series:

       Candidate: Brownian motion
  • Markovian
  • "Tractable"(-ish, depending on how you transform it)
  • Excess kurtosis = 0
  • Market completeness (if number of hedging instruments >= number of sources of randomness)
Since this is the first time the checklist is presented, we should go through each point:
  • A Markov process has no memory. It doesn't matter if the market went up 20%, up 3%, down 3%, or down 20% yesterday. Today's probability of movement is not affected in any way.
  • "Tractable" refers to a closed-form expression for the asset price process itself, or the price of derivatives with the asset as underlying.
  • Excess kurtosis is a measure of "tail effect"
  • Market completeness means a contingent claim can be fully hedged
The paradigm of thinking of asset price as following a Brownian motion is commonly known as the random walk hypothesis. It is well-known and widely used: it's the canonical/default view in the majority of quant finance textbooks; it is mentioned and discussed in "pop-finance" books such as A Random Walk Down Wall Street. But how realistic is it and what are the caveats?

Thursday, November 7, 2013

The Balanced 1-0 Matrix Problem

This post is about the Balanced 1-0 Matrix problem. Namely, for an n-by-n matrix (can be relaxed to n-by-m, but we will stick to square matrix here), how many legitimate assignments are there such that each row as well as column contains exactly n/2 zeros and n/2 ones?

You will find different approaches to solve this problem in the link, and one thing to note is how quickly the sequence grows: the numbers of possible assignments are 1, 2, 90, 297200... for 1-by-1, 2-by-2, 3-by-3, 4-by-4 matrices. The brute force approach is not very interesting, so we will only discuss the dynamic programming approach. The Matlab script can be found at the end.

The idea is first to have an easy way to store the arrangement. That is what stateArr does. As a 2-by-n array, it stores how many zeros and ones are still available to be allocated for each of the n columns. Then we have the systematic sweeping through the rows, meaning that we do a tree search starting from the first row downward. We iterate all the possible combinations (of course, they have to have n/2 zeros and n/2 ones) for a row, and compare these possible combinations against the stateArr to see if there are enough zeros and ones to be assigned. This is what the for loop within the DP_recursion is for.

Finally, the algorithm described above would have to visit every and all solutions unless we use a memoization trick. All partial solutions, as well as the corresponding stateArr, are stored in stateArrTable, and for every step the script would first check whether partial solution already exists. If so, use the stateArr as a signature/key to retrieve it; if not, and only if not, will it jump into recursion.

Unfortunately, even with dynamic programming, the computation is too intensive for Matlab for any n > 4.



function output = ZeroOneMat_DP(numCol)
% ((1, 2) (2, 1) (1, 2) (2, 1)) would be stored as
% [1, 2, 1, 2; 2, 1, 2, 1]
% First row is # zeros, second row is # ones
stateArr = numCol/2*ones(2,numCol);
stateArrTable = [];
partialAnsArr = [];
[output stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr, stateArrTable, partialAnsArr, 0);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [output stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr, stateArrTable, partialAnsArr, numSol)
% Iterate all combinations
locationMat = nchoosek(1:numCol,numCol/2);
tempOutput = numSol;
for i = 1:size(locationMat,1)
    thisRow = zeros(1,numCol);
    thisRow(locationMat(i,:)) = 1;
    % Change stateArr
    stateArr_temp = stateArr;
    for j = 1:numCol
        if thisRow(j) == 0
            stateArr_temp(1,j) = stateArr_temp(1,j) - 1;
        elseif thisRow(j) == 1
            stateArr_temp(2,j) = stateArr_temp(2,j) - 1;
        end
    end
    % Check if there is negative values
    if min(min(stateArr_temp)) < 0
       
    elseif min(min(stateArr_temp)) >= 0 & max(max(stateArr_temp)) > 0
        % See if already in table
        [foundBool theAnswer] = findInTable(stateArr_temp, stateArrTable, partialAnsArr);
        if foundBool == 0 % not
            [tempOutput2 stateArrTable partialAnsArr] = DP_recursion(numCol, stateArr_temp, stateArrTable, partialAnsArr, tempOutput);
            % Save to partial answers
            stateArrTable = [stateArrTable; stateArr_temp];
            partialAnsArr = [partialAnsArr; tempOutput2 - tempOutput];
            tempOutput = tempOutput2;
        elseif foundBool == 1
            % find in table
            tempOutput = tempOutput + theAnswer;
        end
    elseif  max(max(abs(stateArr_temp))) == 0 % successfully placed all numbers through the last row
        tempOutput = tempOutput + 1;
    end
end
output = tempOutput;
end

function [foundBool theAnswer] = findInTable(stateArr, stateArrTable, partialAnsArr)
foundBool = 0;
theAnswer = -1;
for i = 1:size(stateArrTable,1)/2
    if max(max(abs(stateArrTable(2*i-1:2*i,:)-stateArr))) == 0
        theAnswer = partialAnsArr(i);
        foundBool = 1;
        break
    end
end
end

Tuesday, November 5, 2013

Those damn cards...

We are quickly approaching the end of the combo interview question bank series. So far we have discussed a variety of coin and dice problems. Yet another popular theme would be card games, specifically with poker decks. As compared to coins and dice, a poker deck contains two colours and four suits, giving rise to some interesting and complicated games and problems.

CF01
A deck consists of 3 red and 3 black cards. They are turned over one by one, and at any point you can make the call of the following card being red. If it turns out to be the case, you win. What is the optimal strategy?

CF01- Answer:
This is closely related to option pricing with binomial tree. Being able to call 'red' as you wish is equivalent to early exercise. It's trivial to show that without early exercise, the probability tree reads:
0.5000
0.3125  0.6875
0.1250 0.5000 0.8750
0.0000 0.2500 0.7500 1.0000
0.0000 0.5000 1.0000
1.0000 0.0000
corresponding to #Black card shown : #Red card shown
0:0
0:1  1:0
0:2  1:1  2:0
0:3  1:2  2:1  3:0
1:3  2:2  3:1
2:3  3:2
Remember, this is when there is no early exercise, meaning that you can only passively look at cards being flipped open and wait to see if the last card is red. To take early exercise into account, some nodes on the probability tree will be over-ridden, depending on the numbers of remaining cards on the node. Take the (1:2) node as an example. When 1 Black card and 2 Red cards are already shown, there are 2 Black cards and 1 Red card remaining in the deck. Hence the winning probability of early calling at this point is 1/3 = 0.333..., which is greater than 0.25. Hence the optimal strategy would require early calling at this node. Similar argument can be made regarding other nodes on the tree.

CF02
You draw a card from a deck and player B draws another. You win only if your draw has a higher number. What is the probability that you will win?

CF02- Answer:
P(numbers equal) = 3/51 = 1/17. Due to symmetry, the two parties have the same winning probability. Hence P(you win) = (1 - 1/17) / 2 = 8/17

See here for more interview questions/brainteasers