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?

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

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.