fugazi's blog

Linearity of Expectation : WTF
By fugazi, history, 5 years ago, In English

My friend gave me a problem, which can be reduced to the following.

Let $$$S(k)$$$ be the set of all arrays of size $$$n$$$ that contains $$$k$$$ ones and $$$n - k $$$ zeroes. Let for some array $$$s \in S(k)$$$ , $$$pos_s[1..k]$$$ denotes the position of those ones (say in increasing order, it doesn't matter actually). We have to calculate.

$$$ \sum_{s \in S(k)} {\sum_{i = 1}^{k} pos_s[i] } $$$

i.e, for all arrays $$$s \in S(k)$$$ we have to sum the positions of all $$$k$$$ ones.

My thoughts : Modification to binomial expansion? Noo. hmm, what about counting how many times each position occurs, but then there will be intersections, like I might put two ones at the same index, so ? what about inclusion-exclusion? No it's getting a lot messy.

Linearity of Expectation : Let's find the expected value of $$$ \sum_{i = 1}^{k} pos_s[i] $$$

$$$ E[\sum_{i = 1}^{k} pos_s[i]]$$$

Let's look at it it some other way. We choose random variables $$$X_{1, 2, .. k} $$$ lying in $$$[1, n]$$$ with same probability (Note that I'm not saying they're independent. ). Thus $$$E[X_i] = \frac{1 + 2 + .. n}{n} = \frac{n + 1}{2}$$$ Now by linearity of expectation,

$$$ E[\sum_{i = 1}^{k} X_i] = \sum_{i = 1}^{k} E[X_i] = \sum_{i = 1}^{k} \frac{n + 1}{2} = \frac{k(n + 1)}{2}$$$

.

Now, it's left to you to realise that

$$$ E[\sum_{i = 1}^{k} pos_s[i] = E[\sum_{i = 1}^{k} X_i] $$$

.

And since we've $$$n \choose k $$$ arrays possible, we deduce,

$$$ \sum_{s \in S(k)} {\sum_{i = 1}^{k} pos_s[i] }= \frac{{n \choose k} k (n + 1)}{2}$$$

.

I went numb for a few seconds after completing the solution, I mean wtf, what about intersection, how can this be even possible, you can't just choose it randomly (I know the formal proof of LOE, but still :\ )

There are few things, that I know are true, but I can never digest them, "My favourite song has just 7 million views on youtube" is on second", "Linearity of expectation actually works" remains at first.

Maybe I overkilled it. Other easier solutions are welcome :)

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

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

The answer is a big sum like $$$(1 + 3 + 4) + (2 + 5) + \ldots $$$ where e.g. the first term denotes a sequence with ones at position 1, 3 and 4. You can easily count how many times each number will appear in this big sum and thus how many times it should be counted. I think about it as contribution to the answer. More in my blog.

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

hmm, what about counting how many times each position occurs, but then there will be intersections

No, there won't be. It just works fine.

→ Reply