An interview question that was relayed to me by a colleague:
A machine beeps exactly 5 times within a time span of 10 minutes. However, the distribution of these 5 beeps across the entire time span is fully randomized - any distribution of the 5 beeps across the 10 minutes is equally likely.
You heard the 3rd beep, then after exactly 1 minute you heard the 4th beep. What is the expected time remaining until the 5th beep?
Create a clock with a hand that covers 10 minutes in one full revolution. Mark time 0 at the top. The assumptions amount to marking those five beeps independently and uniformly at random around the clock, creating six marks.
This picture should make it obvious that the distributions of the six gaps between the marks are identical. It is immediate that their (unconditional) expectations are the same and must sum to the full time, so each expected gap length is $10/6$ minutes. It makes no difference whether you heard the third beep, or the second, or whatever: the question is tantamount to asking the expected time to the next beep around the clock, given that the preceding gap was one-tenth of the time.
This leaves five gaps uniformly spanning nine-tenths of the remaining time. Again, each must have the same expectation, now equal to one-fifth of nine-tenths of the time. Thus, the answer is $1.8$ minutes.
These plots summarize a simulation of 10,000 independent iterations of this beeping experiment. The histogram at left confirms the beeps were uniformly distributed (within random variation). The five scatterplots compare each gap with its successor (in terms of the total time, so one unit is ten minutes). (Gap 0 is the time of the first beep; Gap 5 is the time from the last beep until the end of the full time period.)
Each plot is decorated, in red, with the Loess smooth of the data. (It fits a general curve rather than forcing a straight line). Their straightness strongly suggests the expectation of the next gap is a linear function of the preceding gap, descending from $1/5=0.2$ of the total time to $0$. The similarities among these scatterplots bear out the claim that the joint gap distributions are all the same, regardless of the location of the gap. The conditional expectation where the preceding gap was $1/10$, shown with the vertical blue lines, must be $(1/10)\times 0 + (1-1/10)\times 0.2 = 0.18$, or $1.8$ minutes.
(A formal rigorous explanation is that the order statistics form a Markov chain in which the order statistics preceding a particular one--a given "mark"--are conditionally independent of those following that mark. See Order Statistics and Related Models by Lopez Blazquez, Balakrishnan, Crmer, and Kamps at http://statmath.wu.ac.at/courses/balakrishnan/OrderStatsandRecords.pdf.)
This R code generated the illustration. Simple modifications at the beginning make it usable for studying other numbers of beeps in more or less detail.
n <- 1e4
n.sample <- 6 # One larger than the number of beeps
#
# Generate data.
# This is a fast way to generate uniform[0,1] order statistics,
# avoiding an explicit sorting operation.
#
x <- matrix(rexp(n*n.sample), nrow=n.sample) # IID exponential
x <- apply(x, 2, function(y) cumsum(y))
x <- t(x) / x[n.sample, ] # Order stats of IID uniform
#
# Display the beep distribution.
#
par(mfrow=c(1,n.sample))
hist(x[, -n.sample], freq=FALSE, main="Time", main="Histogram of all Beeps")
X <- as.data.frame(cbind(x[, 1], x[, -1] - x[, -n.sample])) # The gaps
names(X) <- paste0("Gap.", 1:n.sample - 1)
#
# Display the gap-to-gap scatterplots.
#
for (i in 1:(n.sample-1)) {
Y <- X[, names(X)[0:1 + i]]
plot(Y[, 1], Y[, 2], asp=1, xlim=0:1, ylim=0:1,
pch=19, cex=0.5, col="#00000004",
xlab=names(Y)[1], ylab=names(Y)[2],
main="Gap Comparison")
abline(v=0.1, col="Blue")
f <- as.formula(paste(rev(names(Y)), collapse="~"))
if (n <= 1e4) {
fit <- loess(f, data=Y)
} else { # Loess will be too slow
fit <- lm(f, data=Y)
}
X.hat <- data.frame(V=seq(0, 1, length.out=101))
names(X.hat) <- names(Y)[1]
y.hat <- predict(fit, newdata=X.hat)
lines(X.hat[, 1], y.hat, col="Red", lwd=2)
}
par(mfrow=c(1,1))
