Classico: problema dei compleanni

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Classico: problema dei compleanni

Messaggio da Claudio. »

(Ho controllato tra le discussioni passati mi pare non ci sia)
Qual è la probabilità che tra $n$ persone almeno $k$ facciano il compleanno lo stesso giorno?
nic.h.97
Messaggi: 195
Iscritto il: 19 giu 2012, 19:24

Re: Classico: problema dei compleanni

Messaggio da nic.h.97 »

con $ n $ persone , la probabilita' che $ k=n $ persone compiano gli anni lo stesso giorno è di $ \frac {1}{365^{n-1}} $

poi con $ k=n-1 $
$ n*\frac{1}{365^{n-2}} $

poi con $ k=n-v $

$ (qualcosa)*\frac{1}{365^{n-v-1}} $

qualcosa= cioè in quanti modi posso scegliere x oggetti ordinatamente su n oggetti.....
scommetto che servono i coefficienti binomiali , pero' non li so usare perchè non li ho ancora capiti...
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

Quello che dici tu sarebbe $\displaystyle \binom{n}{k}\cdot\frac1{365^{k-1}}$, ma non è così in ogni caso...questa non è neanche sempre minore di 1...
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Classico: problema dei compleanni

Messaggio da auron95 »

Sarebbe molto più semplice se il testo chiedesse "nate tutte il primo gennaio", in tal caso sarebbe se non erro $ \displaystyle \sum_{i=k}^n \binom{n}{i}\frac{364^{n-i}}{365^n} $.
Il problema è che non basta moltiplicare per 365 potrebbero esserci combinazioni per cui k persone compiono gli anni un giorno e altre k in un altro, che verrebbero contate più volte. Non so se si possano togliere (qualcosa del tipo inclusione-esclusione) e ottenere un'espressione decente.......
This is it. This is your story. It all begins here.
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

Preciso che non conosco la soluzione, ma sto iniziando a pensare che non sia esprimibile in maniera umana...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Classico: problema dei compleanni

Messaggio da jordan »

Da notare che se $n \ge 366k+1$ (considerando anche i bisestili) allora dovrebbe fare $1$ :roll:
The only goal of science is the honor of the human spirit.
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

jordan ha scritto:Da notare che se $n \ge 366k+1$ (considerando anche i bisestili) allora dovrebbe fare $1$ :roll:
A me sembra sia $366(k-1)+1$...
Comunque alla fine si riduce a dover calcolare una combinazione generalizzata, ne senso che hai $n$ tipologie di oggetti in quantità finite $\{q_1,q_2,\cdots,q_n\}$ e bisogna calcolare quante combinazioni di $k\le\sum q_i$ elementi esistono.
Quindi non credo si possa esprimere con una formula generale...è vero che in questo caso $q_1=q_2=\cdots=q_n$ però non credo che la cosa cambi.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Classico: problema dei compleanni

Messaggio da jordan »

Claudio. ha scritto:A me sembra sia $366(k-1)+1$...
Si', è giusto; a mia discolpa, $366k+1$ resta in ogni caso una condizione sufficiente :)
The only goal of science is the honor of the human spirit.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico: problema dei compleanni

Messaggio da Gottinger95 »

Sia \(p_{n,k}\) la probabilità in questione. Sia inoltre \(A_{n,k}\) il numero di combinazioni in cui almeno k persone fanno il compleanno lo stesso giorno in un gruppo di n persone. Naturalmente vale (1):
\(\displaystyle p_{n,k} = \frac{A_{n,k}}{365^n}\)

Immagino di aggiungere un'altra persona e vedere come cambia \(A_{n+1}\):
1. Se già nelle n persone avevo almeno k persone che facevano il compleanno lo stesso giorno, allora me ne strafotto di che giorno compie gli anni il nuovo arrivato;
2. Se invece avevo solo k-1 persone fortunate con lo stesso compleanno tra le n di prima, allora me ne frega eccome e costringo il tizio a cambiare giorno di compleanno in quello che voglio io (evviva il conformismo).

Dunque ho:
\(\displaystyle A_{n,k} = 365 A_{n-1,k} + A_{n-1,k-1}\)
Usando la (1):
\(\displaystyle 365^n p_{n,k} = 365 \cdot 365^{n-1} p_{n-1,k} + 365^{n-1} p_{n-1,k-1}\)

Da cui, dividendo per \(365^n\):

\(\displaystyle p_{n,k} = p_{n-1,k} + \frac{1}{365}p_{n-1,k-1}\)

Che si può scrivere più artisticamente come:

