# Suppose $X_1, X_2, \dotsc, X_n$ are i.i.d. random variables. When is the sequence expected to decrease for the first time?

As suggested in the title. Suppose $X_1, X_2, \dotsc, X_n$ are continuous i.i.d. random variables with pdf $f$. Consider the event that $X_1 \leq X_2 \dotsc \leq X_{N-1} > X_N$, $N \geq 2$, thus $N$ is when the sequence decreases for the first time. Then what's the value of $E[N]$?

I tried to evaluate $P[N = i]$ first. I have \begin{align*} P[N = 2] & = \int_{-\infty}^{\infty} f(x)F(x)dx \\ & = \frac{F(x)^2}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{2} \\ P[N = 3] & = \int_{-\infty}^{\infty} f(x)\int_x^{\infty}f(y)F(y)dydx \\ & = \int_{-\infty}^{\infty}f(x)\frac{1-F(x)^2}{2}dx \\ & = \frac{F(x)-F(x)^3/3}{2}\Large|_{-\infty}^{\infty} \\ & = \frac{1}{3} \end{align*} Similarly, I got $P[N = 4] = \frac{1}{8}$. As $i$ gets large, the calculation gets more complicated and I can't find the pattern. Can anyone suggest how I should proceed?

• Is this a question from a course or textbook? If so, please add the [self-study] tag & read its wiki. – Silverfish Apr 29 '15 at 22:41
• A hint. Consider the ranks, which should be randomly permuted. There are $n!$ arrangements of the ranks $1, 2, \dots, n$. There is only one permutation in which the $X_i$ are all increasing. For $n \geq 2$ there are $n-1$ observations which are not the maximum, which we can then take out and place at the end to generate a sequence which is increasing until the penultimate position, then decreases. Hence the probability of this is $n-1$ out of ... ? That should sort you out with the $1/2$, $1/3$ and $1/8$ that you found, and give you a simple formula to generalise it. The sum is quite easy. – Silverfish Apr 29 '15 at 22:42
• (And if you can't guess the result of the series you'll sum to find the mean, perhaps you should run a simulation of it. You'll recognise the first couple of decimal places.) – Silverfish Apr 29 '15 at 22:53
• It's a problem from the exam I took today. Thank you for the hint, now I figured out how to solve it. – Hao The Cabbage Apr 29 '15 at 22:59
• stats.stackexchange.com/questions/51429/… is essentially a duplicate. Although it concerns only a uniform distribution, it is almost trivial to show the two questions are equivalent. (One way: apply the probability integral transform to the $X_i$.) – whuber Apr 30 '15 at 17:19

If $\{X_i\}_{i\geq 1}$ is an exchangeable sequence of random variables and $$N=\min\,\{n:X_{n-1}>X_n\},$$ then $N\geq n$ if and ony if $X_1\leq X_2\leq\dots\leq X_{n-1}$. Therefore, $$\Pr(N\geq n) = \Pr(X_1\leq X_2\leq\dots\leq X_{n-1})=\frac{1}{(n-1)!}, \qquad (*)$$ by symmetry. Hence, $\mathrm{E}[N]=\sum_{n=1}^\infty \Pr(N\geq n)=e\approx 2.71828\dots$.

P.S. People asked about the proof of $(*)$. Since the sequence is exchangeable, it must be that, for any permutation $\pi:\{1,\dots,n-1\}\to\{1,\dots,n-1\}$, we have $$\Pr(X_1\leq X_2\leq\dots\leq X_{n-1}) = \Pr(X_{\pi(1)}\leq X_{\pi(2)}\leq\dots\leq X_{\pi(n-1)}).$$ Since we have $(n-1)!$ possible permutations, the result follows.

# Monte Carlo
N <- 10^6
dec <- numeric(N)
for (i in 1:N) {
j <- 1
x <- rnorm(1, 0, 1) # plug your favorite distribution here!
repeat {
j <- j + 1
y <- rnorm(1, 0, 1)
if (y < x) {
dec[i] <- j
break
}
x <- y
}
}
cat(mean(dec), "\n")
# A good example of how to program C in R!
• I like this - it's a reminder we often don't need to find the individual $\Pr(Y=y)$ to find the mean of Y and it can be more helpful to go straight for $\Pr(Y \geq y)$ instead. – Silverfish Apr 30 '15 at 6:58
• +1 -- but this doesn't actually answer the question, which supposes a given finite number of $X_i$. Nevertheless the technique applies to the finite case in an obvious way. – whuber May 13 '15 at 19:43
• A little confusing, isn't it? The OP mentions a "sequence". But you're right. By the way, is it intuitive to you that the result should be "universal" (as it is), in the sense that it doesn't depend on the distribution of the (identicaly distributed) $X_i$'s? – Zen May 13 '15 at 20:10
• Actually, independence is not needed. Exchangeability is enough. The result is stronger. I'll add this to my answer. – Zen May 13 '15 at 20:15
• It's intuitive that it's universal for continuous variables. One way to make this obvious is to recognize that the event remains unchanged a.e. upon applying the probability integral transform, which reduces it to the case where the variables have a common uniform distribution. – whuber May 13 '15 at 21:30

As suggested by Silverfish, I'm posting the solution below. \begin{align*} P[N = i] & = P[X_1 \leq X_2 \dotsc \leq X_{i-1} > X_i] \\ & = P[X_1 \leq X_2 \dotsc \leq X_{i-1}] - P[X_1 \leq X_2 \dotsc \leq X_{i-1} \leq X_i] \\ & = \frac{1}{(i-1)!} - \frac{1}{i!} \end{align*} And \begin{align*} P[N \geq i] & = 1 - P[N < i] \\ & = 1 - \left(1 -\frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \cdots +\frac{1}{(i-2)!} - \frac{1}{(i-1)!}\right)\\ & = \frac{1}{(i-1)!} \\ \end{align*}

Thus $E[N] = \sum_{i = 1}^{\infty}P[N \geq i] = \sum_{i = 1}^{\infty}\frac{1}{(i-1)!} = e$.

An alternative argument: there is only one ordering of the $X_i$ which is increasing, out of the $n!$ possible permutations of $X_1, \dots, X_n$. We are interested in orderings which increase until the penultimate position, and then decrease: this requires the maximum to be in position $n-1$, and one of the $n-1$ other $X_i$ to be in the final position. Since there are $n-1$ ways to pick out one of the first $n-1$ terms in our ordered sequence and move it to the final position, then the probability is:

$$\Pr(N=n) = \frac{n-1}{n!}$$

Note $\Pr(N=2) = \frac{2-1}{2!} = \frac{1}{2}$, $\Pr(N=3) = \frac{3-1}{3!} = \frac{1}{3}$ and $\Pr(N=4) = \frac{4-1}{4!} = \frac{1}{8}$ so this is consistent with the results found by integration.

To find the expected value of $N$ we can use:

$$\mathbb{E}(N) = \sum_{n=2}^{\infty} n \Pr(N=n) = \sum_{n=2}^{\infty} \frac{n(n-1)}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!}= \sum_{k=0}^{\infty} \frac{1}{k!} = e$$

(To make the summation more obvious I have used $k=n-2$; for readers unfamiliar with this sum, take the Taylor series $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$ and substitute $x=1$.)

We can check the result by simulation, here is some code in R:

firstDecrease <- function(x) {
counter <- 2
a <- runif(1)
b <- runif(1)
while(a < b){
counter <- counter + 1
a <- b
b <- runif(1)
}
return(counter)
}

mean(mapply(firstDecrease, 1:1e7))

This returned 2.718347, close enough to 2.71828 to satisfy me.

EDIT: My answer is incorrect. I am leaving it as an example of how easy a seemingly simple question like this is to misinterpret.

I don't think your math is correct for the case $P[N=4]$. We can check this via a simple simulation:

n=50000
flag <- rep(NA, n)
order <- 3
for (i in 1:n) {
x<-rnorm(100)
flag[i] <- all(x[order] < x[1:(order-1)])==T
}
sum(flag)/n

Gives us:

> sum(flag)/n
[1] 0.33326

Changing the order term to 4 get us:

> sum(flag)/n
[1] 0.25208

And 5:

> sum(flag)/n
[1] 0.2023

So if we trust our simulation results, it looks like the pattern is that $P[N = X] = \frac{1}{x}$. But this makes sense as well, since what you are really asking is what is the probability that any given observation in a subset of all your observations is the minimum observation (if we are assuming i.i.d. then we are assuming exchangability and so the order is arbitary). One of them has to be the minimum, and so really the question is what is probability that any observation selected at random is the minimum. This is just a simple binomial process.

• You've slightly misinterpreted the question, if my reading of it is correct - we need the final $X_n$ to be anything but the maximum (not necessarily the minimum) while the first $n-1$ of the $X_i$ must be in increasing order, so the one in position $n-1$ is the maximum. – Silverfish Apr 29 '15 at 23:04
• I think that is a bit more than a slight misinterpretation. You're correct, that I'm incorrect. – Dalton Hance Apr 29 '15 at 23:11