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.

For 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

Bing Wang · Accepted Answer · 2021-01-30 06:48:25Z

7

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

edited Jan 30, 2021 at 6:48

answered Jan 30, 2021 at 5:46

Bing Wang

1,7181 gold badge10 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

goalie1998 Over a year ago

@AcatAdog very important you understand the theory of conditional probability, not just copy the code.

AcatAdog Over a year ago

@goalie1998 indeed

Bing Wang Over a year ago

@AcatAdog you can use recursion for small problems as a demo. For larger n see my updated

Collectives™ on Stack Overflow

Recursion function to calculate the probability

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related