zzzz-'s blog

Just for fun
By zzzz-, history, 5 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 7   Vote: I like it +9 Vote: I do not like it

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$$$

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    As much as I remember there is also an O(1) solution, good dp :O

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

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

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

    Nice :)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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

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

        No, I'm very well aware of how elementary probability theory works.

        All I'm saying is that intuitively, it does feel wrong.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, if you work on something, solve problems etc for a while, your intuition will develop and correct its own mistakes.

            → Reply
»
4 years ago, # |
  Vote: I like it -105 Vote: I do not like it

ban

→ Reply