Grand Tour

[axpgn]

Un turista americano ha intenzione di visitare quattro grandi capitali europee: Roma, Parigi, Londra e Berlino.
Essendo un tipo un pochino eccentrico non ha stabilito a priori un calendario preciso ma sceglierà casualmente, di volta in volta, quale città visitare dopo quella appena vista.
Purtroppo però è anche una persona dalla memoria corta quindi nel decidere quale sarà la prossima meta, terrà in considerazione anche quelle già visitate.

Faccio un esempio per spiegarmi meglio: poniamo che scelga casualmente Roma come prima tappa del suo viaggio; al termine del soggiorno sceglierà la prossima tra le altre tre e supponiamo che la prescelta sia Parigi; dopo averla visitata non sceglierà la successiva destinazione solo tra Londra e Berlino, come sarebbe normale che fosse, ma includerà anche Roma tra le prossime tappe tra cui scegliere. E così via, di seguito ...

Mediamente, quanti viaggi dovrà fare per visitarle tutte e quattro?



Cordialmente, Alex

[mgrau]

Solo un abbozzo, o piuttosto un ragionamento sul problema. Trasformo il problema in uno più stringato. Lanciamo un dado a 4 facce, dopo quanti lanci, in media, avremo visto tutte e quattro le facce?
Semplifico ancora, passando da 4 a 2, e uso una moneta. Dopo quanti lanci (dopo il primo) in media, avremo visto le due facce?
Allora: la probabilità di vedere testa al secondo lancio (supponiamo croce al primo) è 1/2; la P di vedere testa al terzo lancio (PROPRIO al terzo lancio, e non prima) è 1/2 per la P che i precedenti siano croce, ossia 1/4, e in generale, la P di avere testa PROPRIO all'n-esimo lancio è $1/2^n$
Infine, il valor medio di n per avere successo (aver visto le due facce) è la media degli n pesata con la loro probabilità, ossia $(Sigma n1/2^n)/(Sigma 1/2^n)$. Il denominatore vale 1, per cui il valore medio cercato è la somma della serie $Sigma n1/2^n$
Mi sembra di vedere che la somma è 2, ma le mie competenze matematiche non mi soccorrono.
Quanto poi al problema delle 4 capitali, direi che cambia solo qualche dettaglio,
EDIT Una veloce ricerca (che potevo fare prima) mi conferma che la serie $Sigma nx^n = x/(1-x)^2$, da cui, per $x = 1/2$, la somma è davvero 2

[axpgn]

Premesso che le mie competenze in campo probabilistico mi soccorrono ancor meno e al di là del fatto che non sono convintissimo dell'analogia, mi suona strano che la media di lanci sia un $2$ scarso ... mi pare un po' poco ...
Peraltro noto sicuramente una differenza col problema originario: in quel caso l'evento appena accaduto (l'ultima città visitata) non è tra le scelte prossime a differenza del lancio della moneta; mi sbaglio?

Cordialmente, Alex

[axpgn]

Ragionandoci un po' di più mi è chiaro il tuo ragionamento: dopo il primo lancio, metà delle volte mi verrà l'altra faccia al secondo lancio, un quarto delle volte al terzo lancio, un ottavo al quarto e così via che in effetti somma a $2$.

Però, come dicevo prima, il problema originale è diverso ...

Cordialmente, Alex

[Quinzio]

Non sono sicuro, ma credo che bisogna procedere cosi'...

Mi chiedo quanti tipi di viaggi ci sono facendo $l$ tappe.
Come prima tappa scelgo tra le 4 citta; A, B, C, D.
Poi possono scegliere una delle 3 dove NON sono io adesso, per la tappa successiva.
Ad es, sono in A, posso scegliere tra B, C, D.
Quindi i viaggi possibili di $l$ tappe sono: $4*3^{l-1}$

Adesso mi chiedo quanti viaggi si concludono dopo $l$ tappe.
Per concludersi, un viaggio deve aver visitato 3 citta' e concludersi sulla 4^.
Quindi posso scegliere tra 4 citta' di arrivo.
Per ognuna delle citta' di arrivo, posso iniziare il viaggio da una delle altre 3.
Quindi, per ogni tappa intermedia, posso scegliere solo tra 2 citta':
non posso scegliere quella di arrivo,
non posso scegliere quella in cui sono.
Quindi i modi sono: $4*3*2^{l-2}$
Poi devo scartare dal computo dei viaggi che si concludono dopo $l$ tappe quei viaggi
che fanno solo 2 citta.
Ad es. il viaggio ABABABABABC che si conclude in C viene contato 2 volte,
siccome manca C e manca D da ogni tappa (C e' solo alla fine).
Di questi viaggi particolari ce ne sono 24:
4 citta' di arrivo x una delle altre 3 x 2 alternative.
Le due alternative sarebbero ad es. ABABC e BABAC.

Quindi la probabilita' che un viaggio termini dopo $l$ tappe sono:
$"numero viaggi che si concludono" / "totale viaggi" = (4*3*2^{l-2} -24) / (4*3^{l-1}) = (2^{l-2}-2)/(3^{l-2})$

Ad es. per i viaggi di 4 tappe, ce ne sono 96 in tutto, di cui 24 terminano.
Qui sotto ci sono solo i 12 che partono da AB, quelli con l'asterisco sono quelli che terminano.

ABAB
ABAC
ABAD
ABCA
ABCB
ABCD *
ABDA
ABDB
ABDC *

Ora, per calcolare il numero medio di tappe, si applica la formula:

$\sum_{l=4} l P(l)$

dove $P(l)$ e' la probabilita' che il viaggio termini dopo $l$ tappe,

$\sum_{l=4} l P(l) = \sum_{l=4} l (2^{l-2}-2)/(3^{l-2})$

$ = \sum_{l=4} l (2/3)^{l-2} - 2 \sum_{l=4} l 1/(3^{l-2})$

$ = \sum_{l=2} (l+2) (2/3)^l - 2 \sum_{l=2} (l+2) 1/(3^l)$

$ = \sum_{l=2} l (2/3)^l + 2\sum_{l=2} (2/3)^l - 2 \sum_{l=2} l 1/(3^l) - 4\sum_{l=2} 1/(3^l)$


Sapendo che

$ \sum_(n=2) n a^n = -((a - 2) a^2)/(a - 1)^2 \ \ \ \"con" \ \ \ \ (a)<1$

e svolgendo i calcoli, dovrebbe risultare $54/12 = 4,5$
ovvero i viaggi durano in media circa 4,5 tappe.

Che e' una soluzione evidentemente sbagliata.

EDIT: la soluzione e' sbagliata perche' ci sono molti viaggi che non si concludono mai,
e questi viaggi abbassano la media di molto.
Bisogna vedere se conteggiarli.

[axpgn]

Come hai già notato il numero di viaggi possibili così come quelli favorevoli è infinito quindi quel metodo non funziona

Cordialmente, Alex

[Drazen77]

22%?

[axpgn]

Non ho chiesto la probabilità (di cosa poi?) ma QUANTI viaggi mediamente dovrà fare per visitarle tutte (Tecnicamente dovrebbe essere "il valore atteso" ma ho sempre dei dubbi nell'usare questa espressione )

[giammaria2]

Formula probabilmente famosa, ma che ricavo perché non la ricordo.
Con $0 $sum_(h=1)^oo hx^(h-1)=(x^0)+(x^1+x^1)+(x^2+x^2+x^2)+(x^3+x^3+x^3+x^3+x^3)+...$
Raccolgo assieme i primi addendi di ogni tonda, poi i secondi eccetera; ottengo
$sum_(h=1)^oo hx^(h-1)=(1+x+x^2+x^3+...)+(x+x^2+x^3+...)+(x^2+x^3+...)+...=$
$" "=1/(1-x)+x/(1-x)+x^2/(1-x)+...=1/(1-x)(1+x+x^2+...)=1/(1-x)^2$

Soluzione del problema
- Contando anche il viaggio dall'America, per raggiungere le prime due città occorrono $n_2=2$ viaggi.

- Dopo aver visitato due città, per ogni viaggio ci sono 3 possibilità; 2 conducono ad una città nuova ed 1 riporta indietro. La terza città viene raggiunta al tentativo h-esimo se $h-1$ viaggi portano indietro e l'ultimo no, quindi con probabilità $p_h=(1/3)^(h-1)*2/3$. Il numero medio di viaggi dalla seconda alla terza città è quindi
$n_3=sum_(h=1)^oo hp_h=2/3 sum_(h=1)^oo h(1/3)^(h-1)=2/3*1/(1-1/3)^3=2/3*9/4=3/2=1,5$

- Ragionando analogamente, trovo che dopo aver visitato 3 città si ha $p_h=(2/3)^(h-1)*1/3$ e quindi per passare dalla terza alla quarta città il numero medio di viaggi è
$n_4=1/3*1/(1-2/3)^2=1/3*9=3$

- In totale, il numero medio di viaggi è
$n=n_2+n_3+n_4=2+1,5+3=6,5$
A questo punto ha finito il tour, ma deve ancora tornare a casa sua: un altro viaggio (da contare o no?). Si spera che almeno ricordi di aver finito.

[axpgn]

Perfetto!

Detto $V$ il numero medio di viaggi per visitare tutte e quattro le città, abbiamo $V=V_0+V_1+V_2+V_3$ dove $V_i$ è il numero medio di viaggi da fare per visitare una nuova città dopo averne già visitate $i$.

Quindi $V_0=V_1=1$

Per calcolare $V_2$ e $V_3$ possiamo usare la famosa formula $p(1-p)^(k-1)$ cioè quella che determina la probabilità di avere un successo al $ktext(-esimo)$ tentativo dopo averne falliti $k-1$ (e dove $p$ è la probabilità di avere successo).
La media di quella serie è $1/p$ quindi siccome è $p_2=2/3$ e $p_3=1/3$ ne consegue che $V_2=3/2$ e $V_3=3$, concludendo che $V=1+1+3/2+3=13/2$

Cordialmente, Alex

P.S.:

"giammaria":A questo punto ha finito il tour, ma deve ancora tornare a casa sua: un altro viaggio (da contare o no?).

No perché si richiede quanto ci metterà a visitarle tutte non a tonare a casa
Se non si ricorda neppure di aver finito, saranno problemi suoi

[Bokonon]

6,5
2 viaggi sicuri
Poi in media 1,5 viaggi per visitare una terza città (avendo 1:1,5 di beccarla)
E infine 3 viaggi in media per visitare la quarta (avendo 1:3 di beccarla)

[axpgn]