Osservazioni casuali di un ordinamento totale, quanto ci dicono?

Question

Supponiamo di avere un ordine totale su elementi $ a_1, a_2, ..., a_n $, che significa che c'è permutazione $ pi $ tale che $ a _ { pi (1)}. Ma non lo sappiamo $ pi $. Quello che sappiamo è una serie di osservazioni casuali dall'ordine a coppie degli elementi. La matrice di osservazione $ B in {0,1 }^{n tempes n} $ viene generato in modo casuale come segue:$$ b_ {i, j} sim inizio {casi} text {bernoulli} (p) qquad text {if} i> j 0 qquad qquad qquad text {altrimenti} end { Casi} $$in quale $ p in [0,1] $ è una costante. La formula sopra significa che gli elementi sopra diagonali sono disegnati da $ text {bernoulli} (p) $ E il resto degli elementi lo sono $0$. Matrice $ B $ indica le nostre osservazioni sull'ordinamento, cioè se $ B_ {i, j} = 1 $ Conosciamo l'ordine di $ a_i $ e $ a_j $, e altrimenti no. Il motivo per cui elementi sul triangolo inferiore di $ B $ sono zero è perché le osservazioni simmetriche sono rossa.

Domanda 1

Permettere $ K $ denotare il numero di ordini di $ a_1, ..., a_n $ che sono coerenti con le nostre osservazioni parziali. Da $ B $ è una variabile casuale, $ K $ è anche una variabile casuale. La domanda è: di cosa il valore atteso $ K $ e qual è la sua concentrazione attorno alla media in funzione di $ p $? Ci sono due casi estremi: (1) se $ p = 0 $ Tutti gli ordini sono validi e quindi $ K = n! $ (2) Se $ p = 1 $ Abbiamo l'ordinamento completo e $ K = 1 $.

Per $ 0 però $ K $ non sarebbe una costante. La mia ipotesi è che per sufficientemente grande $ n $ Se $ p gg mathcal {o} ( frac { log n} {n}) $ porterebbe a $ mathbb {e} [k] a 1 $. La logica alla base di questo è che avremmo $ omega (np) = omega (n log n) $ Confronti che sono asintoticamente più grandi del numero di confronti che la maggior parte degli algoritmi di smistamento fa. Tuttavia, ciò è tutt'altro che chiaro poiché le osservazioni sono prese a caso.

La risposta è idealmente una distribuzione con il parametro $ p $ per il numero di possibilità. Ma se ciò non è possibile, sono accettabili anche i limiti di coda o il valore e la varianza attesi.

Domanda 2

La motivazione alla base della definizione di $ K $ era catturare quanta incertezza rimane. Ma sembra sopravvalutarlo o non esprimerlo molto bene, perché se non conosciamo alcune coppie $ K $ crescerà in modo esponenziale con questo numero. Quindi stavo pensando a un altro modo naturale di definirlo.

Permettere $ O in {0,1 }^{n Times n} $ essere il risultato delle nostre osservazioni, in cui $ O_ {i, j} = 1 $ designa che abbiamo osservato $ a_i. Da questa matrice possiamo calcolare la chiusura transitiva $ O^ stella $, che applica proprietà transitive per trovare tutte le relazioni "più piccole del" nei dati. Ad esempio, se abbiamo $ O_ {i, j} = 1 $ e $ O_ {j, k} = 1 $ avremo $ O^ star_ {i, k} = 1 $. Questo vale anche per una catena di lunghezza arbitraria.

Permettere $ S $ essere la somma di tutti gli elementi di $ O^ stella $. Se possiamo concludere le relazioni tra tutte le coppie, $ S $ raggiungerà il suo valore massimo di $ S = n (n-1)/2 $, e così $ I = frac {s} {(n (n-1)/2)} $ è un valore che mostrerà quanto sappiamo sull'ordinamento, con $1$ Significa che conosciamo esattamente l'ordinamento e $0$ Significa che non sappiamo nulla. Ora la domanda è: ciò che è cattivo $ mathbb {e} [i] $ come una funzione di $ n $ e $ p $? E se è possibile analizzare, qual è la concentrazione di $ I $ Intorno è meschino? Inoltre, a cosa serve la soglia $ p $ come una funzione di $ n $ quello fa $ mathbb {e} [i] $ salta a $0$ o $1$?

Per simulazioni l'ho trovato quando $ n a infty $, anche per un piccolo valore di $ p = frac { log n} {n} $ porta a $ I to1 $ con alta probabilità. La ragione di questa apparente discrepanza tra $ I $ e $ K $ è che se abbiamo $ m $ coppie sconosciute in $ O^ stella $, poi $ K $ crescerà esponenzialmente WRT $ m $ mentre $ S $ sarà interessato solo linearmente. sebbene il $ I $ e $ log k $ sono correlati, non credo che ci sia una relazione esatta tra di loro.