When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Rajan_sust's blog

By Rajan_sust, history, 5 years ago, In English

Let, x1 <  = x2 <  = x3....... <  = xn

and

p1 + p2 + p3 + ....... + pn = 1

We all know that average of x1, x2, x3......., xn is in [x1,xn] and it is easy to understand.

In a contest, I assumed Expected value = p1 * x1 + p2 * x2 + p3 * x3 + ....... + pn * xn is in [x1,xn] regardless how probability is distributed that means the sum of probability can be 1 in many different ways.

My assumption was right and got ac. I'm interested to know the proof.

TIA

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

The sum will be minimal if p1 = 1, because otherwise we can make p1 = 1 with moves which don't increase the value of the sum. Take some non-0 pi (i > 1) and add pi to p1 and make pi 0. This way the sum will change by  - pixi + pix1. Because x1 <  = xi this move will not increase the sum, the minimum is if p1 = 1, but then clearly the sum is at least x1. Same proof can be given for the fact that xn is the maximum.

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

    Same thing, but a bit more intuitive for me so I'll share it:

    p1x1 + p2x2 + ... + pnxn ≥ p1x1 + p2x1 + ... + pnx1 = x1, since for each i, xi ≥ x1. Similarly, p1x1 + p2x2 + ... + pnxn ≤ p1xn + p2xn + ... + pnxn = xn, so you have both bounds.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A small thing about your notation, what you are writing doesn't really make sense, but I think I understand what you are asking about.

There is a simple argument why the expected value is in [x1, xn]. Simply note the following

x1 = p1x1 + p2x1 + ... + pnx1 ≤ p1x1 + p2x2 + ... + pnxn ≤ p1xn + p2xn + ... + pnxn = xn.