Introduzione agli algoritmi (CLRS) EX 5.2-5 Soluzione

Question

Quello che segue è EX 5.2-5 dall'introduzione agli algoritmi (CLRS), 2a edizione.

Permettere $ A [1 ... n] $ essere un array di n numeri distinti. Se $ i e $ A [i]> a [j] $, quindi la coppia $ (i, j) $ è chiamato inversione di $ A $. Supponiamo che gli elementi di $ A $ formare una permutazione casuale uniforme di $ <1, ..., n> $. Utilizzare le variabili casuali dell'indicatore per calcolare il numero previsto di inversioni.

La soluzione da https://walkcc.github.io/clrs/chap05/5.2/ dice:

Permettere $ X_ {ij} $ essere un indicatore variabile casuale per l'evento in cui la coppia $ A [i], a [j] $ per $ i <j $ è invertito. abbiamo $ Pr {x_ {ij} = 1 } = frac {1} {2} $, perché dati due numeri casuali distinti, la probabilità che il primo sia più grande del secondo $ frac {1} {2} $.

Vorrei chiedere a cosa serve $ Pr {x_ {ij} = 1 } = frac {1} {2} $. So che ci possono essere solo 2 risultati, sia $ X_ {ij} = 1 $ o $ X_ {ij} = 0 $. Anche, $ Pr {x_ {ij} = 1 }+ pr {x_ {ij} = 0 } = 1 $.

Dopo aver guardato la risposta, ha senso, ma vorrei chiedere se esiste un modo più "sistematico" per derivare/giustificare questa probabilità. Nota che sono molto vago sul significato di sistematico perché vorrei semplicemente avere un modo più affidabile di derivare questa probabilità piuttosto che fare affidamento solo sull'intuizione.