Notes on Arbitrage

A lot of people and funds claim that they perform arbitrage in order to make a profit. Sometimes it is a little confusing because the term "arbitrage" is used by different individuals to mean quite different things (especially with terms such as stat arb). I think arbitrage can carry a few distinct meanings:

1. The real, good-old sure profit arbitrage
This refers to the option-pricing kind of arbitrage. The PnL is deterministic, since you are basically earning a sure profit by long-shorting the same security across different markets to exploit the price discrepancy. Examples would be a) trading the same contract listed on two exchanges when the prices diverge; and 2) synthesizing a contract (e.g. future) using something else (e.g. call and put).

2. Statistical arbitrage, looking at historical data
This refers to fitting a model to the historical performance. A classic example is pairs trading, in which the price of two assets are expected to return to the "normal" level when a deviation is observed. In a sense, this kind of arbitrage relies on the real world probability distribution as suggested by historical data.

3. Statistical arbitrage, looking at market data
This refers to fitting a model to the market prices. For example, one can try to see if the deep OTM options are over-priced or under-priced, by studying the Greeks. In a sense, this kind of arbitrage relies on the risk-neutral probability distribution as suggested by market data.

Book Review: Volatility Trading by Euan Sinclair

I first came across this book a few years back. I didn't put much time and thought on it back then but now that I revisit it, I find that it is actually quite a practical book for anyone who wants to investigate volatility trading.

The book covers a lot of ground, from basic vol trading principles to vol forecasting to hedging and bet sizing. Perhaps you will find that it tries too hard to be comprehensive, so feel free to skip some sections (such as Ch.8 Psychology).


Nonetheless, there are some good parts. In Ch.2 the author talks about different ways to measure volatility (different calculation methodologies, data with different frequencies etc.). These go beyond the most common definition of volatility, and are essential for creating useful and relevant estimators.

Of particular interest is the section on forecasting volatility. Here Sinclair explains the merits and shortcomings of GARCH type models from a practical point of view. The volatility cone is introduced, and although some might find it too heuristic and ad hoc, it does provide a relatively simple and systematic way to bring implied vol and realized vol into comparison.

The chapter on vol surface dynamics is quite weak, which is possibly a price to pay by not including too much theory. However the chapter on hedging is definitely worth a read, as it is not so much a crash course on Greeks calculation, but rather an in-depth investigation on why, what and when to hedge when trying to trade volatility.

http://www.amazon.com/Volatility-Trading-CD-ROM-Wiley/dp/0470181990

Those damn dice...

To recap, a dice rolling game contrasts with coin tossing in:

- Coin tossing follows a binomial distribution (which converges to Gaussian); die rolling follows a uniform distribution.

- Tossing m coins gives an expectation value of m/2; rolling an m-sided die gives an expectation value of (m+1)/2.

Since the probability distribution itself for dice game is simpler, the game you would encounter in an interview is usually more complex to compensate for it. Let's start with some easy ones.

DR01
Player A rolls one die for 4 times, aiming to get one 6; player B rolls two dice for 24 times, aiming to get (6,6). Who has a better chance of winning?

DR01 - Answer:
The probabilities are 1-(5/6)^4 vs. 1-(35/36)^24

DR02
When rolling 2 dice, what is P(both are 6 | at least one 6)?

DR02 - Answer:
Bayesian: (1 * 1/36) / (1 - 25/36) = 1/11

DR03
You have two dice, one is 10-sided and the other is 20-sided. What is P(points on 10-sided die > points on 20-sided die)?

DR03 - Answer:
(1 + ... + 9) / 200 = 9/40

See here for more interview questions/brainteasers

More Coin Problems

CT10
What is P(# of H out of 4 tosses >= # of H out of 5 tosses)?

CT10 - Answer:
1/2 (symmetry consideration)

CT11
Flip n unbiased coins. What is P(# of H = n/2)?

CT11 - Answer:
nC_(n/2)/2^n

CT12
Toss 4 coins and win the number of H. There is an option to re-toss. What is the value of the game?

CT12 - Answer:
([1 4 6 4 1] * [2 2 2 3 4]') / 16 = $2.375 (dynamic programming/backward induction)

CT13
What is the expected product of (# of H) * (# of T) when tossing 10 fair coins? (Hint: the answer is not 25)

CT13 - Answer:
22.5 (E[(# of H) * (10 - # of H)])

CT14
Keep flipping a fair coin. What is the probability that the sequence HHT appears before THH does?

CT14 - Answer:
1/4 (Once you have T, THH would always precede HHT; likewise, once you have HH, HHT would always precede THH)

CT15
Toss 4 coins and win the number of H. There is an option to re-toss one coin. What is the value of the game?

CT15 - Answer:
2 + 0.5 * 15/16 = $2.469 (dynamic programming/backward induction)

See here for more interview questions/brainteasers

Introduction to a Weird Game

So here is a game that recently came to mind. The two-player case is almost trivial, but let's begin with it anyway.

There are players A and B. The game is turn based, at the beginning of each turn they bet on the result of the turn: A wins or B wins (so a person is allowed to bet on herself), where win is defined as scoring more points than the other person. The scoring rules are:

1. An "A wins" bet gives one point to A; the same goes for B.
2. Betting on the right winner gives a point (i.e. if B bets that A wins and A does win, then B scores a point)

At the end of the turn, calculate the points. A "draw" is called if either logical contradiction is resulted, or the two players tie in score. When there is a draw, a new turn is played. As soon as there is a loser, the game ends. There are four scenarios:

1. A bets A wins; B bets B wins
2. A bets B wins; B bets A wins
3. Both bets are A wins
4. Both bets are B wins

Let's investigate the outcomes.

For scenario 1, each player gains one point, so it's a draw.
For scenario 2 also, each player gains one point, so it's a draw.
For scenario 3, A scores 3 points versus B scores 1 point, A wins.
For scenario 4, A scores 1 point versus B scores 3 points, B wins.

So assuming everyone wants to be the winner, the best strategy is to bet on oneself. Now we introduce a new rule to make the game more fun: one can bet against a certain player, i.e. bet that she loses:

1. An "A loses" bet deducts one point from A; the same goes for B.
2. Betting on the right loser gives a point (i.e. if B bets that A loses and A does lose, then B scores a point)

It seems that for a 2-player game, the new rules do not change the nature of the game much. Thus the best strategy is to bet on oneself (or, equivalently, to bet that the other person loses). What if there are three players? Would it still be the case that the best course of action is to always bet on oneself?

Those damn coins... (Part III)

This is the final episode of coin flipping problems (previous discussions can be found here and here). Last time we ended the discussion with the expected number of toss such that the sequence HH (or other combinations like HT or THH) appears for the first time. Now we consider playing games involving H and T combinations. The first type of game concerns the probability of combination A appearing before B does while flipping an unbiased coin.

CT08
Keep flipping a fair coin. What is the probability that the sequence HTT appears before HHT does?

CT08 - Answer:
This can be solved by setting up the problem as a Markov chain and calculating the absorption probabilities. Alternatively, letting A = HTT appears before HHT, we can consider the conditional probabilities conditioning on the first 3 flips:
P(A)
= P(A|HHH) + P(A|HHT) + P(A|HTH) + P(A|HTT) + P(A|THH) + P(A|THT) + P(A|TTH) + P(A|TTT)
Now it's time to simplify terms:
P(A|HHH) = 0
P(A|HHT) = 0
P(A|HTH) = P(A|H)
P(A|HTT) = 1
P(A|H) = P(A|T) = P(A)
So
P(A) = 1/8 * 0 + 1/8 * 0 + 1/8 *  P(A) + 1/8 * 1 + 1/2 * P(A)
=>  P(A)= 1/3

The second type of game is a little different from the previous case:

CT09
Two players take turn tossing a fair coin. When the sequence HT shows up for the first time, the person who flipped the T wins. What are the probabilities of winning for each player?

CT09 - Answer:
Once again conditional probability saves the day. Let A = First player wins,
P(A) = 0.5 * P(A|H) + 0.5 * P(A|T)
But P(A|T) = P(B) = 1 - P(A) (because "the second player becomes the first" if the first toss give a T)
Also, P(A|H) = 0.5 * P(A|HT) + 0.5 * P(A|HH) = 0.5 * 0 + 0.5 * (1 - P(A|H))
=>  P(A|H) = 1/3
So
P(A) = 0.5 * 1/3 + 0.5 * (1 - P(A))
P(A) = 4/9

See here for more interview questions/brainteasers

Those damn coins... (Part II)

Last time we saw a number of coin-tossing related interview questions. In this post we look at two types of more advanced coin-related problems:
1) (possibly) unfair coins with odds drawn from a continuous distribution, and
2) games involving trying to obtain a specific sequence of Heads and Tails

1) Coins with odds drawn from a continuous distribution
If we cannot be sure about the odds of the coin, there would be another extra degree of randomness.

CT05
Suppose you have an unfair coin with P(Tail) = p, p is an unknown constant. What is the probability distribution of N, where N is the event: 'The first Head shows up at the N-th toss', and what is the expectation value of N?

CT05 - Answer:
The probability distribution is simply the Geometric Distribution p^(N-1) (1-p).
The expectation value of N is E[N] = 1/(1-p), which can be found by
E[N] = Sum_(i=1)^(inf) i*p^(i-1) (1-p)
Noting that
i*p^(i-1) = (d/dp)p^i
Using this and exchanging the order of summation and differentiation, we get
E[N] = 1/(1-p)

Meanwhile, if the odds of Head itself is drawn from a known distribution, then we can compute the desired expected values with integrals:

CT06
Suppose you have an unfair coin, with probability of a head p ~ uniform(0,1). What is the probability of getting 2 (or n) heads with 2 (or n) tosses?

CT06 - Answer:
If the coin is fair, then P(2 Heads) = 1/4. But now we would have to integrate
\int_0^1 p^n U(0,1) dp = 1/(n+1)
So for 2 tosses P(2 Heads) = 1/3.
Note that while for a fair coin with n tosses, the probabilites of obtaining {1,2,3,...,n} Heads are binomial coefficients, in this case the probabilites of obtaining {1,2,3,...,n} Heads are identical.


2) Games involving trying to obtain a specific sequence of Heads and Tails
This is yet another popular genre of interview questions, possibly because the questions can be varied easily (for example, by modifying the desired sequence of H and T). There are two sub-types: i) what is the probability that sequence A would show up before sequence B does? and ii) what is the probability that sequence A would be obtained during the first/second player's turn? (assuming that the two take turns) The two sub-types are to be solved in different ways. Let's start with the expected number of toss for obtaining a particular sequence.

CT07
Keep flipping a fair coin. What is the expected number of toss such that the sequence HH appears for the first time? What about HT and HHH?

CT07 - Answer:
One can take the most general coute and solve this as a Markov chain problem. For short sequences, especially for repeating sequences (i.e. HH, TT, HHH, etc.), writing down a recursive formula should be faster. Let N(A) be the expected number of toss to obtain the sequence A. Then
N(T) = N(H) = 2
N(HH) = N(H) + 0.5 * 1 + 0.5 * (1 + N(HH)) => N(HH) = 6
 The recursive formula can be understood as the two possible outcomes upon obtaining the first H: either another H immediately, in which case the sequence HH is complete, or a T, in which case one has to start over from scratch, hence the N(HH) on the right hand side. It is not hard to prove by induction that, for B = k consecutive H,

N(B) = 2^(k+1) - 2
is a close-form solution. For general sequences, the recursive formula approach still works, though you would have to know the expected number of tosses for the sub-swquences. For instance:

N(HT) = N(H) + 0.5 * 1 + 0.5 * (1 + N(T))
N(HTH) = N(HT) + 0.5 * 1 + 0.5 * (1 + 0.5 * N(HTH))
N(HHT) = N(HH) + 0.5 * 1 + 0.5 * (1 + N(T))

What if we want to know the probability that sequence A would show up before sequence B does? We'll discuss that next time.

See here for more interview questions/brainteasers

Quick Notes - Trading Ideas

• Momentum can be a result of nonlinearity/positive feedback due to algo trading: buy and sell orders induce more orders of their own kinds. Also, especially during market open, order regularities is a sign of algo in action. Can those be detected and exploited?
• Support and resistance levels, together with trading volume, provide useful insights. However, support and resistance levels (and similarly some other price patterns) are difficult to be quantified. Can neural network help?
• Support and resistance levels and volume data are more useful for securities that does not attract a lot of hedging investors (examples: commodities futures, mid cap stocks; counter-examples: ETF, some index futures).

Those damn coins...

Coin tossing (or coin flipping) is one of the popular settings for probability questions. It might be of interest to contrast coin tossing and dice rolling:

- Coin tossing follows a binomial distribution (which converges to Gaussian); die rolling follows a uniform distribution.

- Tossing m coins gives an expectation value of m/2; rolling an m-sided die gives an expectation value of (m+1)/2.

Because of the binomial distribution, coin tossing problems usually are more involved than dice rolling in terms of arithmetics. The most straight-forward kind of coin problems would simply ask you about the mean and variance of the number of Head or Tail:

CT01
What is the expected gain if you are paid $1 for each head in tossing 4 fair coins? What is the standard deviation?

CT01 - Answer:
Remember that in n binary trials with single success probability p, the mean is np and the variance is np(1-p). So the expected gain is $2 and the standard deviation is $1.

Sometimes the question is framed as a game:

CT02
What is the probability that the number of Heads is greater than or equals to 2 when tossing 4 coins?

CT02 - Answer:
The Pascal numbers for 4 trials are {1,4,6,4,1}. Hence the required probability is (6+4+1)/16 = 11/16.

Once the number of tossing becomes large, the Law of Large Number is handy.

CT03
What is the probability that there are more than 60 Heads out of tossing 100 coins?
CT03 - Answer:
The last thing you want to do is to calculate the binomial coefficients explicitly. Instead, observe that the probability distribution converges to a Gaussian as number of trials goes to infinity, with mean equals fifty and variance equals 25 (hence the standard deviation is 5). 60 is two standard deviations away from the mean, and the 68-95-997 rule gives (1 - 95%)/2 = 2.5%.

Another way to ask coin-tossing brainteeasers is to play with Bayesian statistics.

CT04
There are three coins, one with a H side and a T side (coin A); one with both sides being T (coin B); one with both sides being H (coin C).If you draw one among them at random and toss it to observe a Head, what is the conditional probability that coin C is picked?
CT04 - Answer:
This is a typical Bayesian inference question. Let X = [coin C is picked] and Y = [the toss gives an H], then
P(X|Y) = P(Y|X)*P(X)/P(Y) = 1 * (1/3) / (1/3*0 + 1/3*1/2 + 1/3*1) = 2/3

Hope you find this helpful. More to come!

See here for more interview questions/brainteasers

All those interview questions and brainteasers...

It has been a while since this blog was created. It is intended to be a handy way to look up questions and brainteasers for interview preparation, although from time to time other relevant and interesting stuffs are also discussed.

I have recently once again been looking at a lot of the popular quant interview questions, and an idea comes to mind: perhaps it is worthwhile to re-do some posts in a more systemic manner? Instead of listing the questions and answers out, maybe a discussion of the brainteasers according to their solution technique would bring about more benefits?

It is with this spirit that I embark on this little project. In the following number of posts I would try to group different interview questions into categories and discuss them in more detail, especially how one should approach and attack them. You would find that all previous interview questions/brainteasers posts are now linked here; those posts would remain where they are, so you can think of this post as an overview or introduction.

Where to find more interview questions and brainteasers?
There are two popular printed books that are used extensively in interviews:
A Practical Guide To Quantitative Finance Interviews by Zhou, and
Heard on The Street: Quantitative Questions from Wall Street Job Interviews by Crack
Also, Frequently Asked Questions in Quantitative Finance by Wilmott has a relatively short section on brainteasers, although it is a compilation of materials available on his awesome website (see below). Quant Job Interview Questions And Answers by Joshi et al seems to be a good source too, though I have not read it myself.

Apart from printed books, there is an abundance of resource on the internet. The brainteaser section on the forum of Wilmott.com often has some original questions. Sites such as Braingle and Brainden are dedicated to brainteasers, although those might not be the ones that usually show up during interviews. For those looking for real challenges, wu :: forums should be able to keep you busy.

Finally, if you search the site Glassdoor for a particular company, there will be a bunch of questions that are submitted by those who have interviewed with the firm, with attempts to answer the questions (the quality of which can vary). If you can read Chinese, mitbbs.com has more questions that have actually been asked by interviewers (usually banks).

What should I expect?
Some brainteasers don't really require lengthy calculation. It takes a very specific 'Eureka' moment to be answered. It's fair to say that you won't know the answer if you haven't seen it before. And in case you wonder, yes, such questions do show up at interviews.

Otherwise, the majority of the questions does require calculation. When you are practising, don't just memorize the answer (that's obvious). Think about 1) why the answer is what it is; 2) whether there are alternative, shorter and sweeter ways to solve it; and 3) if the question could have been altered or extended. One thing that I find especially useful is to verify the answers using simulations. That not only assures you of correctness, but also gives you some intuition, as well as a handy way to play with different parameters and assumptinos.

So, here we go:

The series
Those damn coins... 
Those damn coins... (Part II) 
Those damn coins... (Part III)
More Coin Problems
Those damn dice...  
Those damn dice... (Part II) 
Those damn cards...