Il numero previsto di inversioni - Dall'introduzione agli algoritmi di Cormen

Question

Sia A [1 .. n] un array di n numeri distinct. Se io < j e A [i]> A [j], allora la coppia (i, j) è chiamata inversione di A. (Vedi il Problema 2-4 per maggiori informazioni sulle inversioni.) Supponiamo che ogni elemento di A sia scelto in modo casuale, indipendente e uniforme dall'intervallo 1 a n. Utilizzare le variabili casuali dell'indicatore per calcolare il numero previsto di inversioni.

---

Il problema è da esercizio 5,2-5 in Introduzione agli algoritmi da Cormen. Ecco la mia soluzione ricorsiva:

x Supponiamo che (i) è il numero di inversioni in un [1..i], ed E (i) è il valore atteso di x (i), allora E (i +1) può essere calcolato come segue:
Immagine abbiamo i+1 posizioni per posizionare tutti i numeri, se poniamo i + 1 sulla prima posizione, quindi x (i + 1) = i + x (i); se poniamo i + 1 sulla seconda posizione, allora x (i + 1) = i-1 + x (i), ..., quindi E (i + 1) = 1/(i + 1) * sum (k) + E (i), dove k = [0, i]. Finalmente otteniamo E (i + 1) = i/2 + E (i).
Perché sappiamo che E (2) = 0.5, così ricorsivamente otteniamo: E (n) = (n-1 + n-2 + ... + 2)/2 + 0.5 = n * (n-1)/4.

---

Anche se la deduzione di cui sopra sembra essere giusto, ma io non sono ancora molto sicuro di questo. Quindi lo condivido qui.

Se c'è qualcosa che non va, per favore correggimi.

Answer 1

Penso che sia giusto, ma penso che il modo giusto per dimostrarlo è quello di utilizzare le aspettative conditionnal:

per tutti X e Y si ha: E [X] = E [E [X | Y]]

quindi nel tuo caso:

E (i + 1) = E [x (i + 1)] = E [E [x (i + 1) | x (i)]] = E [SUM (k)/(1 + i) + x (i)] = i/2 + E [x (i)] = i/2 + E (i)

la seconda affermazione:

se:

E (n) = n * (n-1)/4.

quindi E (n + 1) = (n + 1) * n/4 = (n-1) * n/4 + 2 * n/4 = (n-1) * n/4 + n/2 = E (n) + n/2

Quindi n * (n-1)/4. verificare la relazione ricorsione per ogni n> = 2 e verifica per n = 2

Così E (n) = n * (n-1)/4

Spero capito il problema e aiuta

Answer 2

Tutte le soluzioni sembrano essere corrette, ma il problema dice che dovremmo usare variabili casuali dell'indicatore. Quindi ecco la mia soluzione usando la stessa:

Let Eij be the event that i < j and A[i] > A[j]. 

    Let Xij = I{Eij} = {1 if (i, j) is an inversion of A 

         0 if (i, j) is not an inversion of A} 

    Let X = Σ(i=1 to n)Σ(j=1 to n)(Xij) = No. of inversions of A. 

    E[X] = E[Σ(i=1 to n)Σ(j=1 to n)(Xij)] 

     = Σ(i=1 to n)Σ(j=1 to n)(E[Xij]) 

     = Σ(i=1 to n)Σ(j=1 to n)(P(Eij)) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(P(Eij)) (as we must have i < j) 

     = Σ(i=1 to n)Σ(j=i + 1 to n)(1/2) (we can choose the two numbers in 
              C(n, 2) ways and arrange them 
              as required. So P(Eij) = C(n, 2)/n(n-1)) 

     = Σ(i=1 to n)((n - i)/2) 

     = n(n - 1)/4 

Answer 3

Un'altra soluzione è ancora più semplice, IMO, anche se non usa "variabili casuali indicatore".

Poiché tutti i numeri sono distinte, ogni coppia di elementi è o un inversione (i < j con A[i] > A[j]) o un non-inversione (i < j con A[i] < A[j]). In altre parole, ogni coppia di numeri è in ordine o fuori servizio.

