Erwarteter Wert der Wartezeit für den ersten der beiden Busse, die alle 10 und 15 Minuten verkehren

19

Ich bin auf eine Interviewfrage gestoßen:

Es gibt einen roten Zug, der alle 10 Minuten kommt. Alle 15 Minuten fährt ein blauer Zug. Beide starten von einer zufälligen Zeit, so dass Sie keinen Zeitplan haben. Wenn Sie zu einer beliebigen Zeit am Bahnhof ankommen und in einen Zug einsteigen, der als erster kommt, wie lange ist die erwartete Wartezeit?

Shengjie Zhang
quelle
3
Kommen die Züge pünktlich an, jedoch mit unbekannten, gleichmäßig verteilten Phasen, oder folgen sie einem Vergiftungsprozess mit Mitteln von 10 Minuten und 15 Minuten.
Tilefish Poele
1
Der erstere, nicht vergiften.
Shengjie Zhang
7
@Tilefish macht einen wichtigen Kommentar, den jeder beachten sollte. Es gibt keine eindeutige Antwort. Sie müssen davon ausgehen, was "von einer zufälligen Zeit beginnen" bedeuten könnte. (Bedeutet dies, dass sie gleichzeitig oder zu unterschiedlichen unbekannten Zeiten starten? Was würde es rechtfertigen, "unbekannt" als Zufallsvariable mit einer bestimmten bekannten Verteilung zu behandeln?) die Antwort kann von variieren 15/4 zu 25/6 . Eine gleichmäßige Verteilung der Phasendifferenz ergeben würde 35/9 .
whuber
@whuber alle schienen den Kommentar von OP so zu interpretieren, als ob zwei Busse zu zwei verschiedenen zufälligen Zeiten starteten. Dass sie zur gleichen zufälligen Zeit starten würden, scheint eine ungewöhnliche
Einstellung zu
1
@Aksakal. Nicht jeder: Ich nicht und mindestens eine Antwort in diesem Thread nicht - deshalb sehen wir unterschiedliche numerische Antworten. Darüber hinaus räumt fast niemand ein, dass sie eine solche Interpretation der Frage vornehmen mussten, um eine Antwort zu erhalten.
Whuber

Antworten:

15

Eine Möglichkeit, sich dem Problem zu nähern, besteht darin, mit der Überlebensfunktion zu beginnen. Um mindestens Minuten warten zu müssen, müssen Sie mindestens t Minuten auf den roten und den blauen Zug warten . Die Gesamtüberlebensfunktion ist also nur das Produkt der einzelnen Überlebensfunktionen:tt

S(t)=(1t10)(1t15)

was für 0t10 die Wahrscheinlichkeit, dass Sie mindestens Minuten auf den nächsten Zug warten müssen . Dies berücksichtigt die Klarstellung des OP in einer Bemerkung, dass die richtigen Annahmen zu treffen sind, dass sich jeder Zug auf einem festen Fahrplan befindet, der unabhängig vom anderen und von der Ankunftszeit des Reisenden ist, und dass die Phasen der beiden Züge gleichmäßig verteilt sind ,t

Dann erhält man das pdf als

p(t)=(1S(t))=110(1t15)+115(1t10)

Und der erwartete Wert wird auf die übliche Weise erhalten:

,E[t]=010tp(t)dt=010t10(1t15)+t15(1t10)dt=010(t6t275)dt

das klappt bis Minuten.359

Dave
quelle
Dave, kannst du erklären, wie p (t) = (1 - s (t)) '?
Chef1075
Ich kann erklären, dass für Sie S (t) = 1 - F (t), p (t) nur f (t) = F (t) 'ist.
Deep North
4
Die Idee der Überlebensfunktion ist großartig. Aber warum das PDF ableiten, wenn Sie die Überlebensfunktion direkt integrieren können, um die Erwartung zu erhalten? Tatsächlich demonstrieren zwei Drittel dieser Antwort lediglich den Grundsatz der Analysis anhand eines bestimmten Beispiels. Und was rechtfertigt die Verwendung des Produkts, um zu erhalten ? Dahinter steckt eine versteckte Annahme. S
whuber
2
@whuber Ich bevorzuge diesen Ansatz und leite das PDF von der Überlebensfunktion ab, da er Fälle korrekt behandelt, in denen die Domäne der Zufallsvariablen nicht bei 0 beginnt.
Dave
2
(1) Ihre Domain ist positiv. (2) Die Formel lässt sich leicht verallgemeinern. .
whuber
9

Die Antwort lautet Holendie Teile in den Klammern: y<xydy=y2/2| x 0 =x2/2y>xxdy=xy| 15 x =15x-x2 Der Teil ist also: (.)=(y<xydy+

E[t]=xymin(x,y)110115dxdy=x(y<xydy+y>xxdy)110115dx
y<xydy=y2/2|0x=x2/2
y>xxdy=xy|x15=15xx2
SchließlichE[t]= x(15x-x2/2) 1
(.)=(y<xydy+y>xxdy)=15xx2/2
E[t]=x(15xx2/2)110115dx=(15x2/2x3/6)|010110115=(1500/21000/6)110115=510/93.89

Hier ist der zu simulierende MATLAB-Code:

nsim = 10000000;
red= rand(nsim,1)*10;
blue= rand(nsim,1)*15;
nextbus = min([red,blue],[],2);
mean(nextbus)
Aksakal
quelle
1
Sie machen falsche Annahmen über den anfänglichen Startpunkt von Zügen. Wie viele rote und blaue Züge fahren nach Ihrer Logik alle 2 Stunden? Wie viele Züge insgesamt in den 2 Stunden? etc.
Tilefish Poele
1
Können Züge nicht in Minute 0 und in Minute 60 ankommen?
Tilefish Poele
1
Was ist, wenn sie zur gleichen Zeit anfangen, ist das, was ich versuche zu sagen. Was ist, wenn beide in Minute 0 starten? Wie viele Züge kommen an?
Tilefish Poele
1
Die Simulation emuliert die Problemstellung nicht genau. Insbesondere wird die "zufällige Zeit", zu der Sie an der Bushaltestelle erscheinen , nicht modelliert . Als solches verkörpert es mehrere unausgesprochene Annahmen über das Problem.
Whuber
2
@whuber es emuliert die Phase der Busse im Verhältnis zu meiner Ankunft am Bahnhof
Aksakal
4

Assuming each train is on a fixed timetable independent of the other and of the traveller's arrival time, the probability neither train arrives in the first x minutes is 10x10×15x15 for 0x10, which when integrated gives 3593.889 minutes

Alternatively, assuming each train is part of a Poisson process, the joint rate is 115+110=16 trains a minute, making the expected waiting time 6 minutes

Henry
quelle
3
@Dave it's fine if the support is nonnegative real numbers.
Neil G
3
@dave He's missing some justifications, but it's the right solution as long as you assume that the trains arrive is uniformly distributed (i.e., a fixed schedule with known constant inter-train times, but unknown offset). It works with any number of trains. This is the because the expected value of a nonnegative random variable is the integral of its survival function.
Neil G
1
@Dave with one train on a fixed 10 minute timetable independent of the traveller's arrival, you integrate 10x10 over 0x10 to get an expected wait of 5 minutes, while with a Poisson process with rate λ=110 you integrate eλx over 0x< to get an expected wait of 1λ=10 minutes
Henry
1
@NeilG TIL that "the expected value of a non-negative random variable is the integral of the survival function", sort of -- there is some trickiness in that the domain of the random variable needs to start at 0, and if it doesn't intrinsically start at zero(e.g. for a different problem where the inter-arrival times were, say, uniformly distributed between 5 and 10 minutes) you actually have to use a lower bound of 0 when integrating the survival function. (starting at 0 is required in order to get the boundary term to cancel after doing integration by parts)
Dave
3
+1 At this moment, this is the unique answer that is explicit about its assumptions. All the others make some critical assumptions without acknowledging them.
whuber
2

I am probably wrong but assuming that each train's starting-time follows a uniform distribution, I would say that when arriving at the station at a random time the expected waiting time for:

  1. the Red train is E[R]=5 mins
  2. the Blue train is E[B]=7.5 mins
  3. the train that comes the first is E[min(R,B)]=1510(E[B]E[R])=154=3.75 mins


As pointed out in comments, I understood "Both of them start from a random time" as "the two trains start at the same random time". Which is a very limiting assumption.

keepAlive
quelle
1
Thanks! Your got the correct answer. But 3. is still not obvious for me. Could you explain a bit more?
Shengjie Zhang
1
This is not the right answer
Aksakal
1
I think the approach is fine, but your third step doesn't make sense.
Neil G
2
This answer assumes that at some point, the red and blue trains arrive simultaneously: that is, they are in phase. Other answers make a different assumption about the phase.
whuber
2

Suppose that red and blue trains arrive on time according to schedule, with the red schedule beginning Δ minutes after the blue schedule, for some 0Δ<10. For definiteness suppose the first blue train arrives at time t=0.

Assume for now that Δ lies between 0 and 5 minutes. Between t=0 and t=30 minutes we'll see the following trains and interarrival times: blue train, Δ, red train, 10, red train, 5Δ, blue train, Δ+5, red train, 10Δ, blue train. Then the schedule repeats, starting with that last blue train.

If WΔ(t) denotes the waiting time for a passenger arriving at the station at time t, then the plot of WΔ(t) versus t is piecewise linear, with each line segment decaying to zero with slope 1. So the average wait time is the area from 0 to 30 of an array of triangles, divided by 30. This gives

W¯Δ:=130(12[Δ2+102+(5Δ)2+(Δ+5)2+(10Δ)2])=130(2Δ210Δ+125).
Notice that in the above development there is a red train arriving Δ+5 minutes after a blue train. Since the schedule repeats every 30 minutes, conclude W¯Δ=W¯Δ+5, and it suffices to consider 0Δ<5.

If Δ is not constant, but instead a uniformly distributed random variable, we obtain an average average waiting time of

15Δ=05130(2Δ210Δ+125)dΔ=359.
grand_chat
quelle
2

This is a Poisson process. The red train arrives according to a Poisson distribution wIth rate parameter 6/hour.
The blue train also arrives according to a Poisson distribution with rate 4/hour. Red train arrivals and blue train arrivals are independent. Total number of train arrivals Is also Poisson with rate 10/hour. Since the sum of The time between train arrivals is exponential with mean 6 minutes. Since the exponential mean is the reciprocal of the Poisson rate parameter. Since the exponential distribution is memoryless, your expected wait time is 6 minutes.

Alison
quelle
The Poisson is an assumption that was not specified by the OP. But some assumption like this is necessary. The logic is impeccable. +1 I like this solution.
Michael R. Chernick
1
OP said specifically in comments that the process is not Poisson
Aksakal