As the title suggests, this was supposed to be a three part series.
But I feel like I have left out so much that I wanted to discuss, so
although the first 3 parts have already provided an overview on what I
would call the "classical" quant modeling approach (loosely speaking,
one that focuses on describing the asset price time series with a random
process), I would take this opportunity to talk about what lies beyond
such approach.
We are interested particularly in capturing the tails of the distribution. What about putting the tail on the center stage? That is the spirit of extreme value theory.
It has had wide application in natural disaster forecast. The basic
idea is to posit a probability distribution that specifically fits the
tail of the distribution. Contrast this with, say, the stochastic
volatility approach in which we tried to fatten the tail, while still
keeping our focus on the 'body' of the return distribution. Now we are
directly and un-apologetically modeling the tail itself. The advantage
is obvious: we have more freedom in fitting the tails closely by
dedicating the calibration to it. The short coming is more subtle. In
order to perform extreme value analysis, we have to specify the
threshold at where the tail starts, so that we can attach a distribution
to it. If you define daily return of -20% as the threshold, then you
can use some distribution to catch the sub-sample of daily return less than -20%. But how do you choose the threshold? Choose it too deep into
the body and you miss the point of using extreme value models. After
all, we are trying to focus on the tail by not worrying about modeling
the boring part of the distribution. On the other hand, choose it too
far off into the tail and you suffer by not having enough historical
data points for an accurate calibration. The other issue is that extreme
value analysis would not solve the "you don't know what you don't know"
problem. You pick a threshold, you do the fitting, and chances are
sooner or later a much worse draw down would take you by surprise,
proving to you that the tail is even fatter that you have assumed.
Now you might say, "Hey, isn't that a necessary evil of any perceivable
model in finance? That one has to make assumptions and wait to be
surprised?" And I tend to agree to the sad fact. Perhaps except for if
we follow a completely different paradigm. Recently some researchers
having been looking at crash forecasting using a wide range of
unconventional tools. They range from fractal analysis that studies the
(change in) scaling of time series; agent-based models that take a
bottom-up approach trying to produce asset price dynamics by considering
(grossly simplified) behaviors of traders; and critical point/phase
change models that are inspired by Ising model in solid state physics.
The common theme is the acknowledgement of market non-linearity and the
lack of a single, forever stable market state. Unfortunately there is no
straight forward way to connect these models to option prices, but with
the advancements of numerical methods we may some day see wider
applications of them.
Saturday, March 1, 2014
Friday, February 28, 2014
Looping the Strings Problem
This one is a classic that I believe is found in one of the popular interview books. You start with N pieces of strings that are mixed into a single pile. You start randomly choosing two free ends at a time and joining them together. After N rounds, you will be done as there will be no more free ends left. If the number of closed loops is k, what is F = E[k]?
If you go down the combinatorial path, you will soon see how hopeless it is to try figuring out the many different intermediate states. So perhaps combinatorial is not the right tool here. In fact, this problem can be readily solved with a closed-form solution using induction and recurrence. Before arriving at that, let's get some sense and inspiration by stating with a small N.
N = 1 is trivial and we see that k = 1 surely, so F = 1. Consider N = 2. During the first round of joining, when one free end is picked, it can be joined to any of the remaining 3 free ends. In one out of these three cases, we end up with k = 2 (namely, if the free end is joined to another end of itself); while in the remaining two cases, we end up with k = 1 (namely, if the free end is joined to any end of the other string). So $ F_2 = \frac 1 3 (1+F_1) + \frac 2 3 (F_1)=\frac 4 3 $. More generally, it's easy to show that $ F_N = \frac 1 {2N-1} (1+F_{N-1}) + \frac {2N-2} {2N-1} (F_{N-1})$
This recurring relation can be rearranged to give the difference equation $ F_N = F_{N-1} + \frac 1 {2N-1} $. With the initial condition of $ F_1 = 1$, we can alternatively express it as a finite sum. Note how slow it grows with N (~ log(N)).
If you go down the combinatorial path, you will soon see how hopeless it is to try figuring out the many different intermediate states. So perhaps combinatorial is not the right tool here. In fact, this problem can be readily solved with a closed-form solution using induction and recurrence. Before arriving at that, let's get some sense and inspiration by stating with a small N.
N = 1 is trivial and we see that k = 1 surely, so F = 1. Consider N = 2. During the first round of joining, when one free end is picked, it can be joined to any of the remaining 3 free ends. In one out of these three cases, we end up with k = 2 (namely, if the free end is joined to another end of itself); while in the remaining two cases, we end up with k = 1 (namely, if the free end is joined to any end of the other string). So $ F_2 = \frac 1 3 (1+F_1) + \frac 2 3 (F_1)=\frac 4 3 $. More generally, it's easy to show that $ F_N = \frac 1 {2N-1} (1+F_{N-1}) + \frac {2N-2} {2N-1} (F_{N-1})$
This recurring relation can be rearranged to give the difference equation $ F_N = F_{N-1} + \frac 1 {2N-1} $. With the initial condition of $ F_1 = 1$, we can alternatively express it as a finite sum. Note how slow it grows with N (~ log(N)).
Thursday, January 30, 2014
How do you model the dynamics of asset prices? A self-reflection (3 of 3)
Last time we added jumps to the recipe to enrich the original random walk dynamics. Jump diffusion model is able to fit to market implied vol much better than the diffusion only counterpart. Before moving on, just two reminders:
So is jump diffusion the ultimate holy grail? And is pure diffusion model done with? For the first question, we will see later in the series that there are many other approaches that supersede jump diffusion, but for now let's take a step back and address the second question.
It turns out that the use of mixtures is able to tackle at least some of the shortcomings of the original random walk model. A mixture, not surprisingly, is formed by combining more than one 'sub-distributions.' (usually, but not necessarily, of the same kind) Here we focus on Gaussian mixture. There are a number of possibilities regarding how the sub-distributions are combined, the use of Markov chain being a prominent one. Essentially, every time we need a new random variable to be generated, we first toss a coin to determine which sub-distribution out of the mixture to draw from. In the case of a mixture of two Gaussians, if one sub-distribution has a larger variance than the other, then the mixture would have fatter tail, although the individual sub-distributions do not.
Candidate: Mixture
Another French Mathematician
If producing a fatter tail is all we care about, then what about substituting Gaussian process with something with excess kurtosis? The resulting model would likely not have analytic solution, but we can fall back on numerical methods as our last resort. For example, ask the computer to generate 10000 random numbers from a Student's t distribution and use those in a Monte Carlo simulation.
The idea sounds neat, but one has to be cautious about it. We may not be aware of it, but when we were modeling asset prices with Gaussian or Poisson processes, both of the processes are closed under linear transformation. In other words, aggregating multiple Gaussian (or Poisson) random variables would result in yet another Gaussian (or Poisson) variable. That means when we use Gaussian process to model asset prices, even though it may not be a very faithful description of reality, at least we are being consistent and we know what we are getting ourselves into: namely, if the one-day distribution is an N(0.01, 0.05), then the one-month distribution would be an N(0.25,0.25), etc. Other distributions in general do not have this property. If in our hypothetical Monte Carlo simulation we draw from a t distribution with a degree of freedom of 10 for daily return, how would the monthly return be distributed? How about quarterly?
These problems can be avoided by going for non-Gaussian processes while staying within the territory of Levy processes, which is a broad family of processes that possess the nice property of being closed under linear transformation. (obviously both Gaussian and Poisson processes are members of this family)
- The numerical pricing procedure becomes more involved, especially for grid/finite differencing methods (because we end up with an integro-differential equation, as opposed to a PDE)
- Although we usually speak of "the" jump diffusion model, we are free in specifying the probability distribution of the jump amplitude
So is jump diffusion the ultimate holy grail? And is pure diffusion model done with? For the first question, we will see later in the series that there are many other approaches that supersede jump diffusion, but for now let's take a step back and address the second question.
It turns out that the use of mixtures is able to tackle at least some of the shortcomings of the original random walk model. A mixture, not surprisingly, is formed by combining more than one 'sub-distributions.' (usually, but not necessarily, of the same kind) Here we focus on Gaussian mixture. There are a number of possibilities regarding how the sub-distributions are combined, the use of Markov chain being a prominent one. Essentially, every time we need a new random variable to be generated, we first toss a coin to determine which sub-distribution out of the mixture to draw from. In the case of a mixture of two Gaussians, if one sub-distribution has a larger variance than the other, then the mixture would have fatter tail, although the individual sub-distributions do not.
Candidate: Mixture
- Markovian
- Most likely not tractable
- Excess kurtosis
- Market incomplete
Another French Mathematician
If producing a fatter tail is all we care about, then what about substituting Gaussian process with something with excess kurtosis? The resulting model would likely not have analytic solution, but we can fall back on numerical methods as our last resort. For example, ask the computer to generate 10000 random numbers from a Student's t distribution and use those in a Monte Carlo simulation.
The idea sounds neat, but one has to be cautious about it. We may not be aware of it, but when we were modeling asset prices with Gaussian or Poisson processes, both of the processes are closed under linear transformation. In other words, aggregating multiple Gaussian (or Poisson) random variables would result in yet another Gaussian (or Poisson) variable. That means when we use Gaussian process to model asset prices, even though it may not be a very faithful description of reality, at least we are being consistent and we know what we are getting ourselves into: namely, if the one-day distribution is an N(0.01, 0.05), then the one-month distribution would be an N(0.25,0.25), etc. Other distributions in general do not have this property. If in our hypothetical Monte Carlo simulation we draw from a t distribution with a degree of freedom of 10 for daily return, how would the monthly return be distributed? How about quarterly?
These problems can be avoided by going for non-Gaussian processes while staying within the territory of Levy processes, which is a broad family of processes that possess the nice property of being closed under linear transformation. (obviously both Gaussian and Poisson processes are members of this family)
Tuesday, January 28, 2014
Other Interview Questions
Q: It's 12:00 now. What time would it be when the minute hand crosses the hour hand again?
A: Between 1200 and 2400, this will happen for 11 times. So divide 12 hr by 11 and add to 1200, i.e. 13:05:27
Q: A cell can do 4 things: 1) Dies; 2) Nothing; 3) Duplicate; or 4) Triplicate. What is P(colony dies out) if we start with one single cell?
A: Solve the polynomial
$ p = \frac {1} {4} + \frac {1}{4} p + \frac {1}{4} p^2 + \frac {1}{4} p^3$
Q: A 6x6 matrix has entries of either +1 or -1. How many unique combinations are there such that all column products and row products are +1?
A: Consider the top left 5x5 sub-matrix. It can take any permutation (as long as each row/column contains no more than 3 same number) because we can rely on the rest of the 6x6 matrix (an "L" shape) to "fix" it. So the answer is $ 2^{25} $
Q: There is an integer X. The product of the digits is 96. What is the largest/smallest possible value of X?
A: smallest = 268, largest = 322222
Q: What is the sum of all digits of all the numbers between 1 and 1000000?
A: Convince yourself that all digits appear for an equal number of times. The answer is 27000001
Q: A bus makes a stop, and 3/4 of all passengers get off, while 7 get on. This repeats for two more times. What is the smallest number of initial passengers?
A: 52
Q: Paint the outside of a cube, then dice it into 27 equal smaller cubes. Pick one at random and roll it. What is P(no paint visible after the roll)?
A: $ 6/27 \times 1/6 + 1/27 $
Q: Two equally talented teams are playing a series of games in which the first team to win 4 games wins the series. What is P(7th game has to be played)?
A: $ \frac {6!}{3!3!} \frac {1}{2^6} = \frac {5}{16}$
Q: I roll a die, spin a roulette and draw a card from a deck of 52. What is the probability that all three give the same number?
A: $ 5 \times \frac 1 6 \times \frac 1 {13} \times 1 {38} $
Q: What is the last digit of 3 to the power 33?
A: Some experimentation would indicate that $3^0=1$, $3^1=3$, $
Q: N couples shake hand with others. It is known that 1) They don't shake hand with their own partners; and 2) The first (2N - 1) people surveyed all have different number of handshakes. What is the number of handshake the remaining person made?
A: N - 1 (Can draw graphs to deduce; any analytic solution?)
Q: What is P(3 random points on a circle are within an 180 degree arc)?
A: There are two approaches: 1) Area on an abstract x-y plane, x and y are distances from the first point pinned down (call it z, which is arbitrary); or 2) $ N \times \frac {1}{2^{N-1}} $, with $ N=3$. Both give the answer of 3/4.
Q: How do you simulate a 6-sided die using a fair coin? What's the expected number of toss to produce the number?
A: Use a binary scheme. With 3 tosses, there are 8 possible outcomes, which is more than enough to simulate 6 sides. The trick is to know which 2 to exclude. {HHH,TTT} would be a bad choice because you always have to wait until the 3rd toss to know if you failed. So we should choose something like {HHH,HHT} or {THH,THT}. The expected number of toss is given by solving
$E[N]=\frac 6 8 \times 3 + \frac 2 8 (2+E[N])$
Q: Place 3 points randomly on the perimeter of a square. What is P(they don't form a triangle) and P(all lie on different edges)?
A: $P(they_don't
Q: 10 light bulbs are lined up in a row, and it is known that no two of the adjacent light bulbs can be both on. What is the possible number of arrangements?
A: Fibonacci sequence, 144
Q: You have a large number of red and blue balls (equally many) in a large container. What is P(odd number of red) if you draw a) 3 balls from the container? b) 10 balls from the container?
A: 0.5 regardless of how many you draw. For example if 3 are drawn, the binomial distribution is 1(odd) 3(even) 3(odd) 1(even); if 4 are drawn, the binomial distribution is 1(even) 4(odd) 6(even) 4(odd) 1(even).
Q: Transport as many apples as possible to a destination 1000 km away starting with 3000 apples. For each km of transportation, you lose 1 apple.
A: The best tactic is to always start with full load so as to maximize number of "apple km" traveled per apple lost. So the 1st stop is optimally at 3000 - 3X = 2000 <=> X = 333; the 2nd stop is optimally at 2000 - 2X = 1000 <=> X = 500. After 833 km, we are left with 1000 apples. Hence we will have 833 apples at the destination.
Q: You are playing against two players A and B individually in a tournament, with A being the better player. If you have to win at least 2 consecutive games out of 3 in order to be the champion, would you prefer the order ABA or BAB?
A: Out of the 8 outcomes {LLL,LLW,LWL,LWW,WLL,WLW,WWL,WWW}, only {WWW,WWL,LWW} are desirable. If q = P(winning against A) and p = P(winning against B) so that p > q,
P(champion with the order ABA) = pqp + pq(1-p) + (1-p)qp = 2pq - ppq
P(champion with the order BAB) = qpq + qp(1-q) + (1-q)pq = 2pq - pqq
So P(champion with the order BAB) > P(champion with the order ABA)
A: Between 1200 and 2400, this will happen for 11 times. So divide 12 hr by 11 and add to 1200, i.e. 13:05:27
Q: A cell can do 4 things: 1) Dies; 2) Nothing; 3) Duplicate; or 4) Triplicate. What is P(colony dies out) if we start with one single cell?
A: Solve the polynomial
$ p = \frac {1} {4} + \frac {1}{4} p + \frac {1}{4} p^2 + \frac {1}{4} p^3$
Q: A 6x6 matrix has entries of either +1 or -1. How many unique combinations are there such that all column products and row products are +1?
A: Consider the top left 5x5 sub-matrix. It can take any permutation (as long as each row/column contains no more than 3 same number) because we can rely on the rest of the 6x6 matrix (an "L" shape) to "fix" it. So the answer is $ 2^{25} $
Q: There is an integer X. The product of the digits is 96. What is the largest/smallest possible value of X?
A: smallest = 268, largest = 322222
Q: What is the sum of all digits of all the numbers between 1 and 1000000?
A: Convince yourself that all digits appear for an equal number of times. The answer is 27000001
Q: A bus makes a stop, and 3/4 of all passengers get off, while 7 get on. This repeats for two more times. What is the smallest number of initial passengers?
A: 52
Q: Paint the outside of a cube, then dice it into 27 equal smaller cubes. Pick one at random and roll it. What is P(no paint visible after the roll)?
A: $ 6/27 \times 1/6 + 1/27 $
Q: Two equally talented teams are playing a series of games in which the first team to win 4 games wins the series. What is P(7th game has to be played)?
A: $ \frac {6!}{3!3!} \frac {1}{2^6} = \frac {5}{16}$
Q: I roll a die, spin a roulette and draw a card from a deck of 52. What is the probability that all three give the same number?
A: $ 5 \times \frac 1 6 \times \frac 1 {13} \times 1 {38} $
Q: What is the last digit of 3 to the power 33?
A: Some experimentation would indicate that $3^0=1$, $3^1=3$, $
Q: N couples shake hand with others. It is known that 1) They don't shake hand with their own partners; and 2) The first (2N - 1) people surveyed all have different number of handshakes. What is the number of handshake the remaining person made?
A: N - 1 (Can draw graphs to deduce; any analytic solution?)
Q: What is P(3 random points on a circle are within an 180 degree arc)?
A: There are two approaches: 1) Area on an abstract x-y plane, x and y are distances from the first point pinned down (call it z, which is arbitrary); or 2) $ N \times \frac {1}{2^{N-1}} $, with $ N=3$. Both give the answer of 3/4.
Q: How do you simulate a 6-sided die using a fair coin? What's the expected number of toss to produce the number?
A: Use a binary scheme. With 3 tosses, there are 8 possible outcomes, which is more than enough to simulate 6 sides. The trick is to know which 2 to exclude. {HHH,TTT} would be a bad choice because you always have to wait until the 3rd toss to know if you failed. So we should choose something like {HHH,HHT} or {THH,THT}. The expected number of toss is given by solving
$E[N]=\frac 6 8 \times 3 + \frac 2 8 (2+E[N])$
Q: Place 3 points randomly on the perimeter of a square. What is P(they don't form a triangle) and P(all lie on different edges)?
A: $P(they_don't
__Q: 10 light bulbs are lined up in a row, and it is known that no two of the adjacent light bulbs can be both on. What is the possible number of arrangements?
A: Fibonacci sequence, 144
Q: You have a large number of red and blue balls (equally many) in a large container. What is P(odd number of red) if you draw a) 3 balls from the container? b) 10 balls from the container?
A: 0.5 regardless of how many you draw. For example if 3 are drawn, the binomial distribution is 1(odd) 3(even) 3(odd) 1(even); if 4 are drawn, the binomial distribution is 1(even) 4(odd) 6(even) 4(odd) 1(even).
Q: Transport as many apples as possible to a destination 1000 km away starting with 3000 apples. For each km of transportation, you lose 1 apple.
A: The best tactic is to always start with full load so as to maximize number of "apple km" traveled per apple lost. So the 1st stop is optimally at 3000 - 3X = 2000 <=> X = 333; the 2nd stop is optimally at 2000 - 2X = 1000 <=> X = 500. After 833 km, we are left with 1000 apples. Hence we will have 833 apples at the destination.
Q: You are playing against two players A and B individually in a tournament, with A being the better player. If you have to win at least 2 consecutive games out of 3 in order to be the champion, would you prefer the order ABA or BAB?
A: Out of the 8 outcomes {LLL,LLW,LWL,LWW,WLL,WLW,WWL,WWW}, only {WWW,WWL,LWW} are desirable. If q = P(winning against A) and p = P(winning against B) so that p > q,
P(champion with the order ABA) = pqp + pq(1-p) + (1-p)qp = 2pq - ppq
P(champion with the order BAB) = qpq + qp(1-q) + (1-q)pq = 2pq - pqq
So P(champion with the order BAB) > P(champion with the order ABA)
Friday, January 17, 2014
Short Notes on HMM (Hidden Markov Model)
1. Regarding calibration
Numerical optimization is computatinoal intensive and
prone to local max, but it is able to estimate any general model
specification. On the other hand, EM algorithms such as Baum-Welch are
more reliable in seeking global max, but they are only capable of
backing out the parameters of models with distributions that are fully
described by moments (Gaussian, Poisson, ...)
2. Problem with HMM, and extensions
As Soltan discusses in his paper, ordinary HMM is by
definition prone to instability due to the exponentiated matrix
structure. The instability dominates in the long run, meaning that state
occupancy duration estimation of ordinary HMM is usually unreliable.
There are two ways to go: 1) HSMM (a.k.a. explicit duration HMM, inhomogeneous HMM, etc.), or 2)
Treat duration as an extra degree of state space (see Soltan).
References:
Friday, December 13, 2013
The Importance of Trading More
This is by no means an attempt to promote high frequency trading (HFT). In fact, the HFT scene has become so crowded that even real pro shops are having a hard time, let alone retail traders with their home brew system (By the way, here is an interesting read. Judge for yourself how much to believe). So why should a trader trade more?
Because it's about how confident you can be in making a conclusion. If you make one trade in your life and it turns out winning, your rate of winning is 100% and yet the only legitimate conclusion you can make is...well, that you don't have enough data point. In the spirit of Bayesian statistics as was used here, we can formulate a simple analysis that hopefully would provide some insights.
Suppose that you are a manager about to hire a new trader for your team. There are two candidates, Andrew Flook who had 5 winning trades out of 5 last year; and Bob Luckson who had 70 winning trades out of 100 last year. Who should get the job? Since Andrew has a 100% winning rate and Bob has only 70%...are we missing something?
Let's cast this in the light of Bayesian statistics. Of course I would have to make some assumptions:
Winning probability of a fluke trader = p = 0.5
Winning probability of a skilled trader = q = 0.7
Total number of winning trades = W
Total number of losing trades = L
Unconditional probability that any trader is a skilled one = s = 0.2
The last assumption about a trader being a skilled one is based on the anecdotal evidence that only about 20% of all traders are profitable in the long run. So, if $R$ stands for the trading Results of last year, $S$($F$) stands for the trader being a Skilled(Fluke) one, we have
$$ P(R|S)P(S) = q^W (1-q)^L s $$
$$ P(R|F)P(F) = p^W (1-p)^L (1-s) $$
$$ P(S|R) = \frac {P(R|S)P(S) }{P(R|S)P(S) +P(R|F)P(F) } $$
Plugging in the numbers, we find that Andrew (the 100% guy) has a 57% chance of being a skilled trader, while Bob enjoys a 99.9% chance.
Because it's about how confident you can be in making a conclusion. If you make one trade in your life and it turns out winning, your rate of winning is 100% and yet the only legitimate conclusion you can make is...well, that you don't have enough data point. In the spirit of Bayesian statistics as was used here, we can formulate a simple analysis that hopefully would provide some insights.
Suppose that you are a manager about to hire a new trader for your team. There are two candidates, Andrew Flook who had 5 winning trades out of 5 last year; and Bob Luckson who had 70 winning trades out of 100 last year. Who should get the job? Since Andrew has a 100% winning rate and Bob has only 70%...are we missing something?
Let's cast this in the light of Bayesian statistics. Of course I would have to make some assumptions:
Winning probability of a fluke trader = p = 0.5
Winning probability of a skilled trader = q = 0.7
Total number of winning trades = W
Total number of losing trades = L
Unconditional probability that any trader is a skilled one = s = 0.2
The last assumption about a trader being a skilled one is based on the anecdotal evidence that only about 20% of all traders are profitable in the long run. So, if $R$ stands for the trading Results of last year, $S$($F$) stands for the trader being a Skilled(Fluke) one, we have
$$ P(R|S)P(S) = q^W (1-q)^L s $$
$$ P(R|F)P(F) = p^W (1-p)^L (1-s) $$
$$ P(S|R) = \frac {P(R|S)P(S) }{P(R|S)P(S) +P(R|F)P(F) } $$
Plugging in the numbers, we find that Andrew (the 100% guy) has a 57% chance of being a skilled trader, while Bob enjoys a 99.9% chance.
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
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
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?
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)
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)
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!
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:
Our Checklist
Before proceeding further, let's compile a checklist that we will re-visit multiple times in this series:
Candidate: Brownian motion
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.
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)
- 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
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
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
Subscribe to:
Posts (Atom)