An orangutan starts at position , and in every second moves either up or to the right, both with probability . Whatβs the expected number of seconds until the orangutan hits either or ?
Solution
Letβs let the process continue for infinite time, and let and denote the times at which the orangutan hits the lines and respectively. Then, we wish to find .
However, letβs instead rewrite as . Why? We want to take advantage of the nice fact that after seconds, weβre guaranteed to have already hit either or . However, we also know that we canβt have already hit both prior to these seconds: that is, . So, if we let denote our coordinates after seconds, we have that .
Plugging that back in, we get that
Isnβt that quite an incredible result?
To finish from here, notice that is equivalent to randomly dividing elements into 2 subsets, then finding the expected number of elements in the smaller subset. If both subsets have size , we define the smaller one to be the one containing (although any method of tie-breaking works). For instance, if , here are some possible splits and their corresponding contributions, with the smaller subset listed first in each split:
To elegantly evaluate this expected value, we can switch order of summation. That is, for each of the elements, sum the probability that it is in the smaller subset. Actually, this is not very nice since our current definition of βsmallerβ lacks symmetry when both subsets have size , so instead, we will sum the probability that each element is in a subset with size , then subtract off the case afterward.
This is now much cleaner, since we can pretty easily show that , where is the subset containing .
Therefore, our overall expectation is:
Our final answer is then simply twice this quantity, i.e.