zzzz-'s blog

By zzzz-, history, 5 years ago,

We all know what a permutation is. So, I remember a good problem from school. Let P be a permutation of 1, 2, 3, .... n. We define the function f(P) as the number of positions where P[i] = i (also known as fixed points I think). What is the expect value of f :)

• +11

 » 5 years ago, # | ← Rev. 7 →   +9 I think there is a O(n) solution using dp, let dp[i]: number of ways that i numbers can arrangue that there isn't a p[j]=j, then your answer is $\sum\limits_{i=2}^{n} (n-i)*dp[i]*comb(n, i)/n! + 1/n!$, and $dp[i]=(i-1)*(dp[i-1]+dp[i-2]), 2 \leq i$
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 As much as I remember there is also an O(1) solution, good dp :O
 » 5 years ago, # |   +14 Let p(i) be the probability that i is a fixed point, then p = (n-1)!/n!. Using linearity of expectation, f(P) = sum of p(i)*1 = |P| * 1/|P| = 1
•  » » 5 years ago, # ^ |   +5 Nice :)
•  » » 5 years ago, # ^ |   0 I know this works but this feels so unnatural to me. It really feels like $E[X + Y] = E[X] + E[Y]$ should only work if $X$ and $Y$ are "independent" (in some sense). Abstractly not so much, but looking at this problem it just seems so weird like, that can't possibly be true.
•  » » » 5 years ago, # ^ |   +1 Not really. Expected of sum is sum of expected even if the random variables are not independent. This is used really often in problems, where you "break" the expected into a sum of dependent but computable sub-problems. I think that what you meant is that E(X and Y) = E(X) * E(Y) only and only if X and Y are independent probabilities. Check this for more info
•  » » » » 5 years ago, # ^ |   +4 No, I'm very well aware of how elementary probability theory works.All I'm saying is that intuitively, it does feel wrong.
•  » » » » » 4 years ago, # ^ |   0 When intuition gives incorrect answers, should we continue to trust it? or is there some way to fix intuition so that non-intuitive facts are intuitive?
•  » » » » » » 4 years ago, # ^ |   0 Yes, if you work on something, solve problems etc for a while, your intuition will develop and correct its own mistakes.
 » 4 years ago, # |   -105 ban