\(\displaystyle p_{n,k} = p_{n-1,k} + \frac{1}{365}( p_{n-2,k-1} + \frac{1}{365}(\ldots \frac{1}{365}(p_{n-j,\ k-j+1} +\frac{1}{365}(\ldots \frac{1}{365}(p_{n-k+1,1})\ldots)) \)

Purtroppo devo andare a nanna, ma spero che questa idea funzioni! Domani provo a continuare :D
Ultima modifica di Gottinger95 il 02 dic 2012, 15:15, modificato 1 volta in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

Se con combinazioni intendi davvero combinazioni, allora la probabilità cercata dovrebbe essere $\displaystyle \frac{A_{n,k}}{\binom{365+n-1}{n}}$
Comunque quel problema lì, di calcolare la combinazioni sotto un limite di quantità di palline l'ho incontrato un po' di volte e non sono mai riuscito a tirarci fuori una formula ^^ non per scoraggiare, comunque vediamo.
Non ho capito bene quelle relazioni, ma è tardi domani ricontrollo in ogni caso ti scrivo come avevo provato io e l'errore che commettevo.
Io io avevo cercato di determinare $P_e$ come la probabilità che esattamente k persone facessero il compleanno, così per eliminarmi l'almeno, e poi ovviamente l'almeno diventava $1-\sum_1^{k-1}P_e$. Adesso l'errore che facevo stava nel pensare a $P_e$ come la probabilità che ci fosse un solo gruppo di $k$ persone che facessero il compleanno in uno stesso giorno, cosa che rende facile il calcolo. In realtà $P_e$ è la probabilità che esista almeno un gruppo di $k$ persone ma nessuno di $k+1$. A questo punto calcolare $P_e$ non è più così conveniente :mrgreen:
Altra cosa, nota che $P_{2,n}$ si calcola facilmente ragionando come sopra.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico: problema dei compleanni

Messaggio da Gottinger95 »

Per comodità tipografica sia \(\alpha = \frac{1}{365}\). L'ultima legge si trasforma, moltiplicando per tutti gli alfa, in:
\(p_{n,k} = p_{n-1,k} + \alpha p_{n-2,k-1} + \alpha^{2}p_{n-3, k-2} + \ldots + \alpha^{k-1}p_{n-k,1} = \)
\(\displaystyle \ \ \ \ \ = \sum_{j=0}^{k-1}{\alpha^{j}p_{n-j-1,k-j}}\)

Continuiamo ad applicare la legge ricorsiva appena ottenuta su ogni termine della legge ricorsiva stessa, per cercare di "abbattere" la ricorsione e arrivare a una forma pulita.
Per capire cosa viene fuori, procediamo in questo modo: scriviamo la legge ricorsiva in colonna e - a destra di ogni termine - scriviamo la sua ricorrenza. Spero di essermi spiegato.
\( p_{n, k} = \)
\( p_{n-1,k} = p_{n-2,k} + \alpha p_{n-3,k-1} + \alpha^{2}p_{n-4,k-2} + \ldots + \alpha^{k-1}p_{n-k-1,1} \)
+
\(\alpha p_{n-2,k-1} = \alpha p_{n-3,k-1} + \alpha^{2}p_{n-4,k-2} + \ldots + \alpha^{k-1}p_{n-k-1,1} \)
+
\(\vdots\)
+

+
\(\alpha^{k-1}p_{n-k,1} = \alpha^{k-1}p_{n-k-1,1}\)

Toh guarda, per un incredibile colpo di fortuna (che si può in formalmente dimostrare in modo semplice, ma non mi va di impelagarmi in mille lettere con latex) molti termini sono uguali! La ricorrenza risulta:
\(\displaystyle p_{n,k} = \sum_{j=0}^{k-1}{(j+1)\alpha^{j}p_{n-j-2,k-j)}}\)

Notiamo che il numero di termini non è variato, questo fa molto piacere, ma allo stesso tempo il primo indice del primo termine è diminuito di 1. Scriveremo adesso la generalizzazione di questo "passo", che dovrebbe portare ad esplicitare il risultato. Riassumiamo ciò che abbiamo fatto fino ad adesso:

PASSO 1: \( \displaystyle p_{n,k}= \sum_{j=0}^{k - 1}{\alpha^{j}p_{n-j-1,k-j}} = \sum_{j=0}^{k-1}{\binom{j}{0}\alpha^{j}p_{n-j-1,k-j}}\)
PASSO 2: \(\displaystyle p_{n,k} = \sum_{j=0}^{k-1}{(j+1)\alpha^{j}p_{n-j-2,k-j)}} = \sum_{j=0}^{k-1}{\binom{j+1}{1}\alpha^{j}p_{n-j-2,k-j)}}\)

