Un problema sulle concordanze
Testo del problema :
"In un'urna vi sono 5 palline numerate dall'uno al
cinque.Esse vengono estratte ,una per volte ,dall'urna
senza essere rimesse.
Si chiede la probabilita' che vi sia almeno una concordanza
tra il numero segnato sulla pallina estratta e la sequenza
di estrazione(per es.:alla terza estrazione venga fuori
la pallina che porta il numero 3).
Il risultato indicato dal libro e':
P=1-1/2!+1/3!-1/4!+1/5!=19/30
(In realta' le palline sono (genericamente) n,ma la formula puo' essere facilmente generalizzata).
Confesso di non aver molto "feeling" per questo genere di
questioni,ma,avendo notato che sul forum ne capitano
parecchie,ho pensato che questo mio problema potesse
interessare e/o divertire qualcuno (scusandomi in anticipo
se la cosa fosse gia' stata discussa).
karl.
"In un'urna vi sono 5 palline numerate dall'uno al
cinque.Esse vengono estratte ,una per volte ,dall'urna
senza essere rimesse.
Si chiede la probabilita' che vi sia almeno una concordanza
tra il numero segnato sulla pallina estratta e la sequenza
di estrazione(per es.:alla terza estrazione venga fuori
la pallina che porta il numero 3).
Il risultato indicato dal libro e':
P=1-1/2!+1/3!-1/4!+1/5!=19/30
(In realta' le palline sono (genericamente) n,ma la formula puo' essere facilmente generalizzata).
Confesso di non aver molto "feeling" per questo genere di
questioni,ma,avendo notato che sul forum ne capitano
parecchie,ho pensato che questo mio problema potesse
interessare e/o divertire qualcuno (scusandomi in anticipo
se la cosa fosse gia' stata discussa).
karl.
Risposte
caro karl
si tratta di un problema classico che io personalmente ho in mente come il problema della ‘segretaria-oca’. Una segretaria deve imbustare ed inviare n lettere ad altrettanti indirizzi differenti. Lei imbusta a caso senza controllare se ciascuna lettera è inserita nella busta con l’indirizzo corretto. Si chiede qual è la probabilità che almeno una lettera giunga ad un giusto destinatario. Per affrontare in modo corretto il problema occorre definire il concetto di permutazione e di punto fisso di una permutazione.
Definito un insieme A(a1, a2, …, an) di n elementi si definisce una permutazione di A una mappatura uno a uno di A con se stessa. Il numero di possibili permutazioni di un insieme di n elementi è dato da…
Np= n (n-1) (n-2)... 1 = n! [1]
Operare una permutazione significa in sostanza cambiare l’ordine della disposizione degli elementi di A in un qualsivoglia modo. Se in una particolare permutazione di A in una certa posizione i è presente lo stesso elemento [ossia se operare la permutazione non ha cambiato la disposizione dell’elemento in posizione i], allora l’elemento ai si dice occupare un punto fisso. In sostanza quindi il problema della ‘segretaria-oca’ si riduce al calcolo della probabilità che una permutazione casuale di A abbia almeno un punto fisso.
Per agevolare le cose consideriamo le possibili permutazioni di un insieme di n elementi senza punti fissi [che chiameremo riarrangiamenti] e indichiamo con Wn il loro numero. Evidentemente W1=0 e W2=1. Assumendo che sia n>=3 consideriamo l’insieme dei possibili riarrangiamenti degli elementi con indice compreso tra 1 e n. Se k è l’indice dell’elemento che occupa la posizione 1, allora è k diverso da 1 e l’elemento di indice 1 deve occupare un’altra posizione. Vi sono due possibilità, vale adire tale elemento è in posizione k o in una posizione diversa da k oltre che da 1. Nel primo caso in restanti n-2 elementi costituiscono un riarrangiamento di dimensione n-2 e il loro numero è per definizione Wn-2. Nel secondo caso l’insieme di elementi di indice [1,2,…, k-1, k+1,…, n] occupa le posizioni [2,3,…,n] e quindi è uno dei possibili Wn-1 riarrangiamenti di un insieme di n-1 elementi. Dal momento che abbiamo n-1 valori possibili di k possiamo concludere che…
Wn= (n-1) Wn-1 + (n-1) Wn-2 [2]
Siamo così di fronte ad una equazione alle differenze di secondo ordine con le due ‘condizioni iniziali’ W1=0 e W2=1. Per risolverla si può ricorrere al seguente artificio. Riscrivendo la [2] nel seguente modo…
Wn – n Wn-1 = - Wn-1 + (n-1) Wn-2 [3]
… e chiamando Dn la quantità Wn – n Wn-1 si ottiene l’equazione alle differenze del primo ordine…
Dn= - Dn-1 [4]
…la quale con la ‘condizione iniziale’ D2=1 ha soluzione Dn= (-1)^n.
Dal momento dunque che è…
Wi= i Wi-1 + (-1)^i [5]
… se indichiamo con Pi la probabilità di avere una permutazione di i elementi senza alcun punto fisso sarà Pi=Wi/i! e quindi…
Pi – Pi-1 = (-1)^i/i! [6]
Se sommiamo n-1 termini del tipo [6] per i che và da 2 a n e teniamo conto che P1=0 otteniamo alla fine…
Pn= ½! –1/3! +… +(-1)^n/n! [7]
… che è la probabilità di avere una permutazione di n elementi senza alcun punto fisso. La probabilità che almeno una delle lettere arrivi al giusto destinatario sarà alla fine pari a…
Po(n)= 1 – Pn = Sum [1>=i>=n] (-1)^(i-1)/i!
E’ interessante riportare i primi valori di Po(n)…
Po(1)=1
Po(2)=.5
Po(3)=.6666
Po(4)=.625
Po(5)=.6333
Po(6)=.6319
Po(7)=.6321
Po(8)=.6321
… come si vede per n>6 il valore di Po diviene sostanzialmente indipendente da n e la cosa non deve sorprendere se consideriamo che per n-> 00 la sommatoria, rapidamente convergente, tende a 1-1/e= .6321. Indubbiamente il risultato ottenuto desta una certa sorpresa poiché non è intuitivo [ci si sarebbe aspettati un comportamento crescente al crescere di n e che tendente a 1 per n grande]. Una dimostrazione classica del fatto che non sempre il buon senso e i risultati del calcolo delle probabilità coincidono.
cordiali saluti
lupo grigio
si tratta di un problema classico che io personalmente ho in mente come il problema della ‘segretaria-oca’. Una segretaria deve imbustare ed inviare n lettere ad altrettanti indirizzi differenti. Lei imbusta a caso senza controllare se ciascuna lettera è inserita nella busta con l’indirizzo corretto. Si chiede qual è la probabilità che almeno una lettera giunga ad un giusto destinatario. Per affrontare in modo corretto il problema occorre definire il concetto di permutazione e di punto fisso di una permutazione.
Definito un insieme A(a1, a2, …, an) di n elementi si definisce una permutazione di A una mappatura uno a uno di A con se stessa. Il numero di possibili permutazioni di un insieme di n elementi è dato da…
Np= n (n-1) (n-2)... 1 = n! [1]
Operare una permutazione significa in sostanza cambiare l’ordine della disposizione degli elementi di A in un qualsivoglia modo. Se in una particolare permutazione di A in una certa posizione i è presente lo stesso elemento [ossia se operare la permutazione non ha cambiato la disposizione dell’elemento in posizione i], allora l’elemento ai si dice occupare un punto fisso. In sostanza quindi il problema della ‘segretaria-oca’ si riduce al calcolo della probabilità che una permutazione casuale di A abbia almeno un punto fisso.
Per agevolare le cose consideriamo le possibili permutazioni di un insieme di n elementi senza punti fissi [che chiameremo riarrangiamenti] e indichiamo con Wn il loro numero. Evidentemente W1=0 e W2=1. Assumendo che sia n>=3 consideriamo l’insieme dei possibili riarrangiamenti degli elementi con indice compreso tra 1 e n. Se k è l’indice dell’elemento che occupa la posizione 1, allora è k diverso da 1 e l’elemento di indice 1 deve occupare un’altra posizione. Vi sono due possibilità, vale adire tale elemento è in posizione k o in una posizione diversa da k oltre che da 1. Nel primo caso in restanti n-2 elementi costituiscono un riarrangiamento di dimensione n-2 e il loro numero è per definizione Wn-2. Nel secondo caso l’insieme di elementi di indice [1,2,…, k-1, k+1,…, n] occupa le posizioni [2,3,…,n] e quindi è uno dei possibili Wn-1 riarrangiamenti di un insieme di n-1 elementi. Dal momento che abbiamo n-1 valori possibili di k possiamo concludere che…
Wn= (n-1) Wn-1 + (n-1) Wn-2 [2]
Siamo così di fronte ad una equazione alle differenze di secondo ordine con le due ‘condizioni iniziali’ W1=0 e W2=1. Per risolverla si può ricorrere al seguente artificio. Riscrivendo la [2] nel seguente modo…
Wn – n Wn-1 = - Wn-1 + (n-1) Wn-2 [3]
… e chiamando Dn la quantità Wn – n Wn-1 si ottiene l’equazione alle differenze del primo ordine…
Dn= - Dn-1 [4]
…la quale con la ‘condizione iniziale’ D2=1 ha soluzione Dn= (-1)^n.
Dal momento dunque che è…
Wi= i Wi-1 + (-1)^i [5]
… se indichiamo con Pi la probabilità di avere una permutazione di i elementi senza alcun punto fisso sarà Pi=Wi/i! e quindi…
Pi – Pi-1 = (-1)^i/i! [6]
Se sommiamo n-1 termini del tipo [6] per i che và da 2 a n e teniamo conto che P1=0 otteniamo alla fine…
Pn= ½! –1/3! +… +(-1)^n/n! [7]
… che è la probabilità di avere una permutazione di n elementi senza alcun punto fisso. La probabilità che almeno una delle lettere arrivi al giusto destinatario sarà alla fine pari a…
Po(n)= 1 – Pn = Sum [1>=i>=n] (-1)^(i-1)/i!
E’ interessante riportare i primi valori di Po(n)…
Po(1)=1
Po(2)=.5
Po(3)=.6666
Po(4)=.625
Po(5)=.6333
Po(6)=.6319
Po(7)=.6321
Po(8)=.6321
… come si vede per n>6 il valore di Po diviene sostanzialmente indipendente da n e la cosa non deve sorprendere se consideriamo che per n-> 00 la sommatoria
, rapidamente convergente, tende a 1-1/e= .6321. Indubbiamente il risultato ottenuto desta una certa sorpresa poiché non è intuitivo [ci si sarebbe aspettati un comportamento crescente al crescere di n e che tendente a 1 per n grande]. Una dimostrazione classica del fatto che non sempre il buon senso e i risultati del calcolo delle probabilità coincidono. cordiali saluti
lupo grigio
Bella dimostrazione! Fantastico! Grande!
Io mi ero sempre fermato (circa) a Wn= (n-1) Wn-1 + (n-1) Wn-2 e mi sono arenato più volte (conoscevo un problema simile da un po' di tempo). Insistevo per arrivare direttamente al fattoriale, mentre trovavo sempre formule nelle quali era necessario calcolare prima il valore per n-1 (Wn-1 nel nostro caso).
Io mi ero sempre fermato (circa) a Wn= (n-1) Wn-1 + (n-1) Wn-2 e mi sono arenato più volte (conoscevo un problema simile da un po' di tempo). Insistevo per arrivare direttamente al fattoriale, mentre trovavo sempre formule nelle quali era necessario calcolare prima il valore per n-1 (Wn-1 nel nostro caso).
Lupo grigio,WonderP ha gia' detto tutto ed io ne condivido
totalmente l'apprezzamento per la tua soluzione.
Spero di poter postare anche la mia soluzione...quando avro'
capito quello che c'e' scritto nel testo da cui ho tratto
il quesito!!
Ricambio i saluti.
karl.
totalmente l'apprezzamento per la tua soluzione.
Spero di poter postare anche la mia soluzione...quando avro'
capito quello che c'e' scritto nel testo da cui ho tratto
il quesito!!
Ricambio i saluti.
karl.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo