Linearity of Expectation : WTF

Revision en1, by fugazi, 2019-07-29 16:09:17

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 : hmm, what about considering each position, 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]

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)