Senza rifare la tabellina, cerchiamo di capire come sarà l'andamento al prossimo passo. Ricordiamoci inoltre della legge ricorsiva dei binomiali:
\( \binom{j}{j} + \ldots + \binom{j+h}{j} = \binom{j+h+1}{j+1} \)
I termini uguali si raccoglieranno allo stesso modo, e sommeremo i binomiali: il j-esimo termine (ricordiamoci che j parte da 0) al passo H avrà come coefficiente la somma dei (j+1) binomiali del (H-1)-esimo passo. Se non mi sono spiegato bene, uno schema fatto alla stregua di quello precedente è ben più esplicativo di me :) Fatto sta che si vede/dimostra facilmente il seguente fatto:

Passo h: \( \displaystyle p_{n,k} = \sum_{j=0}^{k-1}{\binom{j+h}{h} \alpha^{j} p_{n-j-h-1, k - j}}\)

Adesso ci chiediamo: quanti "passi" vogliamo fare? Notiamo che il primo indice diminuisce, mentre il secondo rimane fermo. Fino a quando può scendere n, ossia il numero di persone? Di certo non può essere inferiore di k, il numero di persone che vorremmo fossero nate lo stesso giorno, per una questione concettuale (che faccio, scelgo 7 persone tra 4? Mmm...). Dunque, ci piacerebbe di far diventare i due indici (ossia le persone presenti e le persone nate lo stesso giorno) uguali, che è un caso limite. A questo proposito arriviamo fino al passo con \(h= n-k-1\) e ottengo:

\( \displaystyle p_{n,k} = \sum_{j=0}^{k-1}{\binom{j+n-k-1}{n-k-1} \alpha^{j} p_{k-j, k - j}}\)

Adesso noto che \(p_{n,n} = \alpha^{n-1}\): infatti il primo lo scelgo come mi pare, mentre gli altri hanno una probabilità alfa di capitare lo stesso giorno.
La legge diventa:
\( \displaystyle p_{n,k} = \sum_{j=0}^{k-1}{\binom{j+n-k-1}{n-k-1} \alpha^{j} \alpha^{k-j-1}} = \sum_{j=0}^{k-1}{\binom{j+n-k-1}{n-k-1} \alpha^{k-1}} \)

Sfruttiamo ancora la legge ricorsiva dei binomiali e portiamo fuori alfa, che è diventato indipendente dalla sommatoria:
\( \displaystyle p_{n,k} = \alpha^{k-1} \sum_{j=0}^{k-1}{\binom{j+n-k-1}{n-k-1}} = \alpha^{k-1} \binom{n-1}{n-k} = \alpha^{k-1} \binom{n-1}{(n-1) -(n-k)} = \alpha^{k-1} \binom{n-1}{k-1} = \frac{\binom{n-1}{k-1}}{365^{k-1}}\),

che è una formula esplicita per la probabilità richiesta.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

Non ho controllato i calcoli ma c'è qualcosa che non va. Dalla tua formula viene $\displaystyle p_{n,2}=\frac{n-1}{365}$ e non è proprio così...hai letto il mio messaggio precedente?
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Classico: problema dei compleanni

Messaggio da Gottinger95 »

Sono convintissimo che ci sia qualcosa che non va nel risultato finale, anche perchè non è sempre minore di 1, ma non riesco a trovare l'errore! Per questo l'ho sottoposta alla vostra attenzione, magari riusciamo ad aggiustarla insieme :) Comunque si, ho letto il tuo messaggio di prima!

Ah, per combinazioni non intendevo davvero combinazioni, ma piuttosto "configurazioni", cioè con una connotazione piuttosto generale.
Dai che se troviamo l'errore (e riusciamo a rimediare) è fattaa!!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Classico: problema dei compleanni

Messaggio da Claudio. »

Il fatto che non sia sempre minore di 1 non c'entra, infatti è normale che se ci sono più di 365 persone la probabilità è ovviamente 1, quindi in alcuni casi la formula non vale.
Secondo me il tuo errore non è in quest'ultimo post nei calcoli, ma un errore concettuale nelle uguaglianze che hai scritto nel post prima, domani guardo meglio.
Comunque ti propongo questo problema, abbiamo $365\cdot x$ palline di $365$ colori diversi, $x$ palline per ogni colore, in quanti modi diversi possiamo prendere $y$ palline?
Questo problema è equivalente al nostro, e la vedo dura tirarci fuori una formula...
Rispondi