Quindi, per una determinata permutazione, il numero totale di inversioni più non inversioni è solo il numero totale di coppie o n*(n-1)/2.

Per simmetria di "minore di" e "maggiore di", il numero previsto di inversioni è uguale al numero previsto di non inversioni.

Poiché l'aspettativa della loro somma è n*(n-1)/2 (costante per tutte le permutazioni), e sono uguali, sono ciascuna metà di quello o n*(n-1)/4.

[Update 1]

A quanto pare la mia "simmetria 'meno' e 'maggiore di'" affermazione richiede una certa elaborazione.

Per qualsiasi array di numeri A nel range da 1 a n, definire ~A come la matrice che si ottiene quando si sottrae ogni numero da n+1. Ad esempio, se A è [2,3,1], quindi ~A è [2,1,3].

Ora, osservare che per qualsiasi coppia di numeri in A che sono in ordine, gli elementi corrispondenti di ~A sono fuori servizio. (Facile da mostrare perché la negazione di due numeri scambia il loro ordine.) Questa mappatura mostra esplicitamente la simmetria (dualità) tra meno e più che in questo contesto.

Quindi, per qualsiasi A, il numero di inversioni è uguale al numero di non inversioni in ~A. Ma per ogni possibile A, corrisponde esattamente uno ~A; quando i numeri vengono scelti in modo uniforme, sono ugualmente probabili sia A che ~A. Pertanto il numero previsto di inversioni in A corrisponde al numero previsto di inversioni in ~A, poiché queste aspettative vengono calcolate nello stesso spazio esatto.

Pertanto il numero previsto di inversioni in A corrisponde al numero previsto di non inversioni. La somma di queste aspettative è l'aspettativa della somma, che è la costante n*(n-1)/2 o il numero totale di coppie.

[Update 2]

Una simmetria semplice: Per qualsiasi matrice A di n elementi, definire ~A come gli stessi elementi, ma in ordine inverso. Associare l'elemento nella posizione i in A con l'elemento nella posizione n+1-i in ~A. (Ovvero associare ciascun elemento a se stesso nell'array invertito.)

Ora qualsiasi inversione in A è associata a una non inversione in ~A, proprio come con la costruzione nell'Aggiornamento 1 sopra. Quindi vale lo stesso argomento: il numero di inversioni in A è uguale al numero di inversioni in ~A; sia A che ~A sono egualmente sequenze probabili; eccetera.

Il punto dell'intuizione è che gli operatori "minore di" e "maggiore di" sono solo immagini speculari l'uno dell'altro, che è possibile vedere negando gli argomenti (come nell'aggiornamento 1) o scambiandoli (come nell'aggiornamento 2). Quindi il numero previsto di inversioni e non inversioni è lo stesso, dal momento che non si può sapere se si sta guardando un particolare array attraverso un mirror o meno.

Answer 4

utilizzando l'indicatore variabili aleatorie:

1. Sia X = variabile casuale che è uguale al numero di inversioni.
2. Lascia Xij = 1 se A [i] e A [j] formano una coppia di inversione e Xij = 0 altrimenti.
3. Numero di coppie di inversione = Somma oltre 1 < = i < j < = n di (Xij)
4. Ora P [Xij = 1] = P [A [i]> A [j]] = (n scelgo 2)/(2! * N scegli 2) = 1/2
5. E [X] = E [somma su tutte le coppie ij tali che io < j di Xij] = somma su tutte le coppie ij tale che io < j di E [Xij] = n (n - 1)/4

Answer 5

Ancora più semplice (simile alla risposta di Aman sopra, ma forse più chiaro) ...

Let Xij be a random variable with Xij=1 if A[i] > A[j] and Xij=0 otherwise. 
Let X=sum(Xij) over i, j where i < j 

Number of pairs (ij)*:    n(n-1)/2 
Probability that Xij=1 (Pr(Xij=1))): 1/2 
By linearity of expectation**:  E(X) = E(sum(Xij)) 
              = sum(E(Xij)) 
              = sum(Pr(Xij=1)) 
              = n(n-1)/2 * 1/2 
              = n(n-1)/4 

* I think of this as the size of the upper triangle of a square matrix. 
** All sums here are over i, j, where i < j.