# Another IRV question... Inversions

• Feb 24th 2009, 12:58 AM
mander
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 $\displaystyle C_i$ to be 0 ... 2n ?

Then how do I calculated the expected value of $\displaystyle C_i$, would it be $\displaystyle \frac{1}{2n} * n$ to be $\displaystyle \frac {n}{2n}$ reducing to $\displaystyle \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!
• Feb 24th 2009, 10:02 PM
matheagle
It's late and I didn't read everything you wrote, but I do know that.....

$\displaystyle \frac{1}{2n} * n$ equals $\displaystyle \frac {n}{2n}$ reduces to $\displaystyle \frac{1}{2}$
• Feb 25th 2009, 03:49 PM
awkward
Quote:

Originally Posted by mander
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 $\displaystyle C_i$ to be 0 ... 2n ?

Then how do I calculated the expected value of $\displaystyle C_i$, would it be $\displaystyle \frac{1}{2n} * n$ to be $\displaystyle \frac {n}{2n}$ reducing to $\displaystyle \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 $\displaystyle X_{ij} = 1$ if (i,j) is an inversion, 0 otherwise, for $\displaystyle 1 \leq i < j \leq n$. See if you can find $\displaystyle P(X_{ij} = 1)$; this is also $\displaystyle E(X_{ij})$.

The total number of inversions is $\displaystyle \sum_{i < j} X_{ij}$. You want to find its expected value, $\displaystyle E(\sum_{i < j} X_{ij})$. By the theorem on the expected value of a sum, this is equal to $\displaystyle \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.