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).