Don't take life too seriously: it's just a temporary situation

Supponiamo di prendere n cartellini, numerati da 1 a n, mescolarli a caso e disporli in fila: questa semplice operazione pone alcuni interessanti problemi di statistica.

 

In primo luogo ci si può chiedere quanti cartellini siano al loro posto: Eulero dimostrò che la probabilità che non vi siano cartellini al posto giusto tende rapidamente a 1 / e all’aumentare dei cartellini, risolvendo definitivamente un problema già affrontato da Nicolaus Bernoulli (Basilea, 21/10/1687 – Basilea, 29/11/1759: attenzione a non confonderlo col padre, col nonno e col cugino, omonimi).

 

Per riportare ciascun cartellino al proprio posto, possiamo prenderne uno e metterlo al posto giusto, prelevando il cartellino che occupava tale posto abusivamente, mettere questo cartellino al suo posto, spostandone un altro e così via. A un certo punto ci capiterà in mano quello che va al posto del primo spostato e lo metteremo nel posto vuoto, completando un ciclo di spostamenti di una certa lunghezza. Un ciclo di lunghezza 1 corrisponde a un cartellino al suo posto, uno di lunghezza 2 a due cartellini scambiati e così via. Dopo aver completato alcuni cicli, avremo rimesso a posto tutti i cartellini.

 

Con n elementi il la media del numero di cicli è il numero armonico Hn e la varianza è HnHn, 2, dove Hn, k è un numero armonico generalizzato. Di conseguenza la media tende a logn + γ e la varianza a logn + γ + ψ(n + 1) – ζ(2).

 

Goncharov dimostrò nel 1942 che la probabilità che vi siano esattamente k cicli di lunghezza m tende a Limite cui tende la probabilità che vi siano esattamente k cicli di lunghezza m, ovvero che la distribuzione di 1 / m tende a una distribuzione di Poisson.

 

S.W. Golomb dimostrò che il numero di cartellini che formano il ciclo più lungo è in media una frazione λ ≈ 0.6243299885 del numero totale di cartellini e tale numero è noto come “costante di Golomb – Dickman”.

Mitchell ne calcolò 53 cifre decimali nel 1968, A. MacLeod 250 nel 1997, D.J. Broadhurst 1659 nel 2010 e nello stesso anno (addirittura il giorno dopo!) E.W. Weisstein portò il record a 2508.

Qui trovate le prime 101 cifre della costante (The Online Encyclopedia of Integer Sequences http://oeis.org).

 

La costante è anche uguale a:

  • Integrale per il calcolo della costante di Golomb – Dickman (L.A. Shepp e S.P. Lloyd, 1966);

  • Integrale per il calcolo della costante di Golomb – Dickman (L.A. Shepp e S.P. Lloyd, 1966).

 

Golomb dimostrò che la costante si può ricavare come Integrale per il calcolo della costante di Golomb – DickmanIntegrale per il calcolo della costante di Golomb – DickmanIntegrale per il calcolo della costante di Golomb – Dickman dove ρ(x), detta “funzione di Dickman”, è la soluzione dell’equazione differenziale ρ(x) = 1 per 0 ≤ x ≤ 1 e xρ’(x) = –ρ(x – 1) per x > 1.

 

La funzione ρ è non crescente e Limite cui tende la funzione di Dickman.

La funzione può essere approssimata come Approssimazione per la funzione di Dickman, dove ξ è la soluzione dell’equazione eξ – 1 = ξx.

In ogni intervallo del tipo [n .. n + 1], con n intero, la funzione è uguale a una funzione analitica, che cambia per ogni intervallo. Per esempio: ρ(x) = 1 – logx per 1 ≤ x ≤ 2.

Tra i valori particolari,va ricordato Valore particolare della funzione di Dickman.

Da notare una curiosa relazione tra integrale e somma della funzione ρ: Relazione tra integrale e somma della funzione di Dickman.

 

Gourdon dimostrò nel 1996 che la lunghezza media del ciclo più lungo è Lunghezza media del ciclo più lungo.

 

L.A. Shepp e S.P. Lloyd dimostrarono nel 1966 che il numero di cartellini che formano il ciclo più corto tende a e–γ ≈ 0.5614594836 del numero totale di cartellini.

 

Se si ripete una permutazione di n elementi un numero sufficiente di volte, si ottiene di nuovo la disposizione iniziale. W.M.Y. Goh e E. Schmutz dimostrarono nel 1991 che il numero medio di ripetizioni necessarie tende a Numero medio di ripetizioni della permutazione per riottenere la disposizione iniziale, dove Formula per la definizione di b.

R. Stong dimostrò nel 1998 che Formula per il calcolo di b.

 

Se invece delle permutazioni consideriamo generiche funzioni da un insieme finito di elementi in se stesso, abbiamo altri risultati interessanti. Applicando ripetutamente la funzione si possono produrre cicli, che interessano solo una parte degli elementi. Per esempio, se consideriamo la funzione f(n) = 2n mod 10, applicata agli interi da 0 a 9, vediamo che si generano due cicli: uno formato dallo zero, l’altro formato dai numeri 2, 4, 8, 6 (in questo ordine); i numeri dispari invece producono numeri pari e vengono quindi “assorbiti” da uno dei due cicli.

P.W. Purdom e J.H. Williams dimostrarono nel 1968 che la lunghezza media del ciclo più lungo, calcolata su tutte le possibili funzioni su insiemi di n elementi, tende a Limite cui tende la lunghezza media del ciclo più lungo e la lunghezza media del ciclo più corto tende a Limite cui tende la lunghezza media del ciclo più corto.

 

Una funzione può essere applicata più volte ad alcuni elementi, prima di entrare in un ciclo; nel nostro esempio, una sola volta ai numeri dispari. La lunghezza media della sequenza più lunga prima di entrare in un ciclo tende a Limite cui tende la lunghezza media della sequenza più lunga prima di entrare in un ciclo.

 

La funzione dell’esempio separa i numeri in due gruppi, uno formato da 0 e 5, l’altro formato dai restanti, in modo tale che applicando ripetutamente la funzione il valore resta sempre all’interno del gruppo dell’argomento. Il numero medio di gruppi tende a Limite cui tende il numero medio di gruppi.

 

La costante di Golomb – Dickman ha una sorprendente connessione con la scomposizione in fattori primi: K. Dickman infatti dimostrò nel 1930 che il valor medio di x, tale che p = nx sia il massimo fattore primo di n, tende a λ ed è per questo motivo che la costante porta anche il suo nome. Più precisamente, Limite cui tende il rapporto medio tra logaritmo del massimo fattore primo di un intero e il logaritmo dell'intero, dove P(n) è il massimo fattore primo di n.

Inoltre la probabilità che il secondo più grande fattore primo di n non superi la radice quadrata del massimo tende a λ.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.