Linearity of Expectation : WTF

Revision en3, by fugazi, 2019-07-29 17:44:59

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 :)

Tags linearity of expectation, #probabilities, mindfuck

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English fugazi 2019-07-29 17:44:59 16
en2 English fugazi 2019-07-29 17:10:51 1236 Tiny change: '{n + 1}{2}Now by lin' -> '{n + 1}{2}$ Now by lin' (published)
en1 English fugazi 2019-07-29 16:09:17 832 Initial revision (saved to drafts)