chari407's blog

Help needed with 518D
By chari407, history, 6 years ago, In English

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..!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please answer??

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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].

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  1. A person steps onto the elevator. This happens with probability p, and takes us to state (i + 1, j + 1). Hence, Z(i + 1, j + 1) equals p·Z(i, j), plus any other probability being added to it, hence z[i+1][j+1] += z[i][j]*p
  2. A person doesn't step onto the elevator. This happens with probability 1 - p, and takes us to state (i + 1, j). Similar reasoning as above, we have 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.

→ Reply