Hello,
Suppose we have the permutation of size $$$N$$$ and the numbers in it are divided in two groups, one of size $$$a$$$ and one of size $$$b$$$ = $$$N-a$$$ (for simplicity, let's say the first $$$a$$$ numbers form the first group)
We also have an(empty) array of size $$$N$$$ also divided in two groups one of size $$$c$$$ and one of size $$$d$$$ = $$$N-c$$$ (also for simplicity, let's say the first $$$c$$$ cases form the first group)
If we were to divide the $$$N$$$ numbers(all permutations are equiprobable) in the empty array, I am looking for the expected number of numbers of group a that land in a position of group c.
Turns out this is $$$a*c/N$$$ (from the tutorial of Edu 57 F).
I tried to compute it in many ways and just ended up stuck with lots factorials, N choose Ks and the EV sum; sum of i * (probability that we get i numbers)
So I would very much appreciate any help regarding the intuition behind this and the ways of deriving such EV formulas.
Thank you :)
An object from the first array will land in group 1 in the second array with a probability of $$$c/N$$$. Then using linearity of expectation, we get $$$a*c/N$$$ as the expected number of numbers from group A that land in a position of group C. A way that helps me understand this is by imagining all the possible groups C could be. Let us say that there are $$$k$$$ groups. Then we know that for $$$c/N$$$ of the $$$k$$$ groups, 1 will be in the group. Additionally, for $$$c/N$$$ of the $$$k$$$ groups, 2 will be in the group and so on. So since each number is $$$c*k/N$$$ groups, if we count the number of times a number from group A appears in one of the $$$k$$$ groups we get $$$a*c*k/N$$$. Since expected value is just the average number of occurrences, to find the expected value we just divide by the possibilities, $$$k$$$, giving us $$$(a*c*k/N)/k$$$. This simplifies to the answer of $$$a*c/N$$$.
The way I derive such formulas is by trying to think about each element separately. While sometimes you just have to solve it with all the factorials, many times you can find the answer by just visualizing how the elements move around. A good example of this thinking which I take inspiration from is this comment https://codeforces.net/blog/entry/81565#comment-682030.
Thank you for your response!
I still don't understand how for $$$c/N$$$ of the $$$k$$$ groups, $$$1$$$ will be in the group is true
Can you explain this as well? I thought about it but didn't find why, I know I might be missing some easy transitions
Thank you so much for that comment! that is what I'm looking for
imagine you have placed an element 1 from group A in position 1 of the second array. Now c positions of the second array will be selected as positions of group c. out of these. let the number of ways of choosing a group of c elements out of N be = k. (number of ways of choosing the group C) Now let us see, in what fraction of cases do we get that the position 1 is part of group C. Note that position 1 is no special from any other position. I mean that, if x of the k groups contain position 1, then similarly, x of the k groups will choose position 2, x of the k groups will choose position 3 and so on (where x is a fraction / ratio, which means the actual number of groups is x*k).
Now note that, if x fraction of the k ways of choosing group c, chooses a particular position i. That means in x * k ways a position i is chosen, out of the k ways. (Note, x is a fraction <= 1, so x * k <= k).
Now see, a particular position is chosen in x * k ways. So, if we add this quantity up for each position. (That is let S(i) = sum of ways in which position i is chosen.) We want sum of S(i) for all i. That will just be x * k + x * k + x * k + x* k + ........ N times. That is N * x * k. Let us look at this number in another way. Let us focus on any single one of the k ways in which we choose group C.
Note that, in any way of choosing group C, c positions are chosen, and that means essentially, we are "contributing" a +1 to the S(i) of those positions i, which have been chosen. So, (number of positions chosen in a way of choosing group C) * (ways of choosing group C)
or c * K is simply another way of looking at the number above.
So, sum of S(i) for all i = N * x * k = c * k So x = c / N.
That is c / N of the k ways of choosing group C will result in our position i being chosen!
Hope it is clear. It was a little long.
It is very clear thank you very much!
As you pointed, all the elements should be treated equally but I was worrying about the possible "shapes" of the group C; the different IDs and their orderings, which is irrelevant.
I have no idea how I missed this for so long
The intuition behind that statement is this. Say you are assigning elements from the first array to the second array. We can do it in the order 1 to $$$n$$$. So we first pick where to place 1, then where we place 2 and so on. So when we place 1 its like rolling an $$$n$$$ sided die. If the number we get is from 1 to $$$c$$$ we place it in group 1 of the second array. Otherwise we place it in the second array. So this gives us a probability of $$$c/N$$$ for 1 being in the first group. Now the key observation here is that 1 is not special. If there is a probability of $$$c/N$$$ for 1 being in the first group, 2 should also have a probability of $$$c/N$$$ for being in the first group, so should 3 and so on.
Now after this, since each of the $$$k$$$ possible values of the first group are equiprobable, if 1 has a $$$c/N$$$ probability of being in the first group then $$$c/N$$$ of the $$$k$$$ groups have to have 1 in the first group.
Oh my god it's so clear now at last, the elements should be treated independently and that's how we use the linearity of expectation. I overcomplicated it..
Thank you so much for your time, you helped a lot!
The problem was that I kept thinking about all the possible IDs and orderings of the elements to be put in the A group, but that wasn't necessary since as you said, they are not special.