Tuesday, February 23, 2010

Inversions

Let A[1 .. n] be an array of n distinct numbers. If i <> A[j], then the pair (i, j) is called an inversion of A. Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Compute the expected number of inversions.
Pubblicato da a
Reazioni: 

1 comment:

  1. Is the following solution correct -

    Let Xij be the event that when two distinct random numbers i and j are selected between 1 and n and i <> a[j].
    Probability of occurence of Xij = 1-1/n
    We need to sum this probability over i and j from 1 to n and i<>j

    Does this solution work?

    ReplyDelete

Subscribe to: Post Comments (Atom)