Fråga:
Förväntat värde på väntetiden för den första av de två bussarna som kör var 10: e och 15: e minut
Shengjie Zhang
2017-09-27 04:41:57 UTC
view on stackexchange narkive permalink

Jag stötte på en intervjufråga:

Det finns ett rött tåg som kommer var tionde minut.Det finns ett blått tåg som kommer var 15: e minut.Båda börjar från en slumpmässig tid så att du inte har något schema.Om du anländer till stationen vid en slumpmässig tid och går på ett tåg som kommer först, vad är förväntad väntetid?

Kommer tågen fram i tid men med okända lika fördelade faser, eller följer de en poissonprocess med medel 10 minuter och 15 minuter.
Den förra, inte poisson.
@Tilefish gör en viktig kommentar som alla borde vara uppmärksamma på.** Det finns inget definitivt svar. ** Du måste anta vad "börja från en slumpmässig tid" kan betyda.(Betyder det att de börjar samtidigt eller att de börjar vid olika okända tider? Vad skulle motivera att "okänt" behandlas som en slumpmässig variabel med en bestämd känd fördelning?) Som en funktion av deras fasskillnad (som bara betyder modulo 5 minuter),svaret kan variera från $ 15/4 $ till $ 25/6 $.En enhetlig fördelning av fasskillnaden skulle ge $ 35/9 $.
@whuber alla tycktes tolka OP: s kommentar som om två bussar startade vid två slumpmässiga tider.Att de skulle börja vid samma slumpmässiga tid verkar som ett ovanligt tag
@Aksakal.Inte alla: Det gör jag inte och åtminstone ett svar i den här tråden gör det inte - det är därför vi ser olika numeriska svar.Dessutom erkänner nästan ingen att de var tvungna att göra en sådan tolkning av frågan för att få svar.
Sex svar:
Dave
2017-09-27 09:12:20 UTC
view on stackexchange narkive permalink

Ett sätt att närma sig problemet är att börja med överlevnadsfunktionen. För att behöva vänta minst $ t $ minuter måste du vänta i minst $ t $ minuter för både det röda och det blå tåget. Således är den övergripande överlevnadsfunktionen bara en produkt av de enskilda överlevnadsfunktionerna:

$$ S (t) = \ left (1 - \ frac {t} {10} \ right) \ left (1- \ frac {t} {15} \ right) $$

vilket för $ 0 \ le t \ le 10 $ är sannolikheten att du måste vänta minst $ t $ minuter för nästa tåg. Detta tar hänsyn till förtydligandet av OP i en kommentar att de korrekta antagandena är att varje tåg är på en fast tidtabell oberoende av det andra och av resenärens ankomsttid, och att faserna i de två tågen är jämnt fördelade ,

Sedan erhålls pdf som

$$ p (t) = (1-S (t)) '= \ frac {1} {10} \ left (1- \ frac {t} {15} \ right) + \ frac {1} {15} \ left (1- \ frac {t} {10} \ right) $$

Och det förväntade värdet erhålls på vanligt sätt:

$ E [t] = \ int_0 ^ {10} tp (t) dt = \ int_0 ^ {10} \ frac {t} {10} \ left (1- \ frac {t} {15} \ right ) + \ frac {t} {15} \ left (1- \ frac {t} {10} \ right) dt = \ int_0 ^ {10} \ left (\ frac {t} {6} - \ frac {t ^ 2} {75} \ höger) dt $,

som fungerar till $ \ frac {35} {9} $ minuter.

Dave, kan du förklara hur p (t) = (1- s (t)) '?
Jag kan förklara att för dig är S (t) = 1-F (t), p (t) bara f (t) = F (t) '.
Överlevnadsfunktionsidén är fantastisk.Men varför härleda PDF-filen när du direkt kan integrera överlevnadsfunktionen för att uppnå förväntningarna?I själva verket visar två tredjedelar av detta svar bara den grundläggande teoremet för kalkyl med ett särskilt exempel.Och vad motiverar att använda produkten för att få $ S $?Det finns ett dolt antagande bakom det.
@whuber Jag föredrar detta tillvägagångssätt, härleder PDF-filen från överlevnadsfunktionen, eftersom den korrekt hanterar fall där domänen för den slumpmässiga variabeln inte börjar vid 0.
(1) Din domän är positiv.(2) Formeln är [lätt generaliserad.] (Https://stats.stackexchange.com/a/222497/919).
Aksakal
2017-09-27 07:37:55 UTC
view on stackexchange narkive permalink

Svaret är $$ E [t] = \ int_x \ int_y \ min (x, y) \ frac 1 {10} \ frac 1 {15} dx dy = \ int_x \ left (\ int_ {y<x} ydy +\ int_ {y>x} xdy \ höger) \ frac 1 {10} \ frac 1 {15} dx $$ Få delarna inuti paranteserna: $$ \ int_ {y<x} ydy = y ^ 2/2 | _0 ^ x = x ^ 2/2 $$ $$ \ int_ {y>x} xdy = xy | _x ^ {15} = 15x-x ^ 2 $$ Så delen är: $$ (.) = \ left (\ int_ {y<x} ydy + \ int_ {y>x} xdy \ right) = 15x-x ^ 2/2 $$ Slutligen, $$ E [t] = \ int_x (15x-x ^ 2/2) \ frac 1 {10} \ frac 1 {15} dx = (15x ^ 2/2-x ^ 3/6) | _0 ^ {10} \ frac 1 {10} \ frac 1 {15} \\ = (1500 / 2-1000 / 6) \ frac 1 {10} \ frac 1 {15} = 5-10 / 9 \ ca 3,89 $$

Här är MATLAB-koden att simulera:

  nsim = 10000000;
röd = rand (nsim, 1) * 10;
blå = rand (nsim, 1) * 15;
nästa buss = min ([röd, blå], [], 2);
medelvärde (nästa buss)
 
Du antar felaktiga antaganden om tågens ursprungliga startpunkt.dvs. med din logik, hur många röda och blåa tåg kommer varannan timme?Hur många tåg totalt under de två timmarna?etc.
Kan tåg inte komma fram till minut 0 och minut 60?
vad sägs om de börjar samtidigt är det jag försöker säga.Tänk om de båda börjar vid minut 0. Hur många tåg anländer har du?
+1 ändra din simulering till R nsim = 10000000 röd = runif (nsim, 0,10) blå = runif (nsim, 0,15) nästa buss = pmin (röd, blå) medelvärde (nästa buss)
Simuleringen efterliknar inte exakt problemförklaringen.I synnerhet modellerar den inte den "slumpmässiga tiden" då * du * visas på busstationen.Som sådan förkroppsligar det flera osäkra antaganden om problemet.
@whuber det efterliknar fasen av bussar i förhållande till min ankomst till stationen
Rätt - och därmed antar det ett kritiskt antagande om deras relativa starttider.Svaret beror på det.Det kunde mycket väl ha varit annorlunda.Detta är en anledning till att simuleringar borde försöka sitt bästa för att modellera problemet * exakt * snarare än att förlita sig på sådana intuitiva språng av förståelse.överraska dig genom att genom dess avvikelse från vad du förväntar dig avslöja antaganden som du kanske inte har insett att du gjorde.
Henry
2017-09-27 14:54:31 UTC
view on stackexchange narkive permalink

Förutsatt att varje tåg är på en fast tidtabell oberoende av det andra och av resenärens ankomsttid, är sannolikheten att inget tåg anländer under de första $ x $ minuterna $ \ frac {10-x} {10} \ gånger \ frac{15-x} {15} $ för $ 0 \ le x \ le 10 $, som när det är integrerat ger $ \ frac {35} 9 \ ca 3.889 $ minuter

Alternativt, förutsatt att varje tåg är en del av en Poisson-process, är den gemensamma hastigheten $ \ frac {1} {15} + \ frac {1} {10} = \ frac {1} {6} $ tåg per minutvilket gör den förväntade väntetiden $ 6 $ minuter

Att bara integrera överlevnadsfunktionen ger inte rätt svar för allmänna sannolikhetsfördelningar.
@Dave det är bra om stödet är icke-negativa reella tal.
@NeilG skulle denna metod fungera om det bara fanns ett tåg?Eller om tiden mellan tågen fördelades av Poisson?Jag förstår inte hur det kunde.
@dave Han saknar några motiveringar, men det är rätt lösning så länge du antar att tågen anländer är jämnt fördelad (dvs ett fast schema med kända konstanta tågtider men okänd förskjutning).Den fungerar med valfritt antal tåg.Detta beror på att det förväntade värdet för en icke-negativ slumpmässig variabel är integralen i dess överlevnadsfunktion.
@Dave med ett tåg på en fast $ 10 $ minut tidtabell oberoende av resenärens ankomst, integrerar du $ \ frac {10-x} {10} $ över $ 0 \ le x \ le 10 $ för att få en förväntad väntan på $ 5 $ minuter,medan du med en Poisson-process med hastighet $ \ lambda = \ frac1 {10} $ integrerar $ e ^ {- \ lambda x} $ över $ 0 \ le x \ lt \ infty $ för att få en förväntad väntan på $ \ frac1 \ lambda= 10 $ minuter
@NeilG TIL att "det förväntade värdet på en icke-negativ slumpmässig variabel är integralen i överlevnadsfunktionen", typ av - det finns en del knepighet i att domänen för den slumpmässiga variabeln måste börja på $ 0 $, och om den inteStarta inte i sig vid noll (t.ex. för ett annat problem där inter-ankomsttiderna var, säg, jämnt fördelade mellan 5 och 10 minuter) måste du faktiskt använda en nedre gräns på 0 när du integrerar överlevnadsfunktionen.(start vid 0 krävs för att få gränsperioden att avbrytas efter att ha integrerat med delar)
+1 För närvarande är detta det unika svaret som uttryckligen antar dess antaganden.* Alla * de andra gör några kritiska antaganden utan att erkänna dem.
keepAlive
2017-09-27 07:31:23 UTC
view on stackexchange narkive permalink

Jag har förmodligen fel men antar att varje tågs starttid följer en enhetlig fördelning, skulle jag säga att när jag anländer till stationen vid en slumpmässig tid förväntad väntetid på:

  1. $ R $ ed-tåget är $ \ mathbb {E} [R] = 5 $ min
  2. $ B $ lue-tåget är $ \ mathbb {E} [B] = 7,5 $ min
  3. tåget som kommer först är $ \ mathbb {E} [\ min (R, B)] = \ frac {15} {10} (\ mathbb {E} [B] - \ mathbb {E} [R]) = \ frac {15} {4} = 3,75 $ minuter


Som påpekades i kommentarer förstod jag "Båda startar från en slumpmässig tid" som "de två tågen börjar vid samma slumpmässiga tid".Vilket är ett mycket begränsande antagande.
Tack!Du har rätt svar.Men 3. är fortfarande inte självklart för mig.Kan du förklara lite mer?
Detta är inte rätt svar
Jag tycker att metoden är bra, men ditt tredje steg är inte meningsfullt.
Detta svar antar att de röda och blåa tågen någon gång kommer fram samtidigt, det vill säga de är i fas.Andra svar ger ett annat antagande om fasen.
grand_chat
2017-09-28 11:49:26 UTC
view on stackexchange narkive permalink

Antag att röda och blå tåg anländer i tid enligt schemat, med det röda schemat som börjar $ \ Delta $ minuter efter det blå schemat, för ungefär $ 0 \ le \ Delta<10 $. Förvisso antar att det första blåa tåget anländer vid tiden $ t = 0 $.

Antag nu att $ \ Delta $ ligger mellan $ 0 $ och $ 5 $ minuter. Mellan $ t = 0 $ och $ t = 30 $ minuter ser vi följande tåg och interarrival tider: blåttåg, $ \ Delta $, rött tåg, $ 10 $, rött tåg, $ 5- \ Delta $, blåttåg, $ \ Delta + 5 $, rött tåg, $ 10- \ Delta $, blåttåg. Då upprepas schemat och börjar med det sista blå tåget.

Om $ W_ \ Delta (t) $ betecknar väntetiden för en passagerare som anländer till stationen vid tidpunkten $ t $, så är diagrammet för $ W_ \ Delta (t) $ mot $ t $ styckvis linjärt, med varje linjesegment förfaller till noll med lutningen $ -1 $. Så den genomsnittliga väntetiden är området från $ 0 $ till $ 30 $ för en rad trianglar, dividerat med $ 30 $. Detta ger $$ \ begin {align} \ bar W_ \ Delta &: = \ frac1 {30} \ left (\ frac12 [\ Delta ^ 2 + 10 ^ 2 + (5- \ Delta) ^ 2 + (\ Delta + 5) ^ 2 + (10- \ Delta) ^ 2] \ höger) \\ & = \ frac1 {30} (2 \ Delta ^ 2-10 \ Delta + 125). \ end {align} $$ Observera att i ovanstående utveckling finns ett rött tåg som anländer $ \ Delta + 5 $ minuter efter ett blått tåg. Eftersom schemat upprepas var 30: e minut, avsluta $ \ bar W_ \ Delta = \ bar W _ {\ Delta + 5} $, och det räcker att överväga $ 0 \ le \ Delta<5 $.

Om $ \ Delta $ inte är konstant utan istället en jämnt fördelad slumpmässig variabel, får vi en genomsnittlig genomsnittlig väntetid på $$ \ frac15 \ int _ {\ Delta = 0} ^ 5 \ frac1 {30} (2 \ Delta ^ 2-10 \ Delta + 125) \, d \ Delta = \ frac {35} 9. $$

Alison
2017-09-29 07:56:52 UTC
view on stackexchange narkive permalink

Detta är en Poisson-process. Det röda tåget anländer enligt en Poisson-fördelning med parameter 6 / timme.
Det blå tåget anländer också enligt en Poisson-fördelning med hastighet 4 / timme. Ankomster av röda tåg och blå tågankomster är oberoende. Totalt antal tågankomster är också Poisson med hastighet 10 / timme.Sedan summan av Tiden mellan tåg anländer är exponentiell med genomsnittliga 6 minuter.Eftersom det exponentiella medelvärdet är det ömsesidiga av Poisson-hastighetsparametern. Eftersom den exponentiella distributionen är minneslös är din förväntade väntetid 6 minuter.

Poisson är ett antagande som inte specificerades av OP.Men något sådant antagande är nödvändigt.Logiken är oklanderlig.+1 Jag gillar den här lösningen.
OP sa specifikt i kommentarer att processen inte är Poisson


Denna fråga och svar översattes automatiskt från det engelska språket.Det ursprungliga innehållet finns tillgängligt på stackexchange, vilket vi tackar för cc by-sa 3.0-licensen som det distribueras under.
Loading...