Recursion function to calculate the probability

Question

A either catches his bus with probability 1 - p or misses it with probability p. In the former case, he comes to the office on time, in the latter case he is late. A knows that his boss gets angry if A is late two days in a row. For a given number n of days and given p, A wants to compute the probability that after n days his boss will not be angry.

F​or example, if n = 2, then the only way to make the boss angry is two be late both days. Since, events of different days are independent, the probability of this event is p*p = p^2.Therefore, the probability of not making the boss angry is 1 - p^2

def probability_not_angry(n, p):
  if n == 0:
    return 1
  if n == 1:
    return 1
  return probability_not_angry(n-1, p) + probability_not_angry(n-2, p)
  
# should print 0.5
print(probability_not_angry(4, 0.5))
# should print 0.4375
print(probability_not_angry(2, 0.75))

I am not sure how to solve this problem. if return probability_not_angry(n-1, p) + probability_not_angry(n-2, p), it only calculate the n, so i have to change the p in the function, but now sure how to do it.

Thanks

Answer 1

This is basically conditional probability. Think the realizations of your random world as the sequences like CMCCMC.... for Catch/Miss. The Not-Angry means there is no MM in the sequence. Recursive from beginning: if C happens (with prob 1-p), the problem becomes (n-1,p). If MC happens, with probability (1-p)*p, the problems becomes (n-2,p). You do not need consider when MM happens since the conditional probability (of not-angry) is 0.

def probability_not_angry(n, p):
    if n <2:
        return 1
    return (1-p)*probability_not_angry(n-1, p) + p*(1-p)*probability_not_angry(n-2, p)

BTW, the computation complexity of this recursion isn't great even with the right caching. The correct way is to solve it linearly:

def Linear(n,p):
    R=[1,1]
    for _ in range(n-1):
        R.append((1-p)*R[-1]+(1-p)*p*R[-2])
    return R[-1]
print(Linear(4,0.5))
print(Linear(2,0.75))