Fondamentale corrispondenza di Foata

In matematica , e più precisamente in combinatoria , la corrispondenza fondamentale di Foata è una corrispondenza tra sequenze senza ripetizioni e permutazioni, diversa dalla corrispondenza classica dove la sequenza senza ripetizioni è la sequenza di immagini, per permutazione, di elementi 1, 2, 3 , eccetera. in questo ordine. Questa corrispondenza facilita, ad esempio, l'analisi combinatoria del numero di cicli e della dimensione dei cicli di una permutazione .

Descrizione

Esistono diversi modi per codificare una permutazione utilizzando una sequenza di numeri distinti presi da  :  ω=(ω1,ω2,...,ωnon){\ displaystyle \ \ omega = (\ omega _ {1}, \ omega _ {2}, \ dots, \ omega _ {n})} non{\ displaystyle \ n} [[1,non]]{\ displaystyle \ [\! [1, n] \!]}

• nel modo più classico, si ottiene la permutazione definita da  ; ω, {\ displaystyle \ \ omega, \} Tω=σ{\ displaystyle \ T \ omega = \ sigma} σ(io)=ωio, {\ displaystyle \ \ sigma (i) = \ omega _ {i}, \}  1≤io≤non{\ displaystyle \ 1 \ leq i \ leq n}

Esempio:

Se allora  ω=(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13), {\ displaystyle \ \ omega {=} (2,8,10,6,1,3,12,5,4,9,7,15,11,14,13), \}

σ(1)=2σ(2)=8σ(3)=10σ(4)=6...=...{\ displaystyle {\ begin {align} \ sigma (1) & = 2 \\\ sigma (2) & = 8 \\\ sigma (3) & = 10 \\\ sigma (4) & = 6 \\\ punti & = \ punti \ end {allineato}}}

