Un problema sui parcheggi
Ciao a tutti!
In un condominio vivono $n$ condomini: uno è italiano, i restanti $n-1$ sono tedeschi. Ciascun condomino possiede un posto auto. Supponiamo che ogni sera il primo ad arrivare sia l'italiano, il quale parcheggia la sua auto uniformemente a caso in uno degli $n$ posti auto disponibili. Dopo l'italiano arrivano uno dopo l'altro i tedeschi, che parcheggiano secondo il seguente schema: qualora un tedesco trovi il proprio posto libero, parcheggia lì; altrimenti, parcheggia uniformemente a caso in uno qualunque dei posti rimasti liberi.
Qual è la probabilità che l'ultimo condomino che arriva parcheggi al suo posto?
I casi $n=2,3,4$ si trattano abbastanza facilmente (condizionando al fatto che l'italiano parcheggi al suo posto o meno), il fatto è che bisognerebbe generalizzare il tutto ad $n$ condomini.
Il problema è stato assegnato in un corso di catene di Markov, dunque è probabilmente modellizzabile con una CdM (io non la vedo, ci ho pensato parecchio).
Vi ringrazio per l'attenzione
In un condominio vivono $n$ condomini: uno è italiano, i restanti $n-1$ sono tedeschi. Ciascun condomino possiede un posto auto. Supponiamo che ogni sera il primo ad arrivare sia l'italiano, il quale parcheggia la sua auto uniformemente a caso in uno degli $n$ posti auto disponibili. Dopo l'italiano arrivano uno dopo l'altro i tedeschi, che parcheggiano secondo il seguente schema: qualora un tedesco trovi il proprio posto libero, parcheggia lì; altrimenti, parcheggia uniformemente a caso in uno qualunque dei posti rimasti liberi.
Qual è la probabilità che l'ultimo condomino che arriva parcheggi al suo posto?
I casi $n=2,3,4$ si trattano abbastanza facilmente (condizionando al fatto che l'italiano parcheggi al suo posto o meno), il fatto è che bisognerebbe generalizzare il tutto ad $n$ condomini.
Il problema è stato assegnato in un corso di catene di Markov, dunque è probabilmente modellizzabile con una CdM (io non la vedo, ci ho pensato parecchio).
Vi ringrazio per l'attenzione
Risposte
Puoi postare i casi $n = 3, 4$?
$n=3$
$\mathbb{P}(uc)=\mathbb{P}(uc|I=i)\mathbb{P}(I=i)+\mathbb{P}(uc|I=t_1)\mathbb{P}(I=t_1)+\mathbb{P}(uc|I=t_2)\mathbb{P}(I=t_2)=1\cdot\frac{1}{3}+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{3}+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{3}=\frac{1}{2}$,
ove con "uc" intendo l'evento "l'ultimo condomino è contento, ovvero percheggia al suo posto", con $I=i$ l'evento "l'italiano parcheggia al suo posto", con $I=t_i$ l'evento "l'italiano parcheggia al posto del tedesco $i$-esimo".
Il caso $n=3$ è analogo. Il fatto è che dovrebbe esserci un modo più elegante e rapido di farlo, probabilmente usando una opportuna CdM.
$\mathbb{P}(uc)=\mathbb{P}(uc|I=i)\mathbb{P}(I=i)+\mathbb{P}(uc|I=t_1)\mathbb{P}(I=t_1)+\mathbb{P}(uc|I=t_2)\mathbb{P}(I=t_2)=1\cdot\frac{1}{3}+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{3}+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{3}=\frac{1}{2}$,
ove con "uc" intendo l'evento "l'ultimo condomino è contento, ovvero percheggia al suo posto", con $I=i$ l'evento "l'italiano parcheggia al suo posto", con $I=t_i$ l'evento "l'italiano parcheggia al posto del tedesco $i$-esimo".
Il caso $n=3$ è analogo. Il fatto è che dovrebbe esserci un modo più elegante e rapido di farlo, probabilmente usando una opportuna CdM.
Chiaramente intendevo "il caso $n=4$ è analogo".
Ho fatto un po' di prove.
Chiamiamo $1$ il posto dell'Italiano, ed $n$ il posto dell'ultimo Tedesco.
$n$ può prendere solo il "suo" posto, oppure il posto 1.
Non può prendere posti intermedi. Mai.
Gli altri non possono mai pescare entrambi.
Da ciò la probabilità è $1/2$.
Ma non sono in grado di formalizzarla.....
Chiamiamo $1$ il posto dell'Italiano, ed $n$ il posto dell'ultimo Tedesco.
$n$ può prendere solo il "suo" posto, oppure il posto 1.
Non può prendere posti intermedi. Mai.
Gli altri non possono mai pescare entrambi.
Da ciò la probabilità è $1/2$.
Ma non sono in grado di formalizzarla.....
In realtà l'ordine di arrivo dei tedeschi non è noto... Bisognerebbe condizionare al fatto che arrivino in un certo ordine (farlo per ogni permutazione di $n-1$ oggetti). Inoltre sono d'accordo col fatto che l'ultimo tedesco che arriva possa prendere solo il suo posto, o quello dell'italiano, però non mi è chiaro perchè dovrebbe trovare il suo libero proprio con probabilità $\frac{1}{2}$ (quando arriva non sceglie, trova un posto libero e deve parcheggiare lì...).
"vladimir":
Inoltre sono d'accordo col fatto che l'ultimo tedesco che arriva possa prendere solo il suo posto, o quello dell'italiano
Non sono d'accordo. E' vero che se l'italiano occupa il proprio posto (cosa che accade con probabilità $1/n$), allora tutti i tedeschi sono contenti con probabilità $1$, compreso l'ultimo. Ma se l'italiano occupa il posto del primo tedesco che arriva (con probabilità $1/n$), allora questo tedesco potrebbe occupare con probabilità $1/(n-1)$ proprio il posto dell'italiano (nel qual caso sarebbe l'unico tedesco scontento), ovvero con la stessa probabilità il posto dell'ultimo tedesco (il quale rimarrebbe scontento).
EDIT:
"vladimir":
In realtà l'ordine di arrivo dei tedeschi non è noto...
Non sono tanto convinto nemmeno di questo. I tedeschi sono tutti uguali e i posti (per l'italiano) sono tutti uguali. Provo a dirlo in altro modo: se ci facciamo la domanda "in che ordine arrivano?" vuol dire che questo ordine non ci è noto, non fa parte del nostro stato di conoscenza (quindi dovremmo/potremmo condizionare); ma l'italiano se ne frega di un ordine e occupa il posto in maniera casuale; quale che sia il primo tedesco che arriva, egli troverà il suo posto libero comunque con probabilità $(n-1)/n$.
Continuo a pensarci..
"vladimir":
Ciao a tutti!
In un condominio vivono $n$ condomini: uno è italiano, i restanti $n-1$ sono tedeschi. Ciascun condomino possiede un posto auto. Supponiamo che ogni sera il primo ad arrivare sia l'italiano, il quale parcheggia la sua auto uniformemente a caso in uno degli $n$ posti auto disponibili. Dopo l'italiano arrivano uno dopo l'altro i tedeschi, che parcheggiano secondo il seguente schema: qualora un tedesco trovi il proprio posto libero, parcheggia lì; altrimenti, parcheggia uniformemente a caso in uno qualunque dei posti rimasti liberi.
Qual è la probabilità che l'ultimo condomino che arriva parcheggi al suo posto?
La probabilità è sempre il $50%$ per qualsiasi $n$
1) Il primo condomino $A,1$ parcheggia nel suo posto e allora tutto procede positivamente fino all'ultimo posto $n$.
$P = 1/n$
2) $A,1$ parcheggia nel posto $n$ dell'ultimo condomino e allora tutti gli altri $(n-2)$ trovano il loro posto libero, ma l'ultimo $A,n$ lo trova occupato. Probabilità contraria $Q = P = 1/n$
3) $A,1$ mette l'auto in qualsiasi altro posto da $2$ a $n-1$; in questo caso, l'ultimo posto $n$ è ancora libero con probabilità $(n-2)/n$
Arriva $A,2$ e si trova davanti due possibilità:
3a) il posto $2$ è libero e allora lo occupa e non cambia nulla, è come se i condomini e i posti fossero uno in meno
3b)il posto $2$ è stato occupato con probabilità $1/n$ da $A,1$ e allora:
- parcheggia nel posto $n$ o nel posto $1$ con uguale probabilità $1/(n-1)$
- parcheggia in un altro posto libero diverso da $1$ da $2$ e da $n$ e la storia si ripete con il condomino $A,3$
In conclusione, la probabilità che un condomino parcheggi in un posto lasciato libero da un altro (che non aveva occupato il suo) oppure l'ultimo posto $n$ è sempre la stessa per ogni condomino: quindi, quando parcheggerà l'ultimo avrà il $50%$ di probabilità di trovare il suo posto libero.
Nino
"Aster89":
[quote="vladimir"]Inoltre sono d'accordo col fatto che l'ultimo tedesco che arriva possa prendere solo il suo posto, o quello dell'italiano.
[quote="Aster89"]Non sono d'accordo. E' vero che se l'italiano occupa il proprio posto (cosa che accade con probabilità $1/n$), allora tutti i tedeschi sono contenti con probabilità $1$, compreso l'ultimo. Ma se l'italiano occupa il posto del primo tedesco che arriva (con probabilità $1/n$), allora questo tedesco potrebbe occupare con probabilità $1/(n-1)$ proprio il posto dell'italiano (nel qual caso sarebbe l'unico tedesco scontento), ovvero con la stessa probabilità il posto dell'ultimo tedesco (il quale rimarrebbe scontento).
[/quote][/quote]
Non capisco come questo possa contraddire quello che ho scritto sopra, ovvero che l'ultimo tedesco che arriva troverà libero un posto: o il proprio o quello dell'italiano (così non fosse, troverebbe libero il posto di un qualche tedesco $t_i$, il che è assurdo, dato che il suddetto tedesco $t_i$ è già arrivato, e non può non aver occupato il proprio posto).
"nino_":
[quote="vladimir"]Ciao a tutti!
In un condominio vivono $n$ condomini: uno è italiano, i restanti $n-1$ sono tedeschi. Ciascun condomino possiede un posto auto. Supponiamo che ogni sera il primo ad arrivare sia l'italiano, il quale parcheggia la sua auto uniformemente a caso in uno degli $n$ posti auto disponibili. Dopo l'italiano arrivano uno dopo l'altro i tedeschi, che parcheggiano secondo il seguente schema: qualora un tedesco trovi il proprio posto libero, parcheggia lì; altrimenti, parcheggia uniformemente a caso in uno qualunque dei posti rimasti liberi.
Qual è la probabilità che l'ultimo condomino che arriva parcheggi al suo posto?
La probabilità è sempre il $50%$ per qualsiasi $n$
1) Il primo condomino $A,1$ parcheggia nel suo posto e allora tutto procede positivamente fino all'ultimo posto $n$.
$P = 1/n$
2) $A,1$ parcheggia nel posto $n$ dell'ultimo condomino e allora tutti gli altri $(n-2)$ trovano il loro posto libero, ma l'ultimo $A,n$ lo trova occupato. Probabilità contraria $Q = P = 1/n$
3) $A,1$ mette l'auto in qualsiasi altro posto da $2$ a $n-1$; in questo caso, l'ultimo posto $n$ è ancora libero con probabilità $(n-2)/n$
Arriva $A,2$ e si trova davanti due possibilità:
3a) il posto $2$ è libero e allora lo occupa e non cambia nulla, è come se i condomini e i posti fossero uno in meno
3b)il posto $2$ è stato occupato con probabilità $1/n$ da $A,1$ e allora:
- parcheggia nel posto $n$ o nel posto $1$ con uguale probabilità $1/(n-1)$
- parcheggia in un altro posto libero diverso da $1$ da $2$ e da $n$ e la storia si ripete con il condomino $A,3$
In conclusione, la probabilità che un condomino parcheggi in un posto lasciato libero da un altro (che non aveva occupato il suo) oppure l'ultimo posto $n$ è sempre la stessa per ogni condomino: quindi, quando parcheggerà l'ultimo avrà il $50%$ di probabilità di trovare il suo posto libero.
Nino[/quote]
Sono d'accordo su tutto, solo non capisco come sei arrivato al $50%$.
"vladimir":[/quote][/quote]
[quote="nino_"][quote="vladimir"]
Sono d'accordo su tutto, solo non capisco come sei arrivato al $50%$.
Perché ho cercato di spiegare che, indipendentemente dal valore di $n$, gli unici casi significativi riguardano il primo che o occupa il posto 1 dell'italiano o mette l'auto sullo spazio dell'ultimo che deve arrivare e questi eventi sono equiprobabili (nel primo caso, l'ultimo condomino trova il suo posto occupato e dovrà mettere l'auto nel posto dell'italiano, nell'altro caso parcheggerà al suo posto)
Concordo con nino_.
Provo a formalizzare.
I condomini arriveranno in un certo ordine. Si può pensare di numerare i posti esattamente con il numero di arrivo del rispettivo condomino. Con $X_j$ indico la v.a. "numero del posto occupato dal $j$-esimo condomino (per intenderci, l'evento $X_3 = 5$ è "il terzo condomino occupa il posto macchina del quinto condomino").
La probabilità che cerchiamo è $Pr\{X_n = n| n\text{ posti liberi}\}$ e può essere scritta con la regola di Bayes fattorizzando rispetto a quale posto viene occupato dal condomino italiano, cioè
$Pr\{X_n = n\} = \sum_{i=1}^{n} Pr\{X_n = n| X_1=i\} \times Pr\{X_1 = i\} = \sum_{i=1}^{n} Pr\{X_n = n| X_1=i\} \times 1/n = 1/n + 1/n \times \sum_{i=2}^{n-1} Pr\{X_n = n| X_1=i\}$
dove l'ultima uguaglianza è una conseguenza ovvia del fatto che
$Pr\{X_n = n| X_1=1\} = 1$
$Pr\{X_n = n| X_1=n\} = 0$
Ma chi è $Pr\{X_n = n| X_1=i\}$ (per $i !=1,n$) ?
nino_ dice giustamente che, se assumi l'evento "$X_1=i$", la conseguenza è che tutto va liscio fino all'$i$-esimo condomino, il quale si comporterà proprio come l'italiano, ma avendo a disposizione solo $n-i+1$ posti.
Pertanto,
$Pr\{X_n = n\} \dot{=} Pr\{X_n = n|\text{p. tot. =}n\} = 1/n + 1/n \sum_{i=2}^{n-1} Pr\{X_{n-i+1} = n-i+1|\text{p. tot. =}n-i+1\}$
E' facile allora partire dal caso $n = 2$, per il quale la sommatoria risolta vuota, comportando ovviamente che $Pr\{X_2 = 2|\text{p. tot.=} 2\} = 1/2$ e ricavare ricorsivamente che $Pr\{X_n = n|\text{p. tot. =}n\} = 1/2$ per ogni $n$.
Provo a formalizzare.
I condomini arriveranno in un certo ordine. Si può pensare di numerare i posti esattamente con il numero di arrivo del rispettivo condomino. Con $X_j$ indico la v.a. "numero del posto occupato dal $j$-esimo condomino (per intenderci, l'evento $X_3 = 5$ è "il terzo condomino occupa il posto macchina del quinto condomino").
La probabilità che cerchiamo è $Pr\{X_n = n| n\text{ posti liberi}\}$ e può essere scritta con la regola di Bayes fattorizzando rispetto a quale posto viene occupato dal condomino italiano, cioè
$Pr\{X_n = n\} = \sum_{i=1}^{n} Pr\{X_n = n| X_1=i\} \times Pr\{X_1 = i\} = \sum_{i=1}^{n} Pr\{X_n = n| X_1=i\} \times 1/n = 1/n + 1/n \times \sum_{i=2}^{n-1} Pr\{X_n = n| X_1=i\}$
dove l'ultima uguaglianza è una conseguenza ovvia del fatto che
$Pr\{X_n = n| X_1=1\} = 1$
$Pr\{X_n = n| X_1=n\} = 0$
Ma chi è $Pr\{X_n = n| X_1=i\}$ (per $i !=1,n$) ?
nino_ dice giustamente che, se assumi l'evento "$X_1=i$", la conseguenza è che tutto va liscio fino all'$i$-esimo condomino, il quale si comporterà proprio come l'italiano, ma avendo a disposizione solo $n-i+1$ posti.
Pertanto,
$Pr\{X_n = n\} \dot{=} Pr\{X_n = n|\text{p. tot. =}n\} = 1/n + 1/n \sum_{i=2}^{n-1} Pr\{X_{n-i+1} = n-i+1|\text{p. tot. =}n-i+1\}$
E' facile allora partire dal caso $n = 2$, per il quale la sommatoria risolta vuota, comportando ovviamente che $Pr\{X_2 = 2|\text{p. tot.=} 2\} = 1/2$ e ricavare ricorsivamente che $Pr\{X_n = n|\text{p. tot. =}n\} = 1/2$ per ogni $n$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo