33
$\begingroup$
  1. Probability of raining today is 60%.
  2. If it rains today, the probability of raining tomorrow will increase by 10%.
  3. If it doesn't rain today, the probability raining tomorrow will decrease by 10%.

Rule 2 and 3 can be applied to future days.

What is the probability that eventually, it will rain forever?

(I tried using binomial option pricing model but couldn't solve it because the probability isn't fixed. I saw this question in Chinese as an interview question for a quant position. I couldn't find an answer online. So please help me smart people!)

$\endgroup$
  • 5
    $\begingroup$ So, just to clarify, if the probability of raining ever hits $100$ percent, it will rain forever, right? $\endgroup$ – Brian Tung Feb 2 '17 at 22:07
  • 19
    $\begingroup$ What is meant by "will increase by $10 \% $"? Is it $p \mapsto p +0.1$, or $p \mapsto 1.1p$? The same for "decrease". $\endgroup$ – Crostul Feb 2 '17 at 22:12
  • 2
    $\begingroup$ We have a Markov chain (en.wikipedia.org/wiki/Markov_chain) with few states (two of them being absorbing), so we just have to compute the inverse of a simple matrix to get the answer. $\endgroup$ – Jack D'Aurizio Feb 2 '17 at 22:17
  • 2
    $\begingroup$ This problem can be solved by using a Markov chain, and computing a hitting time. $\endgroup$ – Crostul Feb 2 '17 at 22:17
  • 7
    $\begingroup$ What happens if $p$ is already more than $0.9$, then? Is the probability of rain tomorrow then more than $1$? $\endgroup$ – Henning Makholm Feb 3 '17 at 9:26
23
$\begingroup$

Interesting problem! These are simply the partial sums of rows of Pascal's triangle. So in this case, the answer is just the sum of the first six elements of the $n = 9$ row (divided by $2^9 = 512$):

$$ p_6 = \frac{1+9+36+84+126+126}{2^9} = \frac{382}{512} = \frac{191}{256} $$

Here's how this comes about: There are only two possible final states: certain drought, and certain rain. For any $k, 0 \leq k \leq 10$, let $p_k$ be the probability that the final state will be certain rain, given that the initial probability of rain is $\frac{k}{10}$. (Here, initial only means "current" since the process is homogeneous in time.)

Then, there is a simple set of linear equations relating the $p_k$. Suppose $k = 1$ initially. That is, the current rain probability is $\frac{1}{10}$. Then with probability $\frac{1}{10}$, the next rain probability will be $\frac{2}{10}$, and with probability $\frac{9}{10}$, the next rain probability will be $0$ (and the final state is certain drought). We can represent this as follows:

$$ p_1 = \frac{1}{10} p_2 + \frac{9}{10} p_0 $$

where $p_0 = 0$, naturally.

Now, let us suppose that $k = 2$ initially. Then with probability $\frac{2}{10}$, the next rain probability will be $\frac{3}{10}$, and with probability $\frac{8}{10}$, the next rain probability will be $\frac{1}{10}$. We can represent this as follows:

$$ p_2 = \frac{2}{10} p_3 + \frac{8}{10} p_1 $$

Proceeding along these lines, we can write equations of the form

$$ p_k = \frac{k}{10} p_{k+1} + \frac{10-k}{10} p_{k-1} \qquad 1 \leq k \leq 9 $$

with boundary conditions $p_0 = 0, p_{10} = 1$.


Now, interestingly, because for any $k$ the coefficients of $p_{k-1}$ and $p_{k+1}$ sum to $1$, we can view each of the $p_k$ as a weighted mean of $p_{k-1}$ and $p_{k+1}$. That is to say,

  • $p_0 = 0$
  • $p_1$ is $\frac{1}{10}$ of the way from $p_0$ to $p_2$
  • $p_2$ is $\frac{2}{10}$ of the way from $p_1$ to $p_3$
  • $p_3$ is $\frac{3}{10}$ of the way from $p_2$ to $p_4$

and so on. This permits us to find $p_2$ in terms of $p_1$, $p_3$ in terms of $p_2$, etc. In particular, if we let $p_1 = q$, where $q$ is some quantity currently unknown, then

$$ p_2-p_1 = \frac{9}{1} (p_1-p_0) = \frac{9}{1}q $$ $$ p_3-p_2 = \frac{8}{2} (p_2-p_1) = \frac{9 \times 8}{2 \times 1}q $$ $$ p_4-p_3 = \frac{7}{3} (p_3-p_2) = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} q $$

and for any $k$,

$$ p_{k+1}-p_k = \binom{9}{k} q $$

And since

$$ \sum_{k=0}^9 p_{k+1}-p_k = p_{10}-p_0 = 1 $$

it must therefore be the case that $q = \frac{1}{2^9}$, and

$$ p_k = \frac{1}{2^9} \sum_{i=0}^{k-1} \binom{9}{i} $$

So your intuition that the binomial coefficients were involved was not far off; it's just that they represent not the actual probabilities themselves, but their first differences. An obvious generalization of this yields a similar expression when the probability of rain is $\frac{k}{n}$, with increments of size $\frac{1}{n}$:

$$ p_k = \frac{1}{2^{n-1}} \sum_{i=0}^{k-1} \binom{n-1}{i} $$

Alas, this question suggests that no further simplification is likely for general $k$ and $n$. (Obviously, closed forms for some special cases may be obtained.)


ETA: The relatively simple form of the answer makes me wonder if there is a cleverer answer that relies on some analogy between selecting no more than $k$ of $n$ objects and the probability of certain rain starting with a rain probability of $\frac{k}{n}$. But I confess nothing quickly comes to mind.

$\endgroup$
  • $\begingroup$ Why is there only two results (certain drought and certain rain)? Why can't it be alternation between rain and no rain? $\endgroup$ – Leslie Sun Feb 2 '17 at 23:40
  • 1
    $\begingroup$ @LeslieSun: You have $2$ absorbing states while from the other $9$ states you can reach any of the $11$ possible states with positive probability. So an eventual absorption has probability $1$; there are no other stable distributions $\endgroup$ – Henry Feb 2 '17 at 23:45
  • $\begingroup$ @Henry I see. Thank you! $\endgroup$ – Leslie Sun Feb 3 '17 at 0:17
  • $\begingroup$ @BrianTung: Nice answer, nice explanation! (+1) $\endgroup$ – Markus Scheuer Feb 3 '17 at 18:24
1
$\begingroup$

[nvm, wrong answer. There should be only 2 states.]


I just came up with a way to solve it. Correct me if I'm wrong.

I'll denote rain days as R, and no rain days as N,

There are three possible results: eternal R, eternal N, alternating between R&N.

  1. By drawing a binary tree, I observed that to reach eternal R, we need 4 days of R + n days of R + n days of N, meaning 4R+n(N+R). (n can be any non-negative integer and can be infinitely large.)

    The change in probability caused by 1N and 1R cancel each other (+10%-10% = 0).

    For that 4 days of R, regardless of their order or whether they are consecutive or not, the probabilities of the 4R are 0.6, 0.7, 0.8, and 0.9.

    Thus the probability of eternal R is 0.6*0.7*0.8*0.9*P(n(N+R) with all possible n's)

  2. Same rule applies to N days. To reach eternal N, we need 6 days of N + n days of R + n days of N, meaning 6N+n(N+R).

    Same here, for that 6 days of N, the probabilities of the 6N are 0.4, 0.5, 0.6, 0.7, 0.8, and 0.9.

    Thus the probability of eternal N is 0.4*0.5*0.6*0.7*0.8*0.9*P(n(N+R) with all possible n's)

(From this point, I will denote P(n(N+R) with all possible n's) as P.

  1. For the alternating state, we have 9 sub-states: nNR, R+nNR, 2R+nNR, 3R+nNR, N+nNR, 2N+nNR, 3N+nNR, 4N+nNR, 5N+nNR

    Respectively, the probabilities are P, 0.6*P, 0.6*0.7*P, 0.6*0.7*0.8*P, 0.4*P, 0.4*0.5*P, 0.4*0.5*0.6*P, 0.4*0.5*0.6*0.7*P, 0.4*0.5*0.6*0.7*0.8*P

Adding the probability of all three states, we should get 1. Thus we can solve for P = 625/2017

Thus probability of eternal R = 0.6*0.7*0.8*0.9*P = 189/2017

(The assumption here is that because we are summing the probability for all possible n, from 0 to infinity, I assumed that P stays the same for all three states.)

$\endgroup$
0
$\begingroup$

We can model this situation with markov chains

let the following be the first step transition matrix where each state is the probability of rain that day divided by 10

     0   1   2   3   4   5   6   7   8   9  10
_____________________________________________
0 |  1   0   0   0   0   0   0   0   0   0   0
1 | .9   0  .1   0   0   0   0   0   0   0   0  
2 |  0  .8   0  .2   0   0   0   0   0   0   0
3 |  0   0  .7   0  .3   0   0   0   0   0   0
4 |  0   0   0  .6   0  .4   0   0   0   0   0
5 |  0   0   0   0  .5   0  .5   0   0   0   0  
6 |  0   0   0   0   0  .4   0  .6   0   0   0
7 |  0   0   0   0   0   0  .3   0  .7   0   0
8 |  0   0   0   0   0   0   0  .2   0  .8   0
9 |  0   0   0   0   0   0   0   0  .1   0  .9
10|  0   0   0   0   0   0   0   0   0   0   1

We then create a system of linear equations where the probability of being absorbed into state 10 given that you started from state i is $$ ui = \sum Pij*uj $$ where Pij is the probability of going from state i to state j .

Now since if we start in state 5, the probability of going in either direction is .5, we know that the probability of being aborbed into 0 or 10 will be .5 because of the symmetry of the probabilities.

We then create the following system: $$u5 = .5$$ $$u10 = 1$$ $$u9 = .9 + .1 \cdot u8$$ $$u8 = .8 \cdot (.9 + .1 \cdot u8) + .2 \cdot u7 = \frac{(.72 + .2 \cdot u7)}{.92} = .7826 + .2174 \cdot u7$$ $$u7 = .7 \cdot (.7826 + .2174u7) + .3 \cdot u6 = \frac{(.5478 + .3 \cdot u6)}{.8478} = .6461 + .3539 \cdot u6$$ $$u6 = .6 \cdot (.6461 + .3539 \cdot u6) + .4 \cdot u5 = \frac{(.38766 + .2)}{.78766} = \frac{191}{256} \approx .7461$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.