Mendula & Nuxedda

[franco]

Bachisio ama molto i cioccolatini alla mandorla prodotti dalla ditta "Mendula & Nuxedda" che sono venduti in confezioni che comprendono N cioccolatini alla mandorla e altrettanti alla nocciola.
Bachisio non sopporta i cioccolatini alla nocciola.
Quando acquista una confezione, mette tutti i cioccolatini in un sacchetto e ogni giorno ne estrae solo uno: se è alla mandorla lo mangia, se è alla nocciola lo rimette nel sacchetto.
Quando ha finito i cioccolatini alla mandorla, regala quelli alla nocciola alla sorella Bonaria e compra una nuova confezione.

Determinare il valore di N sapendo che mediamente Bachisio compra una nuova confezione "Mendula & Nuxedda" ogni 30 giorni (valore arrotondato all'intero più vicino ...).



diophante.fr G189

[panurgo]

$6$

[franco]

$6$

Io avrei detto $8$
ma probabilmente mi sbaglio ...

[Gianfranco]

Se ci sono 6 mandorle e 6 nocciole, il tempo medio di attesa per ottenere la prima mandorla è:
$t=\frac{12}{6}=2$ giorni (l'inverso della probabilità)

Poi ci sono 5 mandorle e 6 nocciole, quindi il tempo medio di attesa per la prossima mandorla è altri:
t=11/5 giorni

In tutto fanno:
12/6+11/5=21/5 giorni

In generale, se ci sono m mandorle e n nocciole, il tempo medio di attesa per la prossima mandorla è:
$t=\frac{m+n}{m}$

Andando avanti così, il tempo di attesa medio per finire le mandorle è:
12/6+11/5+10/4+9/3+8/2+7/1=207/10=21 giorni circa.

Estendiamo.
Se partiamo con un sacchetto contenente n mandorle e n nocciole, il tempo medio atteso per finire le mandorle è:

$t=\sum_{i=0}^{n-1}{\left. \frac{2 n-i}{n-i}\right.}$

Sapendo che il tempo atteso è 30 giorni, dovremmo risolvere l'equazione:

$\sum_{i=0}^{n-1}{\left. \frac{2 n-i}{n-i}\right.}=30$ circa

nell'incognita n.

Non so come si fa, perciò per tentativi l'engineer che è in me trova che n=8 va bene.

Domanda: bisogna arrotondare all'intero il numero medio dei giorni attesi di volta in volta oppure alla fine della sommatoria?
Ecco il programmino BASIC per la verifica.

Codice: Seleziona tutto

LET n=8
LET g=0
PRINT "mandorle:";n-i; "nocciole: ";n; "giorni passati"; g

FOR i=0 TO n-1
   LET g=g+(2*n-i)/(n-i)
   PRINT "mandorle:";n-i-1; "nocciole: ";n; "giorni passati"; g   
NEXT I

END

[franco]

Se ci sono 6 mandorle e 6 nocciole, ...

Sono praticamente gli stessi ragionamenti che avevo fatto io anche se poi la formulazione che avevo ricavato era leggermente diversa (ma equivalente):
$T=\sum_{i=1}^{N}{\left. \frac{N+i}{i}\right.}=N+\sum_{i=1}^{N}{\left. \frac{N}{i}\right.}$

Anche io non sono in grado di risolvere analiticamente la sommatoria ma con excel è piuttosto semplice fare i conti e trovare che per $N=8$ risulta $T=29,74286... $.

Con $N=6$ invece mi risulterebbe $T=20,7$.


ciao

[panurgo]

Non so neppure io perché ho scritto $6$: gli ultimi post sono stati laconici perché inviati da smartphone...

Come dice giustamente Gianfranco, l’expectation di un processo con probabilità di uscita $p$ è $1/p$.

AaA_fig1.png (2.88 KiB) Visto 9817 volte

La dimostrazione è come segue: la probabilità di uscire al primo tentativo è $p$, la probabilità di uscire al secondo tentativo è $qp$ (con $q=1-p$), la probabilità di uscire al $k$-esimo tentaivo è $q^{k-1}p$ quindi

$\displaystyle \left\langle r \middle|\top\right\rangle=1\cdot p+2\cdot qp+3\cdot q^2p+\ldots=p\cdot\sum_{r=1}^\infty{r q^{r-1}}$

Per trovare la forma chiusa della sommatoria osserviamo che

$\displaystyle \sum_{r=1}^\infty{r q^{r-1}}=\sum_{r=0}^\infty{r q^{r-1}}=\sum_{r=0}^\infty{\frac{d}{dq} q^r}=\frac{d}{dq}\sum_{r=0}^\infty{q^r }=\frac{d}{dq}\frac1{1-q}=\frac1{\left(1-q\right)^2}=\frac1{p^2}$

Sostituendo questo risultato nel calcolo dell’expectation otteniamo

$\displaystyle \left\langle r \middle|\top\right\rangle=p\cdot\frac1{p^2}=\frac1p$

Q.E.D.

Il processo complessivo è rappresentato in figura

AaA_fig2.png (4.04 KiB) Visto 9817 volte

la probabilità di uscita vale

$\displaystyle \Pr\left(k\to k+1\middle|n\wedge k\wedge\top\right)=\frac{n-k}{2n-k}\qquad 0\leq k\leq n-1$

e l’expectation vale

$\displaystyle \left\langle k\to k+1\middle|n\wedge k\wedge\top\right\rangle=\frac{2n-k}{n-k}\qquad 0\leq k\leq n-1$

L’expectation del processo complessivo è

$\displaystyle \left\langle 1\to n\middle|n\wedge\top\right\rangle=\sum_{k=0}^{n-1}\frac{2n-k}{n-k}=\sum_{k=1}^n\frac{n+k}k=n+nH_n$

dove $H_n=\sum_{k=1}^n\frac1k$ è la somma parziale della serie armonica per la quale, purtroppo, non esiste una forma chiusa: si può usare un foglio di calcolo oppure, per i puristi, a mano

$\begin{array}{|l|l|l|C}
\hline
n & \text{formula} & \text{valore} \\
\hline
\displaystyle n=1 &\displaystyle \frac{n}{1}+1 &\displaystyle \frac{1}{1}+1=2\\
\hline
\displaystyle n=2 &\displaystyle \frac{n}{1}+1+\frac{n}{2}+1=\frac{3n}2+2 &\displaystyle \frac{3}{1}+2=5\\
\hline
\displaystyle n=3 &\displaystyle \frac{3n}2+2+\frac{n}{3}+1=\frac{11n}6+3 &\displaystyle \frac{11}{2}+3=8,5 \\
\hline
\displaystyle n=4 &\displaystyle \frac{11n}6+3 +\frac{n}{4}+1=\frac{25n}{12}+4 &\displaystyle \frac{25}{3}+4=12,3\ldots \\
\hline
\displaystyle n=5 &\displaystyle \frac{25n}{12}+4 +\frac{n}{5}+1=\frac{137n}{60}+5 &\displaystyle \frac{137}{12}+5=16,4\ldots \\
\hline
\displaystyle n=6 &\displaystyle \frac{137n}{60}+5 +\frac{n}{6}+1=\frac{49n}{20}+6 &\displaystyle \frac{147}{10}+6=20,7 \\
\hline
\displaystyle n=7 &\displaystyle \frac{49n}{20}+6 +\frac{n}{7}+1=\frac{363n}{140}+7 &\displaystyle \frac{363}{20}+7=25,1\ldots \\
\hline
\displaystyle n=8 &\displaystyle \frac{363n}{140}+7 +\frac{n}{8}+1=\frac{761n}{280}+8 &\displaystyle \frac{761}{35}+8=29,7\ldots \\
\hline
\displaystyle n=9 &\displaystyle \frac{761n}{280}+8 +\frac{n}{9}+1=\frac{7129n}{2520}+9 &\displaystyle \frac{7129}{280}+9=34,4\ldots \\
\hline
\end{array}$

ergo, $n=8$.

[franco]

Non so neppure io perché ho scritto $6$ ...

Grazie Guido,
Come sempre sei un po' criptico per le mie competenze ma ogni volta imparo qualcosa

-----------------------

Questo problema, come ho indicato in coda al post originario, è tradotto (con adattamenti per ambientarlo in Sardegna) dal sito francese diophante.fr
Nel testo originale il protagonista era Pierre e al posto dei cioccolatini c'erano le mirabelle.
Stavolta, preso com'ero dall'adattamento, ho però fatto un errore nella traduzione, errore che ho scoperto quando sono andato a confrontare la mia soluzione con quella degli amici transalpini.

In realtà Bachisio è molto più goloso!
Ogni giorno prende dal sacchetto $3$ cioccolatini, mangia quelli alla mandorla e rimette dentro quelli alla nocciola.
Anche in questo caso passano in media 30 giorni fra l'acquisto delle confezioni M&N ma evidentemente i cioccolatini in ogni pacco sono ben più di 8 e trovare la soluzione è abbastanza più complicato.
Chi vuole cimentarsi nella prova è il benvenuto.


N.B. i 3 cioccolatini sono presi tutti assieme e non uno per volta!

-----------------------

O.T.
Come probabilmente avrete intuito, in Sardo mendula significa mandorla e nuxedda significa nocciola

[panurgo]

Ovviamente, questo processo è molto più complicato del precedente.

Per intenderci, con $N = 4$ il processo ha cinque stati: lo stato $0$, con $4$ cioccolatini alla mandorla, lo stato $1$, con $3$ cioccolatini alla mandorla, e così fino allo stato $4$, con $0$ cioccolatini alla mandorla. Il processo in cui viene pescato un cioccolatino a caso è rappresentato dal grafo

m&n2_001.png (16.57 KiB) Visto 9771 volte

che evidenzia come sia possibile trattare separatamente i singoli passi. Ciò non è più possibile quando si prendono tre cioccolatini per volta, come esemplificato da grafo

m&n2_002.png (21.13 KiB) Visto 9771 volte

Anche la misura della probabilità è più complicata.

Supponiamo di avere un'urna contenente $B$ palline bianche e $R$ palline rosse: in quanti modi possiamo pescare $b$ palline bianche e $r$ rosse?
Vi sono $B \choose b$ modi di pescare le palline bianche, $R \choose r$ di pescare le palline rosse e ${B+R} \choose {b+r}$ di pescare quel numero totale di palline: assegniamo come valore di probabilità la frequenza

$\displaystyle \text{Pr}\left(a\wedge b\middle|A\wedge B\wedge\top\right)=\frac{{B\choose b} {R\choose r}}{{B+R}\choose{b+r}}$

Il nome tecnico di questa distribuzione è distribuzione ipergeometrica: nel caso del processo di cui sopra abbiamo, in uscita dallo stato $0$, le probabilità

$\begin{array}{lC}
\displaystyle \frac{{4\choose 0} {4\choose 3}}{8\choose 3}=\frac{4}{56} & \displaystyle \frac{{4\choose 1} {4\choose 2}}{8\choose 3}=\frac{24}{56} & \displaystyle \frac{{4\choose 2} {4\choose 1}}{8\choose 3}=\frac{24}{56} & \displaystyle \frac{{4\choose 3} {4\choose 0}}{8\choose 3}=\frac{4}{56}
\end{array}$

in uscita dallo stato $1$, le probabilità

$\begin{array}{lC}
\displaystyle \frac{{3\choose 0} {4\choose 3}}{7\choose 3}=\frac{4}{35} & \displaystyle \frac{{3\choose 1} {4\choose 2}}{7\choose 3}=\frac{18}{35} & \displaystyle \frac{{3\choose 2} {4\choose 1}}{7\choose 3}=\frac{12}{35} & \displaystyle \frac{{3\choose 3} {4\choose 0}}{7\choose 3}=\frac{1}{35}
\end{array}$

in uscita dallo stato $2$, le probabilità

$\begin{array}{lC}
\displaystyle \frac{{2\choose 0} {4\choose 3}}{6\choose 3}=\frac{1}{5} & \displaystyle \frac{{2\choose 1} {4\choose 2}}{6\choose 3}=\frac{3}{5} & \displaystyle \frac{{2\choose 2} {4\choose 1}}{6\choose 3}=\frac{1}{5} &
\end{array}$

in uscita dallo stato $3$, le probabilità

$\begin{array}{lC}
\displaystyle \frac{{1\choose 0} {4\choose 3}}{5\choose 3}=\frac{2}{5} & \displaystyle \frac{{1\choose 1} {4\choose 2}}{5\choose 3}=\frac{3}{5} & &
\end{array}$

ed infine, per lo stato $4$, la probabilità vale

$\displaystyle \frac{{0\choose 0} {4\choose 3}}{4\choose 3}=1$

cioè, una volta arrivati a $4$ siamo certi di rimanervi: è quello che si chiama uno stato assorbente.

Il resto alla prossima puntata

[Gianfranco]

Panurgo, ovvero Guido (giusto?),ti ringrazio di cuore per tutte le soluzioni così dettagliate che invii al Forum. Dietro c'è un lavoro notevole.
Personalmente sto imparando un sacco di cose sulla teoria (e pratica) della probabilità. E' uno stimolo a fare passi avanti.
Bacio le mani in ginocchio!

[panurgo]

La seconda puntata ci serve per capire cosa ce ne facciamo di queste probabilità. Per far ciò osserviamo prima un processo alquanto più semplice: il lancio di una moneta fino a che non esce testa, rappresentato dal grafo in figura.

m&n03.001.png (3.99 KiB) Visto 9715 volte

Gli stati $0$ e $1$ sono descritti rispettivamente dalle proposizioni

$\displaystyle\overline{H}\equiv\text{non è ancora uscito testa}$

e

$\displaystyle H\equiv\text{è già uscito testa}$

Fin che siamo nello stato $0$, la probabilità di passare dallo stato $0$ allo stato $1$ e quella di rimanere nello stato $0$ sono uguali a $\frac12$: formalmente

$\displaystyle\text{Pr}\left(\overline{H}\to\overline{H}\middle|\top\right)=\text{Pr}\left(\overline{H}\to H\middle|\top\right)=\frac12$

Viceversa, quando siamo nello stato $1$, non è possibile tornare allo stato $0$ quindi

$\displaystyle\text{Pr}\left(H\to\overline{H}\middle|\top\right)=0\\\text{Pr}\left(H\to H\middle|\top\right)=1$

Organizziamo questi numeri in una matrice $2\times 2$

$\displaystyle T=\frac12\left(\begin{array}{cC}1 & 0 \\ 1 & 2 \end{array}\right)$

Prima dell’inizio del processo è vera la proposizione $\overline{H}$ mentre la proposizione $h$ è falsa: modelliamo la situazione con un vettore colonna contenente le due probabilità, $1$ per vero e $0$ per falso

$\displaystyle y_0=\left(\begin{array}{cC} 1\\0\end{array}\right)$


dove l’indice $0$ del vettore corrisponde al numero di passi effettuati.
Per calcolare le probabilità delle due proposizioni dopo il primo passo non ci resta che moltiplicare $T$ per $y_0$

$\displaystyle y_1=T\,y_0=\frac12\left(\begin{array}{cC}1 & 0 \\ 1 & 2 \end{array}\right) \left(\begin{array}{cC} 1\\0\end{array}\right)=\frac12\left(\begin{array}{cC} 1\\1\end{array}\right)$

Analogamente, per il secondo passo,

$\displaystyle y_2=T\,y_1=\frac12\left(\begin{array}{cC}1 & 0 \\ 1 & 2 \end{array}\right)\frac12\left(\begin{array}{cC} 1\\1\end{array}\right)=\frac14\left(\begin{array}{cC} 1\\3\end{array}\right)$

e, per il terzo,

$\displaystyle y_3=T\,y_2=\frac12\left(\begin{array}{cC}1 & 0 \\ 1 & 2 \end{array}\right)\frac14\left(\begin{array}{cC} 1\\3\end{array}\right)=\frac18\left(\begin{array}{cC} 1\\7\end{array}\right)$

Per un numero generico $r$ di passi avremo

$\displaystyle y_r=T\,y_{r-1}=T\left(Ty_{r-2}\right)=T^2 y_{r-2}=\cdots=T^r y_0$

Dobbiamo dunque calcolare la potenza di una matrice quadrata. A tale scopo dobbiamo effettuare (quella che ho scoperto recentemente chiamarsi) la decomposizione spettrale della matrice.

Alla prossima puntata

[panurgo]

Terza puntata (scusate il ritardo )

Io l’avevo sempre chiamata “diagonalizzazione” ma ho scoperto che non c’è un solo modo di diagonalizzare una matrice quindi ben venga la decomposizione spettrale (forse sarebbe più corretto “scomposizione”).
Ma perché diagonalizzare? Osserviamo cosa succede quando facciamo il quadrato di una matrice

$A^2=\left(\begin{array}{ccCC}a_{00} & a_{01} \\ a_{10} & a_{11}\end{array}\right) \left(\begin{array}{ccCC}a_{00} & a_{01} \\ a_{10} & a_{11}\end{array}\right)= \left(\begin{array}{ccCC} \left(\begin{array}{cC}a_{00} & a_{01} \end{array}\right) \left(\begin{array}{cC}a_{00} \\ a_{10} \end{array}\right) & \left(\begin{array}{cC}a_{00} & a_{01} \end{array}\right) \left(\begin{array}{cC}a_{01} \\ a_{11}\end{array}\right) \\ \left(\begin{array}{cC}a_{11}\end{array}\right) \left(\begin{array}{cC}a_{00} \\ a_{10} \end{array}\right) & \left(\begin{array}{cC}a_{11}\end{array}\right) \left(\begin{array}{cC} a_{01} \\ a_{11}\end{array}\right) \end{array}\right)=\left(\begin{array}{cC}a_{00}^2+a_{01}a_{10} & a_{00}a_{01}+a_{01}a_{11} \\ a_{00}a_{10}+a_{10}a_{11} & a_{01}a_{10}+a_{11}^2\end{array}\right)$

Osserviamo ora cosa succede quando facciamo il quadrato di una matrice diagonale, $\Lambda=\text{diag}\left\{\lambda_k\right\}$

$\Lambda^2=\left(\begin{array}{cC}\lambda_0 & 0 \\ 0 & \lambda_1\end{array}\right) \left(\begin{array}{cC}\lambda_0 & 0 \\ 0 & \lambda_1\end{array}\right)= \left(\begin{array}{cC}\left(\begin{array}{cC}\lambda_0 & 0 \end{array}\right) \left(\begin{array}{cC}\lambda_0 \\ 0 \end{array}\right) & \left(\begin{array}{cC}\lambda_0 & 0\end{array}\right) \left(\begin{array}{cC} 0 \\ \lambda_1\end{array}\right) \\ \left(\begin{array}{cC}0 & \lambda_1\end{array}\right) \left(\begin{array}{cC}\lambda_0 \\ 0\end{array}\right) & \left(\begin{array}{cC}0 & \lambda_1\end{array}\right) \left(\begin{array}{cC} 0 \\ \lambda_1\end{array}\right)\end{array}\right)= \left(\begin{array}{cC}\lambda_0^2 & 0 \\ 0 & \lambda_1^2\end{array}\right)$

Applicando la definizione di potenza ricaviamo che $\Lambda^r=\text{diag}\left\{\lambda_k^r\right\}$ e, se possiamo trovare una trasformazione che dia $\Lambda=F\left(T\right)$, possiamo usare la sua inversa per ottenere $T^r=F^{-1}\left(\Lambda^r\right)=F^{-1}\left(\text{diag}\left\{\lambda_k^r\right\}\right)$.

Come si fa la decomposizione spettrale?

Per prima cosa si scrive l’equazione caratteristica, $\left|T-\lambda I\right|=0$ dove $I=\text{diag}\left\{1,\ldots,1\right\}$ è la matrice unitaria, elemento neutro della moltiplicazione di matrici.
In pratica, questa equazione si ottiene eguagliando a zero il determinante della matrice $T$ alla cui diagonale principale viene sottratta la variabile $\lambda$: ne risulta un polinomio in $\lambda$ equagliato a zero

$\displaystyle\left|T-\lambda I\right|=\left|\begin{array}{cC}\frac12-\lambda & 0 \\ \frac12 & 1-\lambda\end{array}\right|=\left(\frac12-\lambda\right)\left(1-\lambda\right)-1\cdot 0=0$

le cui soluzioni, $\lambda=\left\{\frac12,1\right\}$, vengono definite “autovalori” della matrice.

La seconda cosa che si fa è la ricerca degli “autovettori”, vettori colonna (come li scrivo io) tali che

$\displaystyle\left(T-\lambda_k I\right)\cdot\nu_k=0$

Questo è un sistema di equazioni lineari omogeneo che, come noto, ammette soluzioni solo se il determinante della matrice dei coefficienti è nullo: ma noi sappiamo che i valori di $\lambda$ sono precisamente quelli che annullano il determinante (gli autovalori). E, se gli autovalori sono tutti distinti, non vi sono problemi: esiste un autovettore per ogni autovalore.
Con il nostro esempio

$\displaystyle \lambda = \frac12\quad\Longrightarrow\quad\frac12\left(\begin{array}{cC}0 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{cC}a \\ b\end{array}\right) = \left(\begin{array}{cC}0 \\ 0\end{array}\right) \quad\Longrightarrow\quad\left\{\begin{array}{lC}0a+0b=0 \\ a+b=0\end{array}\right.
\quad\Longrightarrow\quad b = -a\quad\Longrightarrow\quad \nu_0 = \left(\begin{array}{cC}-1 \\ 1\end{array}\right)$

e

$\displaystyle \lambda = 1\quad\Longrightarrow\quad\frac12\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{cC}a \\ b\end{array}\right) = \left(\begin{array}{cC}0 \\ 0\end{array}\right) \quad\Longrightarrow\quad\left\{\begin{array}{lC}-a+0b=0 \\ a+0b=0\end{array}\right.
\quad\Longrightarrow\quad a = 0\quad\Longrightarrow\quad \nu_1 = \left(\begin{array}{cC} 0 \\ 1\end{array}\right)$

Dovrebbe essere evidente che moltiplicare un autovettore per una costante è ininfluente: si può quindi scegliere, come abbiamo fatto in questo caso, di scrivere numeri interi.

Raccogliamo gli autovettori in una matrice $S = \nu_0 \bigsqcup \nu_1\bigsqcup \ldots\bigsqcup \nu_n $, nel nostro caso

$\displaystyle S=\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)$

troviamo l’inversa di $S$, nel nostro caso ancora

$\displaystyle S^{-1}=\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)$

ed ecco la nostra trasformazione

$\displaystyle \Lambda=S^{-1}TS=\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)\frac12\left(\begin{array}{cC}1 & 0 \\ 1 & 2\end{array}\right)\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)
=\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)\frac12\left(\begin{array}{cC}-1 & 0 \\ 1 & 2\end{array}\right)
=\frac12\left(\begin{array}{cC} 1 & 0 \\ 0 & 2\end{array}\right)
=\left(\begin{array}{cC} \lambda_0 & 0 \\ 0 & \lambda_1\end{array}\right)$

Miracolo: la trasformazione produce una matrice diagonale i cui elementi sono precisamente gli autovalori!

La trasformazione inversa è

$\displaystyle \Lambda =S^{-1}TS\Longrightarrow S\Lambda S^{-1}=SS^{-1}TSS^{-1}=T$

In definitiva avremo $\displaystyle y_r=T^r y_0=S\Lambda^r S^{-1}y_0$: nel nostro caso

$\displaystyle y_r=\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{cC}\left(\frac12\right)^r & 0 \\ 0 & 1\end{array}\right)\left(\begin{array}{cC}-1 & 0 \\ 1 & 1\end{array}\right)\left(\begin{array}{cC}1\\0\end{array}\right)=
\left(\begin{array}{cC}\left(\frac12\right)^r \\1-\left(\frac12\right)^r \end{array}\right)$

Alla prossima...