Skip to content

Scegliere in modo uniforme due derangements $sigma_i,sigma_j$. Qual è la distribuzione di $sigma_icirc sigma_j$?

Cerca di interpretare correttamente il codice prima di adattarlo al tuo lavoro se vuoi contribuire con qualcosa puoi lasciarlo nella sezione dei commenti.

Soluzione:

Prova incompleta (che la congettura è vera).

Lasciare che $sigma$ sia una qualche permutazione di destinazione, e cerchiamo $p(sigma) = P(sigma_i circ sigma_j = sigma)$. L'evento è equivalente a $sigma_i^{-1} circ sigma = sigma_j$. Quindi la domanda diventa divisa in due parti:

  1. È $sigma_i^{-1} ´circ ´sigma$ uno squilibrio?

  2. Condizionato da $sigma_i^{-1} circ ´sigma$ sia uno squilibrio, qual è la probabilità che $sigma_j$ sia uguale a quell'alterazione? La risposta alla seconda domanda è semplicemente $1/|D_n|$. Cioè

$$p(sigma) = P(sigma_i^{-1} circ sigma in D_n) ´times frac1{|D_n|}$$

Questo spiega perché l'identità $sigma^*$ è favorita: $P(sigma_i^{-1} circ sigma^* in D_n) = 1$. Ha infatti il massimo $p(sigma)$ tra tutti i target $sigma$'s.

Ora, $Sigma_1^{-1}$ è solo uno squilibrio casuale, quindi la questione diventa calcolare, per qualsiasi obiettivo dato $sigma$, la probabilità $f(sigma) = P(pi circ sigma in D_n)$ dove $pi$ è uno squilibrio casuale, e avremo $p(sigma) = f(sigma) / |D_n|$.

Il resto della risposta non è rigoroso. Immagino che la cosa principale (l'unica cosa?) che conta sia il numero di punti fissi di $sigma$. Più punti fissi ci sono, più alto è $f(sigma)$ perché:

  • Qualsiasi punto fisso di $sigma$, ad esempio $sigma(i) = i$, sicuramente non essere fissato più in $pi ´circ ´sigma$, cioè $pi(sigma(i)) neq sigma(i) = i$.

  • Tuttavia, qualsiasi punto non fisso di $sigma$, ad esempio $sigma(i) = j ´neq i$ potrebbe sfortunatamente fissarsi in $pi circ sigma$, cioè $pi(sigma(i)) = i$, se $pi$ si verifica un "annullamento" $sigma$ in quel momento, cioè $pi(j) = i$.

  • E naturalmente se $pi ´circ ´sigma$ ha un punto fisso, allora è $non in D_n$. Cioè ogni punto non fisso di $sigma$ è una sorta di "motivo potenziale" per violare$pi ´circ ´sigma ´in D_n$ abbassando così $f(sigma)$.

In ogni caso, sulla base di questa argomentazione non rigorosa, il valore più basso di $f(sigma)$ si verificherebbe se $sigma$ non ha punti fissi, cioè è esso stesso un derangement. Senza perdite, qualsiasi derangement andrebbe bene per $sigma$ in questo caso, e $f(sigma)$ diventa la probabilità che due squilibri si compongano per formare un terzo squilibrio -- che viene affrontato esattamente in questa risposta. In base ad essa, il valore asintotico della probabilità è $1/e$.

Cioè, se credete a questa risposta (è troppo avanzata perché io possa verificarla), e se credete a me che $sigma$ essendo di per sé un errore è il "caso peggiore", allora la tua congettura è vera, con limiti $c = 1/e^2, C = 1/e$.


Per inciso, ho provato a usare il limite dell'unione, ma come previsto non è abbastanza forte. Sia $k$ denota il numero di punti non fissi di $sigma$ (cioè $n-k = $ n. di punti fissi di $sigma$), e sia $sigma(i) = j neq i$ denota un tipico punto non fisso di questo tipo. Si ha:

$$pi circ sigma in D_n iff bigcap pi(j) neq i$$

$$P(pi circ sigma in D_n) = 1 - P(bigcup pi(j) = i) ge 1 - k P(pi(j) = i) = 1 - {k over n-1}$$

dove l'intersezione e l'unione sono entrambe su tutti i punti non fissi di $sigma$ e $P(pi(j) = i) = 1/(n-1)$ per simmetria. Tuttavia, questo limite non solo fallisce per $k=n$ (cioè il caso "difficile" di $sigma$ sia uno sbilanciamento), inoltre non fornisce un limite asintotico lontano da $0$ per es. $k = n-10$.

Di seguito è riportata un'approssimazione per la distribuzione, che dimostra che la tua ipotesi è giusta. Si noti che per qualsiasi dato $pi in S_n$, $mathbb{P}[sigma_i circ sigma_j = pi]$ è $frac{1}{|D_n|^2}$ volte il numero $N(pi)$ di alterazioni $sigma$ tali che $pi^{-1} ´circ ´sigma$ è anch'esso un derangement. Equivalentemente, $N(pi)$ è il numero di $sigma in S_n$ tale che $sigma(x) neq x, pi(x)$ per tutti $x in [n]$. Possiamo trovare un'espressione per $N(pi)$ utilizzando un argomento di inclusione-esclusione simile a quello standard utilizzato per trovare il numero di derangements. Si ha
$$N(pi) = sum_{A subset [n]} (-1)^{|A|} #´#{sigma ´in S_n ´mid sigma(a) ´in {a, pi(a)} , per tutto a in A}.$$
Ora, dato un insieme $A sottoinsieme [n]$ e una funzione iniettiva $f : A ´a [n]$ tale che $f(a) ´in {a, pi(a)}$ per tutti $a in A$, ci sono esattamente $(n-|A|)!$ scelte di $sigma in S_n$ che concordano con $f$ su $A$, quindi possiamo scrivere
$$##{sigma in S_n mid sigma(a) \{a, pi(a)} , per tutti gli a in A} = F_A(pi)(n-|A|)!$$
dove $F_A(pi)$ è il numero di tali funzioni. Si ottiene
$$N(pi) = sum_{A subset [n]} (-1)^{|A|} F_A(pi)(n-|A|)! = n! sum_{k=0}^n frac{(-1)^k}{k!} binom{n}{k}^{-1} sum_{|A| = k} F_A(pi).$$
Chiaramente ogni $F_A(pi) ´leq 2^k$, quindi $binom{n}{k}^{-1} sum_{|A| = k} F_A(pi) leq 2^k$, quindi questi termini diminuiscono in modo estremamente rapido:
$$sinistra|frac{N(pi)}{n!} - sum_{k=0}^m frac{(-1)^k}{k!} binom{n}{k}^{-1} sum_{|A| = k} F_A(pi) right| leq sum_{k=m+1}^n frac{2^k}{k!} frac{2^m}{m!} sum_{k=1}^infty frac{2^k}{m^k} leq frac{2^m}{m!}$$
vale per $m geq 4$.

Ora troviamo un'approssimazione per i termini maggiori. Si noti che $k! sum_{|A| = k} F_A(pi)$ è il numero di sequenze di coppie $(a_1, b_1), dots, (a_k, b_k) in [n]^2$ tali che tutti $a_i$ sono distinti, tutti $b_i$ sono distinti e $b_i in {a_i, pi(a_i)}$ per ogni $i$. Chiamare una sequenza $a_1, dots, a_k$buono se tutti ${a_i, ´pi(a_i)}$ sono disgiunti (quindi in particolare tutti i $a_i$ sono distinti), e si noti che per una sequenza buona, il numero di sequenze corrispondenti di coppie è $prod_{i=1}^k |{a_i, pi(a_i)}|$. Come in precedenza, per qualsiasi sequenza (non necessariamente buona) $a_1, punti, a_k$, il numero di sequenze di coppie corrispondenti è al massimo $2^k$. Infine, il numero di sequenze $a_1, punti, a_k$ che non sono buone è al massimo $2k^2 n^{k-1}$ (poiché una sequenza non è buona se ci sono indici $i$ e $j$ con $a_i = a_j$ oppure $a_i = pi(a_j)$). Quindi
$$sinistra|k!sum_{|A| = k}F_A(pi) - sum_{a_1, dots, a_k} prod_{i=1}^k |{a_i, pi(a_i)}|destra| leq 2^{k+1}k^2 n^{k-1}$$
ma $somma_{a_1, punti, a_k} prod_{i=1}^k |{a_i, pi(a_i)}| = (sum_a |{a, pi(a)}|)^k = (2n-t)^k$$, dove $t$ è il numero di punti fissi di $pi$. Lasciando $c = t/n$, abbiamo $sinistra|frac{k!}{n^k} sum_{|A| = k}F_A(pi) - (2-c)^k right| leq frac{2^{k+1}k^2}{n}.$
Questo può essere scritto come $frac{k!}{n^k} sum_{|A| = k}F_A(pi) = (2-c)^k + O(frac{2^k k^2}{n})$, e quindi poiché $binom{n}{k}^{-1} = frac{k!}{n^k}(1 + O(frac{k^2}{n}))$ per piccoli $k$, otteniamo
$$binom{n}{k}^{-1} sum_{|A| = k}F_A(pi) = (2-c)^k + Oleft(frac{2^k k^2}{n}right)$$
da cui $$ $sum_{k=0}^m (-1)^k binom{n}{k}^{-1} sum_{|A| = k}F_A(pi) = sum_{k=0}^m frac{(c-2)^k}{k!} + O(1/n)$.
Notando che $|sum_{k=0}^infty frac{(c-2)^k}{k!} - sum_{k=0}^m frac{(c-2)^k}{k!}| leq frac{2^m}{m!}$ per $m geq 4$ e prendendo $m$ abbastanza grande da far sì che $2^m/m! leq 1/n$, otteniamo
$$frac{N(pi)}{n!} = sum_{k=0}^infty frac{(c-2)^k}{k!} + O(1/n) = e^{c-2} + O(1/n) $$
dove il termine di errore è uniforme su tutti i $$. Quindi, poiché $|D_n| = n! e^{-1}(1 + O(1/n))$, abbiamo
$$mathbb{P}[sigma_i circ sigma_j = pi] = frac{N(pi)}{|D_n|^2} = frac{1}{n!} (e^c + O(1/n))$$
dove ancora una volta, $c = c(pi) = t/n$ è la frazione di $[n]$ fissata da $ $pi$.

Recensioni e valutazioni della guida

Se ti piace questo mondo, puoi lasciare un saggio su ciò che ti ha colpito di questa recensione.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.