Блог пользователя chari407

Автор chari407, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone please answer??

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.