Due militari americani

[Quelo]

Due militari americani si danno un appuntamento segreto al Pentagono
Arrivano alla stessa ora ma entrano da due ingressi diversi, raggiungono il corridoio centrale e si portano verso uno dei vertici.
Nessuno dei due vede l'altro e non potendo comunicare per non destare sospetti, adottano questa strategia:
- decidono se aspettare un altro minuto con una probabilità del 50%
- decidono se percorrere il corridoio di sinistra (richiede 1 minuto) con una probabilità del 25%
- decidono se percorrere il corridoio di destra (richiede 1 minuto) con una probabilità del 25%
Se dovessero trovarsi ai due lati dello stesso corridoio si vedrebbero e si andrebbero incontro

Qual è la probabilità che si incontrino dopo 1 minuto?
E dopo 2 o 3 minuti?
Esiste una strategtia migliore per incontrarsi il prima possibile?

[franco]

La posizione di partenza, con i due militari su vertici del pentagono che non li mettono in vista reciproca è questa (o la simmetrica ...):

ma1.png (9.76 KiB) Visto 27888 volte

Ognuno dei militari ha 3 opzioni: stare fermo(50%), muoversi in senso orario (25%) o muoversi in senso antiorario (25%).
Quindi le combinazioni sono 9.

Una di esse porta all'incontro:

ma2.png (10.07 KiB) Visto 27888 volte

Tre portano a una condizione in cui i due militari si vedono reciprocamente e quindi si incontreranno sicuramente al successivo minuto:

ma3.png (25.59 KiB) Visto 27888 volte

Cinque riportano ad una condizione analoga a quella di partenza:

ma4.png (39 KiB) Visto 27888 volte

Per ognuna delle combinazioni ho riportato la probabilità all'interno del pentagono.

La probabilità di incontrarsi dopo 1 minuto è P(1)=(1/16)=6,25%
La probabilità di incontrarsi dopo 2 minuti è P(2)=(5/16)+(10/16)*(1/16)=35,15625%
e così via ...

Il tutto probabilmente si può risolvere più elegantemente con i concetti delle catene di Markov:
(I=inizio, V=vista, F=fine=incontro)

ma6.png (41.61 KiB) Visto 27888 volte

... io però con le diagonalizzazioni delle matrici sinceramente non riesco a raccapezzarmi

[franco]

La seconda domanda, quella sulla migliore strategia, non sono sicuro di averla bene interpretata.
Se i due militari hanno avuto la possibilità di accordarsi prima sulla strategia, le loro mosse non sono più casuali.
Basta che, se nel momento di partenza non si vedono, A muova in senso orario e B muova in senso antiorario.
C'è il 50% di probabilità che si incontrino dopo un minuto; in caso contrario saranno comunque in condizione di vedersi a vicenda e quindi si incontreranno al minuto successivo.

[Quelo]

Ciao Franco,
io avevo ragionato che se si vedevano si considervano incontrati, quindi ho calcolato al minuto 1 anche parte dei risultati del minuto 2
Per strategia intendo cambiare le percentuali, cioè conviene muoversi o stare fermi?

[franco]

Chiaro.

In questo caso, l'incontro al minuto 1 ha il 37,5% di probabilità, al minuto 2: P=37,5%x62,5%, ..., al minuto n: P=37,5%x(62,6%)^(n-1).

Circa la strategia, se si riducesse a 1/3 la probabilità di stare sul posto, le 9 combinazioni sarebbero equiprobabili e 4 su 9 garantirebbero l'incontro, con una probabilità del 44,4%.
Direi che conviene muoversi ...

Del resto, se i due eleminano proprio l'opzione di star ferrmi (lasciando al 50% la direzione), le combinazioni si riducono a 4 con una probabilità di incontro del 50%.

Resta l'ultima strategia che è quella che avevo detto prima: decidono in anticipo che uno muoverà in un verso e il secondo nell'altro.

[marcoggz]

Piccola annotazione (forse più da fisico che da matematico): se dopo un minuto si vedono vicendevolmente a distanza di un corridoio, allora poi occorrerà loro solo mezzo minuto aggiuntivo per incontrarsi - a metà del corridoio - e quindi il tempo totale sarà 1,5 min anziché 2.

[Quelo]

Ciao Marco,
il tuo ragionamento è corretto.
Per come l'avevo pensato io, dal momento in cui si vedono (agli estremi di un corriodoio) la questione di trovarsi è risolta e non c'è più possibilità che accada un evento diverso dall'andarsi incontro.

Rispondo anche a Franco.
La strategia migliore, senza previo accordo, è appunto quella di eliminare l'opzione di stare fermi.

La matrice, come l'hai ipotizzata tu, sarebbe

$\displaystyle\begin{bmatrix}
0.625 & 0.3125 & 0.0625 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
\end{bmatrix}$

Dove sulle righe abbiamo la partenza (I,V,F) e sulle colonne l'arrivo (I,V,F)
Ad esempio sulla prima riga:
da I a I: 62,5%
da I a V: 31,25%
da I a F: 6,25%
La somma per riga deve dare 1

moltiplicando la matrice per sé stessa abbiamo

$\displaystyle\begin{bmatrix}
0.39 & 0.195 & 0.414 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
\end{bmatrix}$

La probabilità I --> F dopo 2 minuti è 41,4% (6,25% del primo minuto + 35,15% del secondo minuto)

Al terzo minuto 63,4% (con un contributo del terzo minuto pari al 22%)

$\displaystyle\begin{bmatrix}
0.244 & 0.122 & 0.634 \\
0 & 0 & 1 \\
0 & 0 & 1 \\
\end{bmatrix}$

Nella mia ipotesi invece la matrice si riduce a 2x2 (Inizio <--> Vista)

$\displaystyle\begin{bmatrix}
0.625 & 0.375 \\
0 & 1 \\
\end{bmatrix}$

$\displaystyle\begin{bmatrix}
0.39 & 0.61 \\
0 & 1 \\
\end{bmatrix}$

$\displaystyle\begin{bmatrix}
0.244 & 0.756 \\
0 & 1 \\
\end{bmatrix}$