pronoobchamploser's blog

Linearity of expectation
By pronoobchamploser, history, 4 years ago, In English

I recently started studying expected value and linearity of expectations. After studying some material I came across this problem: https://atcoder.jp/contests/dp/tasks/dp_j

Now, thinking in terms of linearity of expectation, my thought:

E(number of operations to eat N dishes) = E(number of operation to eat a1 dish) + E(number of operation to eat a2 dish) + ...

Then, E(number of operation to eat a1 dish) = a1 * E(number of operation to eat 1 dish)

Then, E(number of operation to eat 1 dish) = 1/n * 1 + (1 — 1/n)*(1/n) * 2 + ... = n

What's wrong with this interpretation? At what step am I misusing the linearity of expectation?

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your first line "E(number of operations to eat N dishes) = E(number of operations to eat the a1 dish) + E(number of operations to eat the a2 dish) + ..." is incorrect.

The main problem is that (number of operations to eat N dishes) != (number of operations to eat the a1 dish) + (number of operations to eat the a2 dish) + ... since the summands on the RHS kinda "overlap"

For example, consider the case n = 2, a1 = 1, a2 = 1. If you ate the a1 dish, and then the a2 dish, then the number of operations for eating both dishes would be 1 and 2, respectively. The total number of operations, 2, is not equal to 1 + 2.

I'm pretty sure the intended solution involves storing a 3D dp where states are represented by the number of plates with 1, 2, and 3 pieces left (hence the DP theme), but you should check for yourself lol

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

    I meant

    E(number of operations to eat N dishes) = E(number of operation to eat a1 dish) + E(number of operation to eat a2 dish) + ...

    and not

    (number of operations to eat N dishes) != (number of operations to eat the a1 dish) + (number of operations to eat the a2 dish) + ... since the summands on the RHS kinda "overlap"

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

      lmao, what's the difference between "number of operation to eat a1 dish" and "number of operations to eat the a1 dish"?

      my point is that the random variable on the LHS isn't equal to the sum of the random variables on the RHS, and therefore you can't apply E(X + Y) = E(X) + E(Y)

      → Reply