Results 1 to 3 of 3

Math Help - Another IRV question... Inversions

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    27

    Red face Another IRV question... Inversions

    Hey guys. I have another question regarding IRV. I did several of them between this question and the last I posted, but this one is confusing to me.

    Here's the question:
    Let A[1 ... n] be an array of n distinct numbers.
    If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A.
    Suppose that each element of A is chosen uniformly at random from the range 1 through n.
    Use indicator random variables to compute the expected number of inversions.

    Ok, so I did some trial and error and I think the maximum number of inversions (I understand the whole inversion explanation) is 2n. I didn't try it to very high numbers though... So I'm not entirely confident on that.

    Now, do I want to set up my C_i to be 0 ... 2n ?

    Then how do I calculated the expected value of C_i, would it be \frac{1}{2n} * n to be  \frac {n}{2n} reducing to \frac{1}{n} ? I'm trying to do this by... Possibility * Probability.

    But now I think I may have mixed this whole thing up so any help is really appreciated. We only had the one lecture ("crash course") on this, so I'm a bit overwhelmed, honestly. Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor matheagle's Avatar
    Joined
    Feb 2009
    Posts
    2,763
    Thanks
    5
    It's late and I didn't read everything you wrote, but I do know that.....

    \frac{1}{2n} * n equals  \frac {n}{2n} reduces to \frac{1}{2}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mander View Post
    Hey guys. I have another question regarding IRV. I did several of them between this question and the last I posted, but this one is confusing to me.

    Here's the question:
    Let A[1 ... n] be an array of n distinct numbers.
    If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A.
    Suppose that each element of A is chosen uniformly at random from the range 1 through n.
    Use indicator random variables to compute the expected number of inversions.

    Ok, so I did some trial and error and I think the maximum number of inversions (I understand the whole inversion explanation) is 2n. I didn't try it to very high numbers though... So I'm not entirely confident on that.

    Now, do I want to set up my C_i to be 0 ... 2n ?

    Then how do I calculated the expected value of C_i, would it be \frac{1}{2n} * n to be  \frac {n}{2n} reducing to \frac{1}{n} ? I'm trying to do this by... Possibility * Probability.

    But now I think I may have mixed this whole thing up so any help is really appreciated. We only had the one lecture ("crash course") on this, so I'm a bit overwhelmed, honestly. Thank you!
    Mander,

    What has the max number of inversions got to do with the problem?

    Here is a hint.

    Define X_{ij} = 1 if (i,j) is an inversion, 0 otherwise, for 1 \leq i < j \leq n. See if you can find P(X_{ij} = 1); this is also E(X_{ij}).

    The total number of inversions is \sum_{i < j} X_{ij}. You want to find its expected value, E(\sum_{i < j} X_{ij}). By the theorem on the expected value of a sum, this is equal to \sum_{i < j} E(X_{ij}).

    It may help to know the number of pairs (i, j) with i < j; this is just the number of combinations of n objects taken 2 at a time.

    Go for it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of inversions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 14th 2010, 12:04 PM
  2. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2010, 02:12 PM
  3. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 02:12 PM
  4. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2008, 01:22 PM
  5. Using MergeSort to count Inversions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 17th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum