Max Dama on Automated Trading - Brain Teasers - Answers

Click to see the full text. Below are my answers.

Market Making and Betting

Flip 98 fair coins and 1 HH coin and 1 TT coin. Given that you see an H, what is the probability that it was the HH coin? Explain in layman’s terms.

98 coins have 50% of H, 1 coin has 100% of H, so `1/(1 + 98 * 0.5) = 50%` chance of it being the HH coin.

Flip 10000 fair coins. You are offered a 1-1 bet that the sum is less than 5000. You can bet 1, 2, …, 100 dollars. How much will you bet. How much will you bet if someone tells you that the sum of the coins is less than 5100?

The chance of exactly 5000 is `((10000), (5000)) * 0.5^10000 = 0.79%` . So there is `(1 - 0.0079) / 2 = 49.6%` chance of < 5000, bad bet. For 5100 the chance is 97.6%. Bet the Kelly criterion of `0.976 * 2 - 1 = 95.2%` of your money.

Roll a die repeatedly. Say that you stop when the sum goes above 63. What is the probability that the second to last value was X. Make a market on this probability. I.e. what is your 90 percent confidence interval.

The probability is also 1/6. Simulation:

import random

def roll():
  return random.randint(1, 6)

def run(n):
  total = 0
  rolls = []
  while total <= n:
    cur = roll()
    rolls.append(cur)
    total += cur
  return rolls[-2]

def main():
  random.seed()
  count = dict((x + 1, 0) for x in xrange(6))
  ITERATIONS = 10000
  for i in xrange(ITERATIONS):
    res = run(63)
    count[res] += 1
  for value, cnt in count.iteritems():
    chance = cnt * 100 / float(ITERATIONS)
    print '%d: %2.0f%% %s' % (value, chance, '*' * int(chance))

main()

There are closed envelopes with $2, $4, $8, $16, $32, and $64 lined up in sorted order in front of you. Two envelopes next to each other are picked up and shuffled. One is given to you and one is given to your friend. You and you friend then open your own envelopes, look inside, and then decide whether or not to offer to trade. If you both agree to trade, then you will swap. Assume you open your envelope and see $16. Should you offer to trade?

You have 4 cases:

  1. sorted increasing, picked 4th and 5th => trade
  2. sorted increasing, picked 3rd and 4th => don’t trade
  3. sorted decreasing, picked 3rd and 4th => don’t trade
  4. sorted decreasing, picked 2nd and 3rd => trade

You can’t differentiate (2) and (3), but their answer is the same.

Generate N random values from a random variable where the value N comes from some other variable. Make a market on the sum of the values.

`E(sum^N X) = sum^N E(X) = N * E(X)` .

Find the log-utility optimal fraction of your capital to bet on a fair coin flip where you win x on a heads and lose y on tails.

Bet y with odds `b = (x - y) / y` . Kelly criterion: `(0.5 * (b + 1) - 1)/b` , which simplifies to `(0.5x - y) / (x - y)` .

Explain how you would handle a trading model with 25 factors differently than one with 100. What you would ask or do next if the 100 factor model had 25% better performance than the 25 factor model?

???

If a stock starts at a price of p and then goes up x% then down x%, is its price greater than, less than, or equal to p?

Greater, since the “down x%” is a percentage of a bigger number. `p * (1 + x) * (1 - x) = p * (1 - x^2) < p` for x > 0.

You have 100 dollars. You are playing a game where you wager x dollars on a biased coin flip with a 90 percent probability of heads. You make 2x if it’s heads and lose the x dollars if it’s tails. How much do you think you should bet on each flip if you are going to play for 100 flips?

Odds `b = (2x - x) / x = 1` . Kelly criterion: `0.9 * 2 - 1 = 80%` of your money.

Make a market on a derivative with a price equal to the number of pothole covers in New York.

???

Probability

What is the probability of getting exactly 500 heads out of 1000 coin flips? Approximate it to within 5% of the true value without a calculator.

Using Stirling’s approximation: `n! ~= sqrt(2pin)(n/e)^n` .

On paper I got `((1000), (500)) * 0.5^1000 = (1000! * 0.5^1000) / (500! * 500!) ~= (sqrt(2pi1000)(1000/e)^1000 * 0.5^1000)/((sqrt(2pi500)(500/e)^500)^2) = ... = 1/sqrt(pi500) = 1/(10sqrt(5pi)) ~= 1/40 = 2.5%` . On calculator I get 2.52%.

Play a game like chess or pingpong. You only have two opponents, A and B. A is better than B. You will play three games. There are only two orders you can play: ABA and BAB. Which gives you a better chance of winning?

`Pa * Pb * Pa > Pb * Pa * Pb <=> Pa * Pb > Pb * Pb <=> Pa > Pb` . Answer: BAB.

Play a 1 vs 1 game. I roll a 6 sided die, if I get a 1 I win, if not you roll. If you get a 6 you win, otherwise I go again… What are my chances of winning and what are yours?

`E = 1/6 + (5/6) * (5/6) * E => E = 54%` .

Normal 52 card deck. Cards are dealt one-by-one. You get to say when to stop. After you say stop you win a dollar if the next card is red, lose a dollar if the next is black. Assuming you use the optimal stopping strategy, how much would you be willing to pay to play? Proof?

There is no strategy with an edge. Examples:

Assume there is a diagnostic drug for detecting a certain cancer. It is 99% sensitive and 99% specific. 0.5% of the population has this cancer. What is the probability that a randomly selected person from the population has this cancer given that you diagnose them using the drug and it comes back positive?

`(0.005 * 0.99) / (0.005 * 0.99 + 0.995 * 0.01) = 33%` .

You have 3 pancakes in a stack. 1 is burned on both sides, 1 burned on 1 side, 1 burned on no sides. What is P(burned on other side | burned on the top)?

`1 / (1 + 0.5) = 66%` .

Roll a die until the first 6. What’s the expected number of rolls? What’s the expected number of rolls until two sixes in a row? How about a six then a five? Are they different?

`E = p + (1 - p) * (E + 1) => E = 1/p` . Answers: 6, 36, 36.

Say you roll a die, and are given an amount in dollar equal to the number on the die. What would you pay to play this game if you played it a many times in a row? Now say that when you roll the die, you’re allowed to either take the money that you’d get with the roll, or roll a second time; if you roll a second time, you’re obligated to take the number of dollars that you get with the second roll. Now what is the worth of the game? Same thing as above, except you have an option to play the game a third time.

` 1/6 + 2/6 + ... + 6/6 = 21/6 = 3.5` .

With 2, roll a second time if <= 3: `(15*6 + 3*21)/36 = 25.5/6 = 4.25` .

With 3, roll a second time if <= 4, and a third time if <= 3: `(11 * 6 + 4 * 25.5)/36 = 28/6 = 4.66` .

With 4, do <=4, <=4, <=3: ` (11 * 6 + 4 * 28)/36 = 29.66/6 = 4.94` .

With 5, do 4, 4, 4, 3: `(11 * 6 + 4 * 29.66)/36 = 30.77/6 = 5.12` .

With 6, do 5, 4, 4, 4, 3: `(6 * 6 + 5 * 30.77)/36 = 31.64/6 = 5.27` .

You are trying to determine the price a casino should charge to play a dice game. The player rolls a die and gets paid the amount on the face, however he can choose to re-roll the dice, giving up the chance to take the first payout amount before seeing the second result. Similarly he has the same option on the second roll, but after the second re-roll, he must keep the amount shown the third time. How much should the casino charge to break even in expectation on this game assuming the player chooses the best strategy?

Same answer as the previous question.

Let’s say you’re playing a two-player game where you take turns flipping a coin and whoever flips heads first wins. If the winner gets 1 dollar, how much would you pay to go first instead of second?

`E = 0.5 + 0.5 * 0.5 * E => E = 2/3 = 66%` .

`0.66 * (1 - c) - 0.33 * c > 0.33 => 0.66 - c - 0.33 > 0 => c < 0.33` .

Two fair coins are flipped behind a curtain. You are told at least one came up heads. Given that information and nothing else, what is the probability that both landed heads?

33%. HH, HT, TH.

You have 5 quarters on the table in front of you: four fair (regular two-sided coins) and one double-sided (both sides are heads). You pick one of them up at random, flip it five times, and get heads each time. Given this information, what is the probability that you picked up the double-sided quarter?

`(0.2 * 1) / (0.2 * 1 + 0.8 * 0.5 ^ 5) = 88%` .

Mental Math

Answer as quickly as possible.

`7^3`

`7^3 = 49 * 7 = 350 - 7 = 343` .

15% of 165

`0.15 * 165 = 16.5 + 16.5/2 = 24.75` .

one million minus 1011

998989.

54% of 123

`0.54 * 123 = 61.5 + 6.15 - 1.23 = 66.42` .

`55^2`

`55^2 = 550 * 5 + 55 * 5 = 2500 + 250 + 250 + 25 = 3025` .

Math and Logic

A girl is swimming in the middle of a perfectly circular lake. A wolf is running at the edge of the lake waiting for the girl. The wolf is within a fence surrounding the lake, but it cannot get out of the fence. The girl can climb over the fence. However if the wolf is at the edge of the lake where the girl touches it, then it will eat her. The wolf runs 2 times faster than the girl can swim. Assume the wolf always runs toward the closest point on the edge of the lake to where the girl is inside. Can the girl escape? If so, what path should she swim in?

Go to the middle, see where the wolf is, then swim straight in the opposite direction. `2r < pir` .

The hands on a clock cross each other at midnight. What time do they cross each other next?

`m = m / 12 + 5 => m = 60 / 11 = 5.45` . Answer: 1h05m22.5s.

In general: `m = m / 12 + h * 5 => m = 5.45 * h` .

Three people are standing in a circle in a duel. Alan has 100% accuracy, Bob has 66% accuracy, and Carl has 33%. It is a fight to the death – only one person can walk away. They take turns starting with Carl, then Bob, then Alan, and so on. Assume each person plays rationally to maximize their chance of walking away. What is Carl’s action on the first round?

Pass. Then either

So overall, Carl has `0.66 * 0.42 + 0.33 * 0.33 = 38%` chance of winning.

Bad alternatives: if Carl kills Bob, then he gets killed by Alan; if Carl kills Alan, then he has 66% chance of being killed by Bob, and overall `0.33 * 0.42 = 14%` chance of winning.

Alan always kills Bob first. Bob always tries to kill Alan first.

`x^(x^(x^(x^...))) = 2` . What is x?

`x^2 = 2 => x = sqrt(2)` . And it converges. For other numbers it doesn’t converge.

What is `sqrt(2 + sqrt(2 + sqrt(2 + ...)))` ?

`x = sqrt(2 + x) => x^2 = 2 + x => x = 2` .

A line segment is broken into three pieces. What is the probability they form a triangle?

50%. Can’t have a segment larger than 50%.

What is the probability that three points chosen uniformly and independently on a circle fall on a semicircle?

The first 2 points can be anywhere. The 3rd point can’t be in a range of the closest distance in degrees between the first 2 points, in the opposite side.

`sum_(i = 1)^179 x/(360 * 179) = (179 * 180) / (360 * 179 * 2) = 25%` .

We have two concentric circles. A chord of the larger circle is tangent to the smaller circle and has length 8. What’s the area of the annulus – the region between the two circles?

???

There are a cup of milk and a cup of water. Take one teaspoon of milk, put into the water cup; mix well. Take one teaspoon of the mixture in the water cup and put into the milk cup then mix well. Which is higher: the percentage of water in the milk cup or the percentage of milk in the water cup?

Both are the same. For example: `0.9w + 0.1m - 0.01m - 0.09w = 0.81w + 0.09m` and `0.9m - 0.1m + 0.01m + 0.09w = 0.81m + 0.09w` .

Two trains are 30 miles apart and are on track for a head-on collision – one train is going at 20 miles per hour and the other is going at 40 miles per hour. If there is a bird flying back and forth between the fronts of the two trains at 10 miles per hour, what is the total distance the bird will travel before the trains hit?

`30 / (20 + 40) = 0.5` hours. `0.5 * 10 = 5` miles. Note that the bird is slower than both trains.

A 10-by-10-by-10 cube constructed from 1-by-1-by-1 cubes falls into a bucket of paint. How many little cubes have at least one face with paint on it?

`10 * 10 * 10 - 8 * 8 * 8 = 488` .

`8 * 8 * 6 + 8 * 4 * 2 + 8 * 4 + 4 * 2 = 488` .

You have an unsorted array of the numbers 1 to 50 in a random order. Let’s say one of the numbers is somehow missing. Write an efficient algorithm to figure which is missing.

`(50 * 51) / 2` minus the sum of the array.

What is `(1 + 1/n)^n` as `n -> infty` .

`e` .

The number of lily pads on a pond doubles each minute. If there is 1 lily pad initially at time t = 0, therefore 2 at t = 1, 4 at t = 3, 8 at t = 4, etc and the pond is totally covered at time t = 60, then how much of the pond’s surface is still visible at time t = 58?

`1 - 1/2^2 = 75%` .

How can a cheesecake be cut three times to get eight equal slices?

Vertical, horizontal, then align the pieces and finally diagonal.

The airplane passengers problem: say you have 100 passengers boarding a plane with 100 seats. The first person to board is a weird old lady who, instead of going to her own seat, seats in one of the seats uniformly at random (she could pick her own, but she could also pick someone else’s seat). From then on, when a person boards, they’ll sit in their own seat if it’s available, and if their seat is taken by someone, they’ll pick one of the remaining seats uniformly at random and sit there. What is the probability that the last person sits in his/her own seat?

When someone sits at the place of the old lady, everyone after that sits on their place.

`E(100) = 1/100 + (E(99))/100 + (E(98))/100 + ... + (E(2))/100` .

`E(n) = 1/n + (E(n-1))/n + (E(n-2))/n + ... + (E(2))/n` .

`E(2) = 1/2` .

`E(3) = 1/3 + (E(2))/3 = 1/3 + 1/6 = 1/2` .

`E(4) = 1/4 + (E(3))/4 + (E(2))/4 = 1/4 + 1/8 + 1/8 = 1/2` .

`E(5) = 1/5 + (E(4))/5 + (E(3))/5 + (E(2))/5 = 1/5 + 1/10 + 1/10 + 1/10 = 1/2` .

`...`

`E(100) = 1/2 = 50%` .

A company has a value V which is uniformly distributed between 0 and 1. You are planning to place a bid B for the company. If B is smaller than V, then your bid loses and you get nothing; if B is larger than V, you get to purchase the company at price B, and the company will end up being worth 1.5 * V. What price B should you bid to maximize your profit?

Expected value: `int_(0)^B kV dv = kB^2/2` .

Expected profit: `kB^2/2 - B` .

If V grows more than 100%, then buy all, else buy nothing.

On a sheet of paper, you have 100 statements written down. the first says, “at most 0 of these 100 statements are true.” The second says, “at most 1 of these 100 statements are true.” … The nth says, “at most (n-1) of these 100 statements are true.” … the 100th says, “at most 99 of these statements are true.” How many of the statements are true?

`0 => 100 => 1 => 99 => 2 => 98 => ... => 50` .

The first 50 statements are false (from 0 to 49), the next 50 statements are true (from 50 to 99).

You and your spouse host a party with eight other couples. At the beginning of the party, people proceed to shake the hands of those they know. No one shakes their own hand or their spouse’s hand. After this shaking of hands is done, you take a survey of how many hands each person shook, and it turns out that excluding yourself, the numbers of hands shook by everyone else are distinct—that is, no one shook the same number of hands as anyone else. How many hands did your spouse shake?

0 and 6, 1 and 5, 2 and 4, 3 and 3. Answer: 3.

You have two decks of cards: one has 13 reds and 13 blacks, and the other has 26 reds and 26 blacks. We play a game in which you select one of the two decks, and pick two cards from it; you win the game if you select two black cards. Which deck should you select to maximize your chances of winning? Try to do this problem in your head, without writing any calculations down.

`(n - 1)/(2n - 1)` , bigger deck is better.

You have a deck of 52 cards, and you keep taking pairs of cards out of the deck. If a pair of cards are both red, then you win that pair; if a pair of cards are both black, then I win that pair; if a pair of cards has one red and one black, then it’s discarded. If, after going through the whole deck, you have more pairs than I do, then you win 1 dollar, and if I have more pairs than you do, I win 1 dollar. What is the value of this game in the long run?

  1. It is symmetrical.