• in modo più correlato alla struttura dei cicli , da cui si ottiene la permutazione definita da ..., purché sia minore della lunghezza del ciclo di contenere 1 ( è la dimensione dell'orbita di 1): la posizione di 1 nel seguito indica inoltre la durata di questo ciclo: come interpretare allora  ? Foata propone di utilizzare la sequenza rimanente se non è vuota, per codificare le immagini dell'elemento più piccolo di questa sequenza ω, {\ displaystyle \ \ omega, \} Rω=τ{\ displaystyle \ R \ omega = \ tau} τ(1)=ω1, {\ displaystyle \ \ tau (1) = \ omega _ {1}, \}  τ2(1)=ω2, {\ displaystyle \ \ tau ^ {2} (1) = \ omega _ {2}, \} τK(1)=ωK, {\ displaystyle \ \ tau ^ {k} (1) = \ omega _ {k}, \} K{\ displaystyle \ k} ℓ1{\ displaystyle \ \ ell _ {1}} τ{\ displaystyle \ \ tau} ℓ1{\ displaystyle \ \ ell _ {1}} ω{\ displaystyle \ \ omega} ωℓ1=1. {\ displaystyle \ \ omega _ {\ ell _ {1}} = 1. \} ωℓ1+1{\ displaystyle \ \ omega _ {\ ell _ {1} +1}} ω′=(ωℓ1+1,ωℓ1+2,...,ωnon), {\ displaystyle \ \ omega ^ {\ prime} = (\ omega _ {\ ell _ {1} +1}, \ omega _ {\ ell _ {1} +2}, \ dots, \ omega _ {n} ), \} m2{\ displaystyle \ m_ {2}}

m2=min{ωK |ℓ1+1≤K≤non},{\ displaystyle m_ {2} = \ min \ {\ omega _ {k} \ | \ ell _ {1} +1 \ leq k \ leq n \},} impostandola di nuovo, purché sia inferiore alla lunghezza del ciclo di contenimento  : la posizione di nella sequenza indica anche la lunghezza di questo ciclo: Si itera quindi il processo con la sequenza fintanto che non è vuota, per codificare le immagini dell'elemento più piccolo di questa sequenza τ(m2)=ωℓ1+1, {\ displaystyle \ \ tau (m_ {2}) = \ omega _ {\ ell _ {1} +1}, \}  τ2(m2)=ωℓ1+2, ..., τK(m2)=ωℓ1+K, {\ displaystyle \ \ tau ^ {2} (m_ {2}) = \ omega _ {\ ell _ {1} +2}, \ \ dots, \ \ tau ^ {k} (m_ {2}) = \ omega _ {\ ell _ {1} + k}, \} K{\ displaystyle \ k} ℓ2{\ displaystyle \ \ ell _ {2}} τ{\ displaystyle \ \ tau} m2{\ displaystyle \ m_ {2}} m2{\ displaystyle \ m_ {2}} ω{\ displaystyle \ \ omega} ωℓ1+ℓ2=m2. {\ displaystyle \ \ omega _ {\ ell _ {1} + \ ell _ {2}} = m_ {2}. \} ω′′=(ωℓ1+ℓ2+1,ωℓ1+ℓ2+2,...,ωnon), {\ displaystyle \ \ omega ^ {\ prime \ prime} = (\ omega _ {\ ell _ {1} + \ ell _ {2} +1}, \ omega _ {\ ell _ {1} + \ ell _ {2} +2}, \ dots, \ omega _ {n}), \} m3=min{ωK |ℓ1+ℓ2+1≤K≤non}.{\ displaystyle m_ {3} = \ min \ {\ omega _ {k} \ | \ ell _ {1} + \ ell _ {2} +1 \ leq k \ leq n \}.} Il numero di iterazioni di questo processo è il numero di cicli di decomposizione di in cicli disgiunti τ{\ displaystyle \ \ tau} .

Questa seconda corrispondenza tra sequenze senza ripetizioni e permutazioni è proprio la corrispondenza fondamentale di Foata.

Esempio:

• Sempre con noi  ω=(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13), {\ displaystyle \ \ \ omega {=} (2,8,10,6,1,3,12,5,4,9,7,15,11,14,13), \}

m1=1, ℓ1=5, τ(1)=2, τ(2)=8, τ(8)=10, τ(10)=6, τ(6)=1,m2=3, ℓ2=1, τ(3)=3,m3=4, ℓ3=3, τ(4)=12, τ(12)=5, τ(5)=4,m4=7, ℓ4=2, τ(7)=9, τ(9)=7,m5=11, ℓ5=2, τ(11)=15, τ(15)=11,m6=13, ℓ6=2, τ(13)=14, τ(14)=13.{\ displaystyle {\ begin {align} m_ {1} & = 1, \ \ ell _ {1} = 5, \ \ tau (1) = 2, \ \ tau (2) = 8, \ \ tau (8 ) = 10, \ \ tau (10) = 6, \ \ tau (6) = 1, \\ m_ {2} & = 3, \ \ ell _ {2} = 1, \ \ tau (3) = 3 , \\ m_ {3} & = 4, \ \ ell _ {3} = 3, \ \ tau (4) = 12, \ \ tau (12) = 5, \ \ tau (5) = 4, \\ m_ {4} & = 7, \ \ ell _ {4} = 2, \ \ tau (7) = 9, \ \ tau (9) = 7, \\ m_ {5} & = 11, \ \ ell _ {5} = 2, \ \ tau (11) = 15, \ \ tau (15) = 11, \\ m_ {6} & = 13, \ \ ell _ {6} = 2, \ \ tau (13) = 14, \ \ tau (14) = 13. \ End {allineato}}} Così la corrispondenza fondamentale di Foata si associa alla permutazione la cui scomposizione in cicli disgiunti è: ω{\ displaystyle \ \ omega} τ{\ displaystyle \ \ tau}τ=(2,8,10,6,1) (3) (12,5,4) (9,7) (15,11) (14,13) = R(ω).{\ Displaystyle \ tau = (2,8,10,6,1) \ (3) \ (12,5,4) \ (9,7) \ (15,11) \ (14,13) \ = \ R (\ omega).} Inoltre, la scrittura tradizionale di è: τ{\ displaystyle \ \ tau}T-1∘R(ω)=(2,8,3,12,4,1,9,10,7,6,15,5,14,13,11).{\ Displaystyle T ^ {- 1} \ circ R (\ omega) = (2,8,3,12,4,1,9,10,7,6,15,5,14,13,11).}

• D'altra parte, la scomposizione in cicli disgiunti di è: σ{\ displaystyle \ \ sigma}

σ=(2,8,5,1) (10,9,4,6,3) (12,15,13,11,7) (14).{\ Displaystyle \ sigma = (2,8,5,1) \ (10,9,4,6,3) \ (12,15,13,11,7) \ (14).} Così la fondamentale corrispondenza di Foata si associa alla seguente sequenza : σ{\ displaystyle \ \ sigma} ω~{\ displaystyle \ {\ tilde {\ omega}}}ω~=R-1∘T(ω)=(2,8,5,1,10,9,4,6,3,12,15,13,11,7,14).{\ displaystyle {\ tilde {\ omega}} = R ^ {- 1} \ circ T (\ omega) = (2,8,5,1,10,9,4,6,3,12,15,13 , 11,7,14).}

Biiettività

Questa codifica di una permutazione da una sequenza, attribuita a Foata, è biettiva, cioè raggiungiamo tutte le permutazioni? Non raggiungiamo più volte la stessa permutazione? Infatti, un ciclo di una data lunghezza è scritto in modi differenti (123 è anche scritto 231 o 312), e la scomposizione unica in cicli di una permutazione con cicli disgiunti, di rispettive lunghezze, è quindi scritta come K{\ displaystyle k}K{\ displaystyle k}ℓ{\ displaystyle \ ell}(Kj)1≤j≤ℓ, {\ displaystyle (k_ {j}) _ {1 \ leq j \ leq \ ell}, \}

ℓ!∏1≤j≤ℓKj{\ displaystyle \ ell! \ prod _ {1 \ leq j \ leq \ ell} k_ {j}}

modi diversi, poiché i cicli disgiunti si spostano. Inoltre, la sequenza ottenuta accostando le scritte dei diversi cicli è ambigua, perché si perdono di vista le separazioni tra i cicli.

Tuttavia, va notato che la sequenza ottenuta utilizzando la corrispondenza Foata evita tutte queste insidie. In effetti, non scriviamo in alcun modo ogni ciclo, ma terminando con il suo elemento più piccolo, che fissa un modo unico di scrivere ogni ciclo. Inoltre, non si scrivono i cicli in alcun ordine, ma disposti in ordine crescente dell'elemento più piccolo di ogni ciclo. È quindi chiaro che ogni permutazione ha un'unica codifica, ben definita, data dal ciclo contenente 1, scritta in modo da terminare seguito dal ciclo contenente l'elemento più piccolo, non appartenente al ciclo di 1, s 'ci sono elementi che non appartengono al ciclo contenente 1, questo secondo ciclo scrive in modo da terminare con ecc. m1=1, {\ displaystyle m_ {1} = 1, \}m2, {\ displaystyle m_ {2}, \}m2, {\ displaystyle m_ {2}, \}

Viceversa ogni codifica può essere associata ad una sola permutazione: infatti, sebbene la fine di ogni ciclo non sia indicata dalla codifica (che è una serie di numeri tutti diversi, ma senza segni che possono indicare la fine di ogni ciclo), notiamo che se è associato, tramite la corrispondenza fondamentale di Foata, ad una permutazione allora ciascuno è più piccolo di tutti gli interi posti dopo di esso nella sequenza e che questa proprietà è caratteristica poiché l'elemento più piccolo del ciclo compare per ultimo nel ciclo , gli altri numeri del ciclo sono seguiti, poco più avanti, da un numero strettamente minore. In altre parole, sono esattamente i record del sequel rovesciati . In tal modo ω{\ displaystyle \ omega}non{\ displaystyle n}ω{\ displaystyle \ omega}τ, {\ displaystyle \ tau, \}mio{\ displaystyle m_ {i}}ω, {\ displaystyle \ omega, \}mio, {\ displaystyle m_ {i}, \}mio{\ displaystyle m_ {i}}ω~=(ωnon,ωnon-1,...,ω1){\ displaystyle {\ tilde {\ omega}} = (\ omega _ {n}, \ omega _ {n-1}, \ dots, \ omega _ {1})}

Proprietà  -  I cicli della permutazione associati alla sequenza dalla corrispondenza fondamentale di Foata sono descritti dai frammenti di questa sequenza che terminano con i record verso il fondo della sequenza inversa . In particolare, il numero di cicli nella scomposizione della permutazione è uguale al numero di record lungo la sequenza inversa . Rω{\ displaystyle R \ omega}ω{\ displaystyle \ omega}ω{\ displaystyle \ omega}ω~=(ωnon,ωnon-1,...,ω1){\ displaystyle {\ tilde {\ omega}} = (\ omega _ {n}, \ omega _ {n-1}, \ dots, \ omega _ {1})}Rω{\ displaystyle R \ omega}ω~=(ωnon,ωnon-1,...,ω1){\ displaystyle {\ tilde {\ omega}} = (\ omega _ {n}, \ omega _ {n-1}, \ dots, \ omega _ {1})}

Ciò consente di trovare la fine dei cicli della permutazione codificata successivamente e di verificare che ciascuna sequenza abbia un antecedente unico nell'insieme delle permutazioni. ω, {\ displaystyle \ omega, \}

Esempio:

Nell'esempio della sezione precedente, i record dalla sequenza inversa vengono visualizzati di seguito in grassetto e sottolineato:

 ω~=(13_,14,11_,15,7_,9,4_,5,12,3_,1_,6,10,8,2),{\ displaystyle \ {\ tilde {\ omega}} {=} ({\ underline {\ mathbf {13}}}, 14, {\ underline {\ mathbf {11}}}, 15, {\ underline {\ mathbf {7}}}, 9, {\ underline {\ mathbf {4}}}, 5,12, {\ underline {\ mathbf {3}}}, {\ underline {\ mathbf {1}}}, 6, 10,8,2),}

che, rispetto alla scomposizione in cicli disgiunti della permutazione  :  τ {\ displaystyle \ \ tau \}

τ=(2,8,10,6,1) (3) (12,5,4) (9,7) (15,11) (14,13),{\ Displaystyle \ tau {=} (2,8,10,6,1) \ (3) \ (12,5,4) \ (9,7) \ (15,11) \ (14,13), }

mostra come invertire la partita fondamentale di Foata.

Applicazioni

Possiamo considerare il gruppo simmetrico di permutazioni di n simboli come un universo probabilistico, ogni permutazione essendo ugualmente probabile. Quindi la lunghezza dei cicli, il numero di cicli di decomposizione di una permutazione in cicli disgiunti, il numero di salite, il numero di inversioni, ecc. sono variabili casuali, la cui distribuzione è interessante. Ad esempio, una formula dovuta a Cauchy indica che la legge congiunta del numero di cicli di lunghezza rispettivamente 1,2,3, ecc. è la legge di una serie di variabili di Poisson indipendenti con rispettivi parametri 1, 1/2, 1/3, ecc., 1 / n, condizionato che: Snon {\ displaystyle \ {\ mathfrak {S}} _ {n} \} (Y1,Y2,Y3,...) {\ displaystyle \ (Y_ {1}, Y_ {2}, Y_ {3}, \ dots) \}

∑K≥1 KYK = non.{\ Displaystyle \ sum _ {k \ geq 1} \ k \, Y_ {k} \ = \ n.}

Ciò risulta (ma non immediatamente) che la legge congiunta del numero di cicli di lunghezza rispettivamente 1, 2, ecc. converge ad una sequenza di variabili di Poisson indipendenti con rispettivi parametri 1, 1/2, 1/3, ecc., incondizionati, ma questo non permette di dire molto sulla legge limite delle lunghezze dei cicli maggiori di una permutazione tracciata a casuale. È qui, tra l'altro, che la corrispondenza di Foata mostra la sua utilità.

Processo di rottura dei bastoncini, processo di Poisson-Dirichlet e lunghezze dei cicli

Processo di rottura dello stick e processo di Poisson-Dirichlet

Il processo di Poisson-Dirichlet con parametro (0, θ) è una variabile casuale con valori nel simplesso di dimensione infinita:  X=(XK)K≥1 {\ displaystyle \ X = (X_ {k}) _ {k \ geq 1} \}

S={X=(XK)K≥1| Xio≥0,∀io≥1 e ∑io≥1Xio=1}.{\ displaystyle S = \ left \ {x = (x_ {k}) _ {k \ geq 1} \, \ left | \ x_ {i} \ geq 0, \ forall i \ geq 1 {\ text {e} } \ sum _ {i \ geq 1} x_ {i} = 1 \ right. \ right \}.}

La descrizione più significativa del processo di Poisson-Dirichlet è data dal seguente "algoritmo", che produce il processo di Poisson-Dirichlet  :  X=(XK)K≥1 {\ displaystyle \ X = (X_ {k}) _ {k \ geq 1} \}

• rompere un bastone di lunghezza 1, in due pezzi di rispettivi formati casuali e poi rompere nuovamente il pezzo rimanente in due pezzi a caso e quindi rompere il pezzo rimanente in due pezzi casuali di nuovo e così via. in modo da produrre una sequenza di valori in ; Y1=U1 {\ displaystyle \ Y_ {1} = U_ {1} \} R1=1-Y1, {\ displaystyle \ R_ {1} = 1-Y_ {1}, \} R1=1-Y1 {\ displaystyle \ R_ {1} = 1-Y_ {1} \} Y2=R1U2, {\ displaystyle \ Y_ {2} = R_ {1} U_ {2}, \} R2=R1(1-U2), {\ displaystyle \ R_ {2} = R_ {1} (1-U_ {2}), \} R2 {\ displaystyle \ R_ {2} \} Y3=R2U3, {\ displaystyle \ Y_ {3} = R_ {2} U_ {3}, \} R3=R2(1-U3), {\ displaystyle \ R_ {3} = R_ {2} (1-U_ {3}), \} Y=(YK)K≥1 {\ displaystyle \ Y = (Y_ {k}) _ {k \ geq 1} \} S {\ displaystyle \ S \}
• ordinare la sequenza in ordine decrescente per ottenere una sequenza decrescente con valori in Y=(YK)K≥1 {\ displaystyle \ Y = (Y_ {k}) _ {k \ geq 1} \} X=(XK)K≥1 {\ displaystyle \ X = (X_ {k}) _ {k \ geq 1} \} S. {\ displaystyle \ S. \}

Se le variabili casuali reali sono indipendenti e seguono tutte la legge Beta con parametro (1, θ) , allora segue la legge di Poisson-Dirichlet con parametro (0, θ) .  (UK)K≥1 {\ displaystyle \ (U_ {k}) _ {k \ geq 1} \} X=(XK)K≥1 {\ displaystyle \ X = (X_ {k}) _ {k \ geq 1} \}

Nota. appartiene a se e solo se  Y(ω) {\ displaystyle \ Y (\ omega) \} S {\ displaystyle \ S \}

 ∑io≥1Uio(ω)=+∞, {\ displaystyle \ \ sum _ {i \ geq 1} U_ {i} (\ omega) = + \ infty, \}

che si verifica con probabilità 1 nel caso del processo di Poisson-Dirichlet. L' sono date dalla formula esplicita  Yio(ω) {\ displaystyle \ Y_ {i} (\ omega) \}

 Yio(ω)=Uio(ω) ∏1≤K≤io-1(1-UK(ω)), {\ displaystyle \ Y_ {i} (\ omega) = U_ {i} (\ omega) \ \ prod _ {1 \ leq k \ leq i-1} \, (1-U_ {k} (\ omega)) , \}

e gli avanzi vengono donati da  Rio(ω) {\ displaystyle \ R_ {i} (\ omega) \}

 Rio(ω)= ∏1≤K≤io(1-UK(ω)). {\ displaystyle \ R_ {i} (\ omega) = \ \ prod _ {1 \ leq k \ leq i} \, (1-U_ {k} (\ omega)). \} Collegamento con le lunghezze del ciclo

Considera una permutazione casuale su n simboli, τ , o anche la sequenza ω di n tutti i diversi numeri che è associata ad essa dalla corrispondenza Foata. Indichiamo la sequenza finita delle lunghezze dei cicli di decomposizione di τ , righe in ordine decrescente, lunghezze tutte divise per n , e sequenza finita completata da una sequenza infinita di zeri.  X(non)(ω)=(XK(non)(ω))K≥1 {\ displaystyle \ X ^ {(n)} (\ omega) = \ sinistra (X_ {k} ^ {(n)} (\ omega) \ destra) _ {k \ geq 1} \}

Ad esempio, per e abbiamo   ω=(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13) {\ displaystyle \ \ \ omega = (2,8,10,6,1,3,12,5,4,9,7,15,11,14,13) \} τ=(2,8,10,6,1) (3) (12,5,4) (9,7) (15,11) (14,13),{\ Displaystyle \ \ tau = (2,8,10,6,1) \ (3) \ (12,5,4) \ (9,7) \ (15,11) \ (14,13),}

X(15)(ω)=(13, 15, 215, 215, 215, 115, 0, 0, 0, 0, ...).{\ displaystyle X ^ {(15)} (\ omega) = \ left ({\ frac {1} {3}}, \ {\ frac {1} {5}}, \ {\ frac {2} {15 }}, \ {\ frac {2} {15}}, \ {\ frac {2} {15}}, \ {\ frac {1} {15}}, \ 0, \ 0, \ 0, \ 0 , \ \ punti \ destra).}

Allora

Teorema  -  è una sequenza di variabili casuali con valori in simplex , sequenza che converge debolmente verso una distribuzione di Poisson-Dirichlet del parametro (0,1) (cioè le variabili casuali reali che intervengono nella definizione del processo di Poisson-Dirichlet tutte seguire la legge Beta del parametro (1,1), che altro non è che la legge uniforme sull'intervallo [0,1]).  (X(non))non≥1 {\ displaystyle \ \ left (X ^ {(n)} \ right) _ {n \ geq 1} \} S {\ displaystyle \ S \} (UK)K≥1 {\ displaystyle \ (U_ {k}) _ {k \ geq 1} \}

Grazie alla corrispondenza di Foata, vediamo che le lunghezze dei cicli sono dettate dalle posizioni dei numeri (record successivi) le cui posizioni sono distribuite uniformemente sullo spazio lasciato dai cicli precedenti, che naturalmente rivela una versione discreta del bastone. - processo di rottura . Si può quindi senza difficoltà formalizzare una rigorosa dimostrazione del risultato della convergenza nel diritto di cui sopra.  mio {\ displaystyle \ m_ {i} \}

Dimostrazione

È facile vedere che il numero di sequenze ω di n numeri diversi presi e soddisfacenti è (n-1)! . Quindi la lunghezza, che indicheremo del ciclo contenente 1 nella scomposizione in cicli disgiunti di verifica  [[1,non]] {\ displaystyle \ [\! [1, n] \!] \} ωK=1 {\ displaystyle \ \ omega _ {k} = 1 \} nonY1(non)(ω), {\ displaystyle \ nY_ {1} ^ {(n)} (\ omega), \} τ=R(ω), {\ displaystyle \ \ tau = R (\ omega), \}

∀K∈[[1,non]],P(nonY1(non)=K)=1non.{\ displaystyle \ forall k \ in [\! [1, n] \!], \ qquad \ mathbb {P} \ left (nY_ {1} ^ {(n)} = k \ right) = {\ frac { 1} {n}}.}

Tuttavia, se lo chiediamo

Y^1(non) = ⌈nonU1⌉non,{\ displaystyle {\ widehat {Y}} _ {1} ^ {(n)} \ = \ {\ frac {\ lceil nU_ {1} \ rceil} {n}},}

lo vediamo e abbiamo la stessa legge. altrimenti  Y1(non) {\ displaystyle \ Y_ {1} ^ {(n)} \} Y^1(non) {\ displaystyle \ {\ widehat {Y}} _ {1} ^ {(n)} \}

U1 ≤ Y^1(non) < U1 + 1non.{\ displaystyle U_ {1} \ \ leq \ {\ widehat {Y}} _ {1} ^ {(n)} \ <\ U_ {1} \ + \ {\ frac {1} {n}}.}

Poiché la sequenza converge quasi sicuramente verso si deduce che la sequenza converge di diritto verso (Y^1(non))non≥1 {\ displaystyle \ \ left ({\ widehat {Y}} _ {1} ^ {(n)} \ right) _ {n \ geq 1} \} U1, {\ displaystyle \ U_ {1}, \} (Y1(non))non≥1 {\ displaystyle \ \ left ({Y} _ {1} ^ {(n)} \ right) _ {n \ geq 1} \} U1. {\ displaystyle \ U_ {1}. \}

Esaminiamo ora la lunghezza, che indicheremo con il ciclo contenente nella scomposizione in cicli disgiunti di Possiamo facilmente vedere che la legge condizionale del sapere che è la legge uniforme su appunto, sapendo che la sequenza ω inizia con una sequenza di numeri k-1 molto precisi, seguiti dal numero 1, il nk! modi di terminare la sequenza ω sono ugualmente probabili, e la posizione del numero più piccolo rimanente è quindi distribuita uniformemente sulle nk posizioni di questa sequenza, per la stessa ragione di prima: da qui la legge condizionale di sapere tutto sui primi k termini di la sequenza, è la legge uniforme su e quindi non dipende realmente dai primi k-1 termini di questa sequenza, ma solo dal fatto che il numero 1 appare alla k -esima posizione. La legge uniforme su è quindi anche la legge condizionale del sapere che nonY2(non)(ω), {\ displaystyle \ nY_ {2} ^ {(n)} (\ omega), \} m2 {\ displaystyle \ m_ {2} \} τ=R(ω). {\ displaystyle \ \ tau = R (\ omega). \} nonY2(non), {\ displaystyle \ nY_ {2} ^ {(n)}, \} nonY1(non)=K, {\ displaystyle \ nY_ {1} ^ {(n)} = k, \} [[1,non-K]]: {\ displaystyle \ [\! [1, nk] \!]: \} m2, {\ displaystyle \ m_ {2}, \} nonY2(non), {\ displaystyle \ nY_ {2} ^ {(n)}, \} [[1,non-K]], {\ displaystyle \ [\! [1, nk] \!], \} [[1,non-K]] {\ displaystyle \ [\! [1, nk] \!] \} nonY2(non), {\ displaystyle \ nY_ {2} ^ {(n)}, \} nonY1(non)=K. {\ displaystyle \ nY_ {1} ^ {(n)} = k. \}

Mettiamoci in posa

Y^2(non) = ⌈non(1-Y^1(non))U2⌉non.{\ displaystyle {\ widehat {Y}} _ {2} ^ {(n)} \ = \ {\ frac {\ left \ lceil n (1 - {\ widehat {Y}} _ {1} ^ {(n )}) U_ {2} \ right \ rceil} {n}}.}

Quindi le coppie e hanno la stessa legge, ma la seconda coppia converge quasi sicuramente verso Indeed:  (Y1(non),Y2(non)) {\ displaystyle \ (Y_ {1} ^ {(n)}, Y_ {2} ^ {(n)}) \} (Y^1(non),Y^2(non)) {\ displaystyle \ ({\ widehat {Y}} _ {1} ^ {(n)}, {\ widehat {Y}} _ {2} ^ {(n)}) \} (U1,(1-U1)U2)=(Y1,Y2). {\ displaystyle \ \ left (U_ {1}, (1-U_ {1}) U_ {2} \ right) = (Y_ {1}, Y_ {2}). \}

(1-U1)U2 -U2non ≤Y^2(non) = ⌈⌊non(1-U1)⌋U2⌉non ≤ (1-U1)U2 +1non.{\ displaystyle (1-U_ {1}) U_ {2} \ - {\ frac {U_ {2}} {n}} \ \ leq {\ widehat {Y}} _ {2} ^ {(n)} \ = \ {\ frac {\ left \ lceil \ lfloor n (1-U_ {1}) \ rfloor U_ {2} \ right \ rceil} {n}} \ \ leq \ (1-U_ {1}) U_ {2} \ + {\ frac {1} {n}}.}

Così la coppia converge di diritto verso In un modo alquanto noioso, ma senza grandi difficoltà, si otterrà così, per ogni k , la convergenza di diritto del verso ; di seguito viene delineato un metodo più elegante, consistente nello studio della convergenza dei resti . Ciò comporta la convergenza di diritto della successione verso la successione Sul simplex, l'operazione consistente nell'ordinare una successione in modo decrescente è un'operazione continua per la topologia della convergenza termine per termine (che è metrizzabile). Così le sequenze ottenute riordinando le sequenze in modo decrescente, cioè anche le sequenze convergono di diritto, verso il riordino decrescente della sequenza Y , che, per definizione, è un processo di Poisson-Dirichlet con parametro (0,1).  (Y1(non),Y2(non)) {\ displaystyle \ (Y_ {1} ^ {(n)}, Y_ {2} ^ {(n)}) \} (Y1,Y2). {\ displaystyle \ (Y_ {1}, Y_ {2}). \} (Yio(non))1≤io≤K {\ displaystyle \ (Y_ {i} ^ {(n)}) _ {1 \ leq i \ leq k} \} (Yio)1≤io≤K {\ displaystyle \ (Y_ {i}) _ {1 \ leq i \ leq k} \} Y(non) {\ displaystyle \ Y ^ {(n)} \} Y. {\ displaystyle \ Y. \} Y(non), {\ displaystyle \ Y ^ {(n)}, \} X(non), {\ displaystyle \ X ^ {(n)}, \}

Nota: una sequenza non può essere sempre riordinata in modo decrescente (ad esempio l'enumerazione di tutti i razionali non può essere riordinata in questo modo), ma una sequenza appartenente al simplex può sempre essere riordinata in modo decrescente, perché l'insieme dei termini di questa successione maggiore di ε> 0 è un insieme finito, quindi ben ordinato.

Studio dei resti. Dato un qualsiasi inizio di una sequenza di lunghezza nk , la fine della sequenza, di lunghezza k , è uniformemente distribuita tra i k! possibile fine delle suite. È quindi conveniente studiare i resti successivi:

R0(non)=non, R1(non) = non-nonY1(non), R2(non) = non-nonY1(non)-nonY2(non), R3(non) = non-nonY1(non)-nonY2(non)-nonY3(non), ...{\ displaystyle R_ {0} ^ {(n)} = n, \ R_ {1} ^ {(n)} \ = \ n-nY_ {1} ^ {(n)}, \ R_ {2} ^ { (n)} \ = \ n-nY_ {1} ^ {(n)} - nY_ {2} ^ {(n)}, \ R_ {3} ^ {(n)} \ = \ n-nY_ {1 } ^ {(n)} - nY_ {2} ^ {(n)} - nY_ {3} ^ {(n)}, \ \ dots}

L'uniformità delle sequenze residue, annotata poco sopra, implica che la legge condizionale del sapere che è la legge uniforme su (la posizione del minimo della sequenza residua, di lunghezza k , essendo distribuita uniformemente su di essa segue che il numero di termini della sequenza che compaiono dopo che il minimo è uniformemente distribuito Questo rende la sequenza una catena di Markov , a partire da n , con un kernel di transizione molto semplice  Rℓ+1(non){\ displaystyle \ R _ {\ ell +1} ^ {(n)}} (Rj(non))1≤j≤ℓ=(r1,r2,...,rℓ-1,K), {\ displaystyle \ \ left (R_ {j} ^ {(n)} \ right) _ {1 \ leq j \ leq \ ell} = (r_ {1}, r_ {2}, \ dots, r _ {\ ell -1}, k), \} [[0,K-1]] {\ displaystyle \ [\! [0, k-1] \!] \} [[1,K]], {\ displaystyle \ [\! [1, k] \!], \} [[0,K-1]]).{\ displaystyle \ [\! [0, k-1] \!]).} (Rj(non))j≥0 {\ displaystyle \ \ left (R_ {j} ^ {(n)} \ right) _ {j \ geq 0} \}

pK,j = 1K 1 io0≤j<K,K,j∈NON.{\ displaystyle p_ {k, j} \ = \ {\ frac {1} {k}} \ 1 \! \! \! \ {\ text {I}} _ {0 \ leq j <k}, \ qquad k, j \ in \ mathbb {N}.}

Tuttavia, possiamo generare una tale catena di Markov utilizzando una sequenza di variabili casuali indipendenti uniformi su [0,1] , tramite la relazione di ricorrenza  (Uj)j≥1 {\ displaystyle \ \ sinistra (U_ {j} \ destra) _ {j \ geq 1} \}

R^j(non) = ⌊R^j-1(non)(1-Uj)⌋,j≥1, e R^0(non) = non.{\ displaystyle {\ widehat {R}} _ {j} ^ {(n)} \ = \ \ left \ lfloor {\ widehat {R}} _ {j-1} ^ {(n)} (1-U_ {j}) \ right \ rfloor, \ qquad j \ geq 1, \ qquad {\ text {et}} {\ widehat {R}} _ {0} ^ {(n)} \ = \ n.}

Mettiamoci in posa

rj = ∏K=1j(1-UK),j≥1, e r0 = 1.{\ displaystyle r_ {j} \ = \ \ prod _ {k = 1} ^ {j} (1-U_ {k}), \ qquad j \ geq 1, \ qquad {\ text {e}} r_ {0 } \ = \ 1.}

Lo dimostriamo facilmente

0 ≤ nonrj-R^j(non) ≤ j,j≥0,{\ displaystyle 0 \ \ leq \ nr_ {j} - {\ widehat {R}} _ {j} ^ {(n)} \ \ leq \ j, \ qquad j \ geq 0,}

quindi la sequenza converge quasi sicuramente, termine per termine, verso la sequenza. Di conseguenza, la sequenza converge di diritto verso la sequenza r . La sequenza delle lunghezze dei cicli, come appaiono nella corrispondenza Foata, viene dedotta dalla sequenza dei resti utilizzando la relazione  (R^j(non)/non)j≥1 {\ displaystyle \ \ left ({\ widehat {R}} _ {j} ^ {(n)} / n \ right) _ {j \ geq 1} \} r=(rj)j≥1. {\ displaystyle \ r = \ sinistra (r_ {j} \ destra) _ {j \ geq 1}. \} (Rj(non)/non)j≥0 {\ displaystyle \ \ sinistra (R_ {j} ^ {(n)} / n \ destra) _ {j \ geq 0} \} (nonYj(non))j≥1, {\ displaystyle \ \ left (nY_ {j} ^ {(n)} \ right) _ {j \ geq 1}, \}

nonYj(non) = Rj-1(non) - Rj(non),j≥1.{\ displaystyle nY_ {j} ^ {(n)} \ = \ R_ {j-1} ^ {(n)} \ - \ R_ {j} ^ {(n)}, \ qquad j \ geq 1.}

Così la sequenza converge di diritto verso la sequenza e altrove  (Yj(non))j≥1, {\ displaystyle \ \ left (Y_ {j} ^ {(n)} \ right) _ {j \ geq 1}, \} (rj-1-rj)j≥1, {\ displaystyle \ \ left (r_ {j-1} -r_ {j} \ right) _ {j \ geq 1}, \}

rj-1-rj = Yj,j≥1.{\ displaystyle r_ {j-1} -r_ {j} \ = \ Y_ {j}, \ qquad j \ geq 1.}

Si noti che la legge di (primo termine della sequenza X ) è chiamata distribuzione di Dickman ed è onnipresente nell'analisi probabilistica degli oggetti algebrici (dimensione del fattore primo più grande di un numero intero estratto a caso, grado del fattore primo grado più alto di un polinomio disegnato a caso, dimensione del ciclo più lungo di una permutazione disegnata a caso, ecc.).  X1 {\ displaystyle \ X_ {1} \}

Interpretazioni del numero di Stirling

I numeri di Stirling del primo tipo contano il numero di permutazioni di n oggetti con esattamente k cicli, ma anche il numero di permutazioni di n oggetti con esattamente k record. Usando il codice Lehmer di una permutazione, il numero di record, e quindi anche il numero di cicli, possono essere visti come somme di variabili di Bernoulli indipendenti , il che spiega la forma moltiplicativa della serie generatrice di numeri di Stirling , e apre la strada a stime precise sulla concentrazione della legge del numero di cicli (stime tramite la disuguaglianza di Hoeffding , o utilizzando il teorema del limite centrale ).

Vedi anche

Appunti

1. (in) JFC Kingman , "  Random Discrete Distributions  " , Journal of the Royal Statistical Society. Serie B (metodologica) , vol.  37, n o  1,1975, p.  1-22 ( leggi in linea )
2. (in) AM Vershik e AA Shmidt , "  Misure limite che sorgono nella teoria dei gruppi I.  " , Theor. Probab. Appl. , vol.  22,1977, p.  79-85.
3. (in) JF Kingman , "  La struttura della popolazione associata alla formula di campionamento di Ewens  " , Theor Popul Biol. , vol.  11, n o  2Aprile 1977, p.  274-283

Bibliografia

• (en) M. Lothaire , Combinatorics on Words , Addison - Wesley, coll.  "Encyclopedia of Mathematics and its Applications",1983( ripr.  1997), 260  p., Sezione 10.2.
• (en) Philippe Flajolet e Robert Sedgewick , Analytic Combinatorics , Cambridge University Press ,2008( ISBN  0-521-89806-4 , leggi online ), Sezione II.6.3.
• (en) Jean Bertoin , Random Fragmentation and Coagulation Processes , Cambridge University Press, coll.  "Cambridge Studies in Advanced Mathematics",28 agosto 2006, 1 °  ed. , 288  p. ( ISBN  0521867282 ), Sezione 2.2.4.
• (en) Jim Pitman , Combinatorial Stochastic Processes: Summer School of Probability of Saint-Flour XXXII - 2002 , Springer, coll.  "Appunti di matematica",6 luglio 2006, 1 °  ed. , 256  p. ( ISBN  354030990X )

Articolo correlato

Biiezione di Joyal

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">