Domanda:
Tempo medio di cui una formica ha bisogno per uscire nel bosco
dokondr
2020-01-30 19:02:48 UTC
view on stackexchange narkive permalink

Una formica ha tre passaggi tra cui scegliere:

  1. Il passaggio A impiega 7 minuti per portare la formica fuori dalla casa delle formiche nel bosco.

  2. Il passaggio B impiega 8 minuti per riportare formica al punto di partenza in cui si trova.

  3. Il passaggio C impiega 12 minuti per riportare formica al punto di partenza in cui si trova.

La formica sceglie un passaggio a caso finché non esce dal formicaio nel bosco.

Come calcolare il tempo medio previsto per una formica per uscire?

Il valore medio semplice (7 + 8 + 12) / 3 = 9 risponde alla domanda?

Nota che se la formica non esce al primo tentativo entro 7 minuti, impiegherà almeno 15 minuti per uscire.Per ottenere un tempo medio di soli 9 minuti, la formica dovrebbe scappare al primo tentativo più della metà del tempo, cosa che sappiamo non è il caso.Sto solo cercando di dare un'idea intuitiva di quale gamma di risposte potrebbe avere senso, come un controllo di sanità mentale per escludere possibili linee di pensiero - possiamo vedere che la risposta media è troppo bassa.
Se c'è solo una via d'uscita e $ n-1 $ modi per perdere tempo, la * somma semplice * risponde alla domanda
È lo stesso di [questa] (https://math.stackexchange.com/q/2521890/321264) domanda popolare.
Sette risposte:
#1
+25
Don Slowik
2020-01-30 23:27:07 UTC
view on stackexchange narkive permalink

$$ T = 7/3 + (8 + T) / 3 + (12 + T) / 3 = 9 + 2T / 3 $$ $$ T / 3 = 9 $$ $$ T = 27 $$ Dal punto di partenza, ciascuno dei 3 percorsi è ugualmente possibile.Due percorsi ti riportano al punto di partenza.

Cosa sono "8 + T" e "12 + T"?
+1 Molto [email protected] $ T $ è il tempo previsto che la formica impiegherà per uscire dalla foresta.Se prosegue con il passaggio $ B $ o $ C $ torna al punto di partenza e deve intraprendere un viaggio con il tempo previsto $ T $ da capo, più il tempo impiegato per quel particolare passaggio.
Quindi è una definizione ricorrente di T
$ T $ non è * definito * ricorsivamente, ma la formula iniziale è una relazione ricorsiva che nasce dalla definizione dell'aspettativa.
Non è una definizione ricorsiva di T;è solo un'equazione che è vera per T, dove T è l'intero lato sinistro e dove T appare anche sul lato destro.
Sì, questa era anche la mia soluzione.Ha semplificato l'equazione in modo diverso però.+1
#2
+10
Bridgeburners
2020-01-30 21:01:55 UTC
view on stackexchange narkive permalink

Per rispondere a questa domanda, devi sommare tutti i possibili percorsi che la formica può prendere e ottenere la durata di quel percorso, moltiplicata per la probabilità di intraprendere quel percorso. Questo è, $$ E [T] = \ sum _ {\ text {percorso} \ in \ text {possibili percorsi}} p (\ text {percorso}) T (\ text {percorso}) $$

Ogni percorso possibile accetta Passage $ A $ solo una volta, ma può accettare passaggi $ B $ e $ C $ un numero qualsiasi di volte, in qualsiasi permutazione. Quindi i possibili percorsi possono essere $ A $ , $ BA $ , $ BBCCA $ , $ BCCBA $ e così via

Supponi le probabilità di scegliere i passaggi $ A, $ $ B, $ e $ C, $ sono $ p_a $ , $ p_b $ e $ p_c $ rispettivamente. Quindi, ad esempio, la probabilità di prendere il percorso $ CBBCCA $ è $ p_a p_b ^ 2 p_c ^ 3. $ span> E, poiché ci sono $ {5 \ choose 2} = 10 $ modi per utilizzare $ B $ span > due volte e $ C $ tre volte, il contributo del tempo di percorso previsto dato dalla possibilità di 3 $ C $ s e 2 $ B $ s è $ 10 p_a p_b ^ 2 p_c ^ 3 (T_a + 2 T_b + 3 T_c) $ , dove $ T_a $ , $ T_b $ e $ T_c $ sono rispettivamente i tempi di percorso di ogni passaggio.

Quanto sopra fornisce il contributo al tempo previsto per prendere due $ B $ e tre $ C $ span> s prima di $ A $ . Ma in generale, devi sommare il contributo temporale previsto di tutte le possibili combinazioni di percorsi $ B $ e $ C $ prima di $ A $ lo farò di seguito, ma ti suggerisco di fermarti qui e di provare prima tu stesso.


SPOILER

In generale, la formica può eseguire un passaggio non $ A $ un numero qualsiasi di volte compreso tra zero e infinito prima di eseguire un passaggio $ A $ e per quel numero di volte può essere una qualsiasi combinazione di passaggi $ B $ e $ C $ . Quindi, per ottenere il tempo di percorso previsto, sommiamo il contributo di tutte le possibilità di passaggio, moltiplicato per il loro tempo, che sembra,

$$ E [T] = T_a + p_a \ sum_ {n = 0} ^ \ infty \ sum_ {i = 0} ^ n {n \ scegli i} p_b ^ i p_c ^ {ni} [i T_b + (ni) T_c] . $$

Queste somme possono essere valutate. Usando il teorema binomiale e prendendo la derivata, puoi dimostrare che, $$ \ sum_ {i = 0} ^ n i {n \ scegli i} x ^ i y ^ {n-i} = n x (x + y) ^ {n-1} $$ e

$$ \ sum_ {i = 0} ^ n (n-i) {n \ scegli i} x ^ i y ^ {n-i} = n y (x + y) ^ {n-1}. $$

Usando queste identità, otteniamo

$$ E [T] = T_a + p_a (p_b T_b + p_c T_c) \ sum_ {n = 0} ^ \ infty n (p_b + p_c) ^ {n-1}. $$

Prendendo la derivata della somma delle famose serie geometriche, puoi mostrare che, per $ | x | < 1 $ ,

$$ \ sum_ {n = 0} ^ \ infty n x ^ {n-1} = \ frac {1} {(1 - x) ^ 2}. $$

Notando che $ 1 - (p_b + p_c) = p_a $ , otteniamo,

$$ E [T] = T_a + \ frac {1} {p_a} (T_b p_b + T_c p_c). $$

Se prendiamo $ p_a = p_b = p_c = 1/3 $ e i tuoi valori per i tempi, otteniamo $ E [T] = T_a + T_b + T_c $ che è di 27 minuti.

Ottima spiegazione!
#3
+8
Davide ND
2020-01-30 21:10:56 UTC
view on stackexchange narkive permalink

Ciao donkordr e benvenuto nel CV.
No, purtroppo la media non risponde alla domanda.

Puoi leggere il tuo problema come una catena di Markov con due stati: bosco e formicaio.
Ora, le tue probabilità di transizione sono:

  • Dal bosco: (non importa perché è l'obiettivo) $ p = 1 $ rimanere nel bosco
  • Dalla casa delle formiche: $ p_1 = \ frac {2} {3} $ per stare alla casa delle formiche e $ p_2 = \ frac {1} {3} $ per andare nei boschi

Vogliamo sapere quanti movimenti occorrono in media per raggiungere il bosco - e puoi farlo come spiegato qui

Ciò si traduce in una media di 3 movimenti.
Di questi 3 movimenti, uno e solo uno sarà quello che porta nel bosco, mentre il resto sarà uno qualsiasi degli altri. Il tempo medio di un movimento che non va nel bosco è di $ (8 + 12) / 2 = 10 $ minuti.

Di conseguenza, il tempo medio prima di raggiungere il bosco è di $ 27 $ minuti: $ 7 $ dall'ultimo passaggio e $ 2 \ cdot10 $ da quelli precedenti.

PS: ci sono altri modi per eseguire questo calcolo con stati intermedi che potrebbero essere più puliti, ma sembrava abbastanza facile.

#4
+5
Igor F.
2020-01-30 22:31:33 UTC
view on stackexchange narkive permalink

Mi unisco a una spiegazione che, almeno a me, sembra ancora più semplice:

Innanzitutto, osserva che i percorsi $ B $ e $ C $ possono essere uniti in un unico percorso $ X $ , con il tempo di percorrenza pari ai tempi medi di $ B $ e $ C $ , cioè $ 10 $ minuti. Ciò è dovuto al fatto che questi percorsi hanno la stessa probabilità. In caso contrario, dovremmo prendere una media ponderata. La probabilità di prendere il percorso $ X $ è la somma delle probabilità di prendere il percorso $ B $ oppure $ C $ : $ P (X) = P (B) + P (C) = 2/3 $ .

Ora, ci sono i seguenti modi per arrivare nel bosco:

$$ \ begin {array} {lrr} i & \ text {percorso} _i & P (i) & T (i) \\ \ hline 0 & A & 1/3 & 7 \\ 1 & XA & 2/3 \ cdot 1/3 & 10 + 7 \\ 2 & XXA & (2/3) ^ 2 \ cdot 1/3 & 20 + 7 \\ 3 & XXXA & (2/3) ^ 3 \ cdot 1/3 & 30 + 7 \\ & ... & \\ i & (i \ cdot X) A & (2/3) ^ i \ cdot 1/3 & 10 \ cdot i + 7 \ end {array} $$

e il tempo previsto è:

$$ \ begin {array} {lcl} E (T) & = & \ sum_ {i = 0} ^ \ infty P (i) T (i) \\ & = & 1/3 \ cdot \ sum_ {i = 0} ^ \ infty \ left (10 \ cdot i + 7 \ right) \ cdot (2/3) ^ i \\ & = & 10/3 \ cdot \ sum_ {i = 0} ^ \ infty i \ cdot (2/3) ^ i + 7/3 \ cdot \ sum_ {i = 0} ^ \ infty (2/3) ^ i \\ & = & 10/3 \ cdot 6 + 7/3 \ cdot 3 \\ & = & 27 \\ \ end {array} $$

Grazie!Spiegazione molto bella.Ma come si fa ad ottenere `sum (i * (2/3) ** i)` uguale a 6?E `sum ((2/3) ** i)` uguale a 3?
@dokondr Usa la formula per la somma di infinite serie geometriche.$ \ sum_ {n = 1} ^ \ infty nx ^ n = \ frac {x} {(x-1) ^ 2} $ e $ \ sum_ {n = 0} ^ \ infty x ^ n = \ frac {1} {1-x} $.
#5
+5
Sextus Empiricus
2020-01-31 09:45:53 UTC
view on stackexchange narkive permalink

Modo tipico per risolvere questo problema:

La formica prenderà il percorso a e finirà o prenderà il percorso bec e tornerà alla sua posizione di partenza.

Sia $ k $ il numero di volte che la formica ha già preso il percorso b o c. Sia $ T_k $ il valore atteso per il termine del tempo per una formica che ha già impiegato $ k $ volte il percorso. Quindi il valore atteso per una formica con $ k $ passaggi può essere espresso in termini di una formica con $ k + 1 $ passaggi.

$$ T_k = \ underbrace {\ frac {1} {3} 7} _ {\ substack {\ frac {1} {3} th \ text {possibilità di finire con percorso} \\ \ text {a in 7 minuti}}} + \ underbrace {\ frac {1} {3} (T_ {k + 1} + 8)} _ {\ substack {\ frac {1} {3 } th \ text {possibilità di finire con il percorso b} \\ \ text {in 8 minuti} \\ \ text {più ciò di cui ant $ k + 1 $ ha bisogno in media}}} + \ underbrace {\ frac {1} { 3} (T_ {k + 1} +12)} _ {\ substack {\ frac {1} {3} th \ text {possibilità di finire con il percorso c} \\ \ text {in 12 minuti} \\ \ text {più ciò di cui ant $ k + 1 $ ha bisogno in media}}} $$

Poiché le formiche si trovano nella stessa posizione di partenza indipendentemente dalla cronologia (numero di passaggi $ k $ ) il tempo medio è (hai $ T_k = T_ {k + 1} $ che puoi usare per risolvere l'equazione precedente):

$$ T_k = \ frac {1} {3} 7+ \ frac {1} {3} (8 + T_k) + \ frac {1} {3} ( 12 + T_k) $$

e dopo alcune modifiche

$$ T_k = 7 + 8 + 12 = 27 $$


Utilizzo di una media

Puoi risolvere questo problema con un mezzo, una specie di.

  • La formica finisce almeno con il percorso a che richiede almeno 7 minuti
  • Inoltre, la formica ha 2/3 di probabilità di prendere percorsi bo c (ogni volta) che in media prendono $ \ frac {8 + 12} {1 + 1} = 10 $ minuti.

Il numero medio di volte in cui la formica prende i percorsi bec è:

$$ 1 \ cdot \ frac {1} {3} \ left (\ frac {2} {3} \ right) + 2 \ cdot \ frac {1} {3 } \ left (\ frac {2} {3} \ right) ^ 2 + 3 \ cdot \ frac {1} {3} \ left (\ frac {2} {3} \ right) ^ 3 + 4 \ cdot \ frac {1} {3} \ left (\ frac {2} {3} \ right) ^ 4 + .... = \ sum_ {k = 1} ^ \ infty k \ cdot \ frac {1} {3} \ left (\ frac {2} {3} \ right) ^ k = 2 $$

nota che questo è correlato a una distribuzione geometrica e il numero medio di passaggi aggiuntivi necessari alla formica è 2 (e ogni passaggio richiede in media 10 minuti). Quindi la formica prenderà (in media):

$$ \ text {$ 7 $ minuti $ + $ 2 volte $ \ volte $ $ 10 $ minuti $ = 27 $ minuti} $$


È interessante: potresti anche dire che il tempo medio per un singolo passaggio è $ 9 $ minuti (ciò che hai calcolato) e la media numero di passaggi è $ 3 $ , quindi la formica impiega $ 3 \ times 9 = 27 $ minuti (tu eri non molto lontano dalla soluzione).

"È interessante notare che potresti anche dire che il tempo medio per un singolo passaggio è di 9 minuti (quello che hai calcolato) e il numero medio di passaggi è 3, quindi la formica impiega 3 × 9 = 27 minuti (non eri molto lontano dalsoluzione)."Questa soluzione è garantita?O solo un'approssimazione che sembra essere corretta
Dopo aver ragionato su questo problema, sembra che funzioni effettivamente per ogni combinazione di valori.Decisamente inaspettato.
@cruncher, Sono d'accordo con te sul fatto che all'inizio sembra un po 'semplicistico moltiplicare due medie, perché in effetti non è garantito che funzioni ogni volta.Quindi devo ancora esaminare quella "parte interessante 3 × 9 = 27" che sembra essere davvero una felice coincidenza.Ma i minuti 2 × 10 mi sembrano buoni.È possibile moltiplicare il numero medio di passaggi per il tempo medio per passaggio quando sono indipendenti.Sotto il cofano stai sommando ogni possibile combinazione di tempi di passo con ogni possibile numero di passi.
#6
+2
Gregor
2020-01-31 01:03:43 UTC
view on stackexchange narkive permalink

Commentando il post di @Igor F. (reputazione insufficiente in questo subforum per commentare semplicemente):

Entrambi i termini sono serie geometriche:

$ \ sum_ {i = 0} ^ \ infty i \ cdot (\ frac {2} {3}) ^ i \ overset {q = 2/3} {=} \ sum_ {i = 0} ^ \ infty i \ cdot q ^ i = q \ frac {d} {dq} \ sum_ {i = 0} ^ \ infty q ^ i = \ frac {q} {(1-q) ^ 2}, \ text {for} | q | <1 $ , quindi per $ q = \ frac {2} {3} $ questoè uguale a $ 6 $ .

$ \ sum_ {i = 0} ^ \ infty (\ frac {2} {3}) ^ i $ è solo una serie geometrica infinita di base e noiavere $ \ sum_ {i = 0} ^ \ infty c \ cdot q ^ i = \ frac {c} {1-q}, \ text {con costante} c \ text {e} | q | <1 $ , che è $ 3 $ per $ q = \ frac {2} {3} $ e $ c = 1 $ .

#7
  0
rabtrfld
2020-02-01 11:00:35 UTC
view on stackexchange narkive permalink

Ci vogliono sempre $ 7 $ min per avere successo, cosa che accade una volta. Ci vuole una media di $ 10 $ min per fallire. La probabilità di errore è $ 2/3 $ a ogni tentativo o $ (2/3) ^ n $ span> per n tentativi. Quindi il tempo totale è ( $ 7 + 10 \ cdot \ sum_n (2/3) ^ n $ ) min. Che è $ 7 $ min + $ 2 \ cdot 10 $ min $ = 27 $ .



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 4.0 con cui è distribuito.
Loading...