In the tutorial for this problem, I am confused as to why z[i + 1][j + 1] + = z[i][j] * p
is done? Specifically, why are we multiplying p and (1-p) to the previous probabilities? I am a beginner with probabilities and expected value and I didnt understand why " z[i][j] is multiplied with p " . Please explain in detail. Thank You..!
Can someone please answer??
Number p (0 <= p <= 1) is the probability that ith person will enter the escalator, hence (1-p) is the probability thag ith person wil not enter the escalator. Because of that, from state dp[i][j], we switch to state dp[i+1][j+1] with probability p, and to state dp[i+1][j] with probability (1-p). That's why we add dp[i][j] multiplied by p or (1-p) to dp[i][j].
Let Z(i, j) denote the probability that there are j people on the elevator after i seconds have passed. From a state (i, j), 2 things can happen:
z[i+1][j+1] += z[i][j]*p
z[i+1][j] += z[i][j]*(1-p)
Obviously there is an edge case — a person can't step onto the elevator if there are already n people on it — so take care of that.