Preface
My brother was applying for a university. In his entrance exam there was the following question (translation done by me):
John buys 100 shares of a company. He estimates that during one trading day there is a probability of 0.5 that the price of a share raises by \$1 and a probability of 0.5 that it goes down by \$1. Other options are not possible. He has decided to sell the shares as soon as their price at the end of the day is higher than their acquisition price. The costs of buying and selling shares are not taken into account since they are so small they have no notable effect. What is the probability that he sells his shares during the next 5 trading days?
This wasn't very difficult. Both the amount of shares and the value of $1 are completely irrelevant. I simply drew a graph where each node corresponds to the change in value of one share. If the change becomes positive, the money is taken out. Like this:
0 Day 0
/ \
-1 1 Day 1
/ \
-2 0 Day 2
/ \ / \
-3 -1 1 Day 3
/ \ / \
-4 -2 0 Day 4
/ \ / \ / \
-5 -3 -1 1 Day 5
Then I labelled the first two edges having the probabilities 1/2 and the edges after that had half the probability of the edges that lead to them (I couldn't figure out a good way to write the weights to the picture). From there we can count the weights of the edges that lead to 1 and see that the answer to the problem is $1/2+1/8+1/16\approx 0.69$. Now, I started to wonder how to generalize this.
The Problem
John buys 100 shares of a company. He estimates that during one trading day there is a probability of 0.5 that the price of a share raises by \$1 and a probability of 0.5 that it goes down by \$1. Other options are not possible. He has decided to sell the shares as soon as their price at the end of the day is higher than their acquisition price. The costs of buying and selling shares are not taken into account since they are so small they have no notable effect. What is the probability that he sells his shares during the next N trading days?
Attempt at Solution
Firstly, I thought this wouldn't be too difficult. I just figure out the number of paths in the graph that lead to +1 profit at a given level, divide by the total number of paths and sum them together. The problem is that the paths that end up at +1 get cut off. I tried writing all the combinations down like this (0 corresponds to a loss during a day and 1 correponds to gain):
Combinations that lead to net gain after day 7 (not before):
0101011
0100111
0010111
0011011
0001111
The probability of day 7 gain ends up being 5/128 (the numbers start getting more complicated).
There are some obvious things here. All combinations start with 0 and end with 11. But in the middle there still can't be a place where there have been more 1s than 0s so far. I seem to hit a dead end. How is this done?
Best Answer
You're looking for the Catalan numbers. The number of ways to return to $0$ in $2k$ steps without going positive in between is $C_k$. Then (taking into account the probability $\frac12$ for going positive in the next step), the probability of cashing in after exactly $2k+1$ days is
$$\frac12C_k\left(\frac12\right)^{2k}=\frac{2^{-2k-1}}{k+1}\binom{2k}k\;.$$
The first few values for $k=0,1,2,3$ are $\frac12$, $\frac18$, $\frac1{16},\frac5{128}$.
The probability for selling the shares after at most $2n+1$ days is obtained by summing over $k$:
$$ \sum_{k=0}^n\frac{2^{-2k-1}}{k+1}\binom{2k}k=1-2^{-2(n+1)}\binom{2(n+1)}{n+1}\;. $$
The nice form of the result suggests that it could be obtained more elegantly without the summation. The first few values for $n=0,1,2,3$ are $\frac12$, $\frac58$, $\frac{11}{16}$, $\frac{93}{128}$.
From the asymptotic behaviour of the central binomial coefficients we see that the probability of not selling the shares after at most $2n+1$ is asymptotic to $1/\sqrt{\pi n}$.
Here's the more elegant proof that the probability for not selling the shares after at most $2n$ days is $2^{-2n}\binom{2n}n$:
$\binom{2n}n$ is the number of paths that lead to a net zero change in stock price after $2n$ days. These can be placed in one-to-one correspondence with the paths that never go positive for $2n$ days. For a given path with net zero change after $2n$ days, find the maximum stock price it reached, and the first step in which it was reached. Turn that step into a negative step instead. Repeat until you obtain a path that never goes positive. This is a bijection to the paths that never go positive; the inverse is given by reversing the step after the last time the maximum price was reached, until you obtain a path with net zero change.