Expected number of swaps in bubble sort Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i &lt; n$. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

I've tried the following:


The probability for an element $A[i] &gt; A[j]$ for $i &lt; j$ can be calculated easily from the given probabilities.
Using the above, I have calculated the expected number of swaps as:

double ans = 0.0;
for ( int i = 0; i &lt; N-1; i++ ){
    for ( int j = i+1; j &lt; N; j++ ) {
        ans += get_prob(A[i], A[j]); // Computes the probability of A[i]&gt;A[j] for i &lt; j.



Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number $A[i]$ will be swapped with a number $A[j]$.

Note that the initial array elements can be in any order, sorted or unsorted. Then each number can change with some probability. After this I have to calculate the expected number of swaps.

I have posted a similar question before but it did not had all the constraints.

I did not get any good hints on whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.
Let $\sf{Bubble Sort}$ be defined as the following:

for (j = A.length; j &gt; 1; j--)
    for (i = 0; i &lt; j - 1; i++)
        if (A[i] &gt; A[i + 1])
            swap(i, i + 1, A)


Given some permutation $x_1, \cdots, x_n$, an inversion is said to have occurred if $x_j &lt; x_i$ for some $i &lt; j.$ We see that $\sf{Bubble Sort}$ performs an inversion check for each pair, and if so, performs a swap. Let $X$ be the number of swaps. It is not hard to see in the worst case there are $X = \binom{n}{2}$ possible swaps made. But we are interested in the expected case, which we can compute by defining $X$ in terms of inversions in $\sf{Bubble Sort}$.

Now let $X = \sum_j \sum_{i&lt;j} I_{ij}$ where $I_{ij}$ is the indicator variable that there exists an inversion for some pair $(i,j)$. The expectation is defined as $E[X] = E[\sum_j \sum_{i&lt;j} I_{ij}] = \sum_j \sum_{i&lt;j} E[I_{ij}]$. We now need to determine $P\{I_{ij}\}$.

When assuming any possible permutation as input, each with uniform probability, it can been shown that $P\{I_{ij}\} = \frac{1}{2}$. The reasoning behind this is that under any possible permutation, half of the time $x_j &lt; x_i$ and half of the time $x_i &lt; x_j$ for $i \neq j$.

Returning to our expectation calculation we see that $E[X] = \sum_j \sum_{i&lt;j}E[I_{ij}] = \sum_j \sum_{i&lt;j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$