Random Sequence of Alternating Increase/Decrease Numbers

Question

The problem statement: Repeatedly pick a random number (uniformly-distributed) between $0$ and $1$. Keeping going while the second number is smaller than the first, the third number is larger than the second, the fourth number is smaller than the third, the fifth number is larger than the fourth, etc. In other words, the numbers must alternate between decreasing and increasing. Stop when this alternating pattern is broken. What is the expected value of the number of random numbers picked?

I would think that the problem requires integrals, specifically integrating the expected value over $0$ to $1$. However, I am stuck at arriving at this expected value, since, if $x_0, x_1, x_2, \cdots, x_n$ is the sequence of numbers picked, the probability is $1-x_0$ that the number of numbers picked is $2$, the probability is $x_1$ that the number of numbers picked is $3$, the probability is $1-x_2$ that the expected number of numbers picked is $4$, the probability is $x_3$ that the number of numbers picked is $5$, etc. I can't figure out how to set up an integral from this. Any ideas?

Answer 1

A key realization here is that the numbers themselves don't matter, and neither does the fact that this is a uniform distribution. The answer would be the same for any continuous distribution. All that matters is the rank ordering of the numbers. Given that any N distinct numbers were chosen, all $N!$ orderings of those numbers have equal probability. So the problem reduces to counting the ways $A_N$ to arrange the $N$ integers $1,2,\dots,N$ in such a way that they alternate decreasing and increasing starting with decreasing. Then our answer is simply

$$E(picks) = 2 + \sum_{k=2}^{\infty}P(N \gt k)$$

$$=\sum_{N=0}^{\infty}\frac{A_N}{N!}$$

where $A_0 = 1$, and $A_1 = 1$, and we can easily verify

$A_2 = 1$

$A_3 = 2$

$A_4 = 5$

$A_5 = 16$

These produce the terms

$1 + 1 + 1/2 + 1/3 + 5/24 + 2/15 + \dots$

consistent with what has been computed previously. Determining the others is a well-known combinatorics problem known as counting alternating permutations or André's problem whose sequence is given by AEIS A000111 and known as the Euler zigzag numbers:

1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981, 1903757312, 19391512145, 209865342976, 2404879675441, 29088885112832, 370371188237525, 4951498053124096, 69348874393137901, 1015423886506852352, 15514534163557086905, 246921480190207983616, 4087072509293123892361, ...

Using these values gives an expected value of approximately $3.41$ picks, in agreement with simulation. The generating function for these numbers turns out to be sec(x) + tan(x), so the exact answer is sec(1) + tan(1).

This problem should be tagged for combinatorics, permutations, alternating permutations, Euler zigzag numbers, and Andrés problem.

Answer 2

The chance that you pick at least two numbers is $1$. The chance you pull a third is $x_0$, because that is the room that $x_1$ has to be less. To make this a probability, we integrate over $x_0$, getting $\int_0^1(1-x_0)dx_0=\frac 12$. The chance that we pick a fourth is $1-x_1$, but the distribution of $x_1$ is not uniform. On a relative basis, the probability of a given value of $x_1$ is $(1-x_1)$ or on a normalized basis we have $P(x_1)=2(1-x_1)$ The chance that we pick a fourth given that we picked three is then $\int_0^12(1-x_1)^2dx_1=\frac 23$, so the overall chance of selecting at least $4$ is $\frac 13$

Answer 3

EDITED: Let $N$ be the random variable giving the numbers of terms in a monotonic alternate sequence of uniformly distributed random numbers in [0,1).

N takes the values $2,3,4, \ldots n, \ldots $. In order to get the probability distribution of $N$, we denote by $U_1, U_2, \ldots, U_n, \ldots$ a sequence of i.i.d. random variables, $U_n\sim Unif[0,1)$, and by $D_1=\{(x,y)\in[0,1)^2\:|\: x>y\}$, $D_2=\{(x,y)\in[0,1)^2\:|\: x\leq y\}$, the regions of interest within the unit square $[0,1)^2$.

For the simplicity of writing I do not insert the sign '=' to characterize a pair in $D_2$.

Let us compute $P((U_2, U_3)\in D_2|((U_1, U_2)\in D_1)=\dfrac{P(U_2<U_3, U_2<U_1)}{P(U_2<U_1)}=\dfrac{P(U_2<min(U_1, U_3))}{1/2}$.

But $P(U_2< min(U_2, U_3))=P(U_1, U_2, U_3)\in \Delta_m)$, with $\Delta_m=\{(x_1, x_2, x_3)\in [0,1)^3\:|\: x_2\leq min(x_1,x_3)\}$.

Due to the symmetry we plot the surface $x_3= min(x_1, x_2)$, and compute the volume of the region in the unit cube characterized by $x_3\leq min(x_1, x_2)$.

This region is a solid pyramid having the unit square as base, and height length equal to 1. Hence its volume is $1/3$ and we conclude that $P((U_2, U_3)\in D_2|((U_1, U_2)\in D_1)=\dfrac{1/3}{1/2}=2/3$.

The probability $P((U_2, U_3)\in D_1|((U_1, U_2)\in D_1))=\dfrac{P(U_3<U_2, U_2<U_1)}{1/2}=\dfrac{1/6}{1/2}=1/3$.

By symmetry we get $P((U_2, U_3)\in D_1|((U_1, U_2)\in D_2)=\dfrac{1/3}{1/2}=2/3$.

and $P((U_2, U_3)\in D_2|((U_1, U_2)\in D_2))=1/3$.

It is simply to see that only the present position of a point influences the probability that the next one lands in some region $D_1, D_2$. i.e. this flight from one region to another can be interpreted as a Markov chain having the states $D_1, D_2$ and the transition matrix

$T=\left[\begin{array}{ll} 1/3&2/3\\ 2/3&1/3\end{array}\right]$

Let us denote by $X_n$ this Markov chain.

Now we can compute the probability that an admissible sequence has the length equal to $k$, $k=2,3, \ldots$:

$P(N=2)=P(X_1=D_1, X_2=D_1)=T_{11}=1/3$.

$P(N=3)=P(X_1=D_1, X_2=D_2, X_3=D_2)=T_{12}T_{22}=\dfrac{2}{3}\dfrac{1}{3}$

$P(N=4)=P(X_1=D_1, X_2=D_2, X_3=D_1, X_4=D_1)=\dfrac{2^2}{3^2}\dfrac{1}{3}$

Analogously we get: $P(N=k)=(\dfrac{2}{3})^{k-2}\dfrac{1}{3}$, for any $k\geq 2$.

We notice that our random variable can be expressed as $N=G+1$, where $G$ is a geometric random variable of parameter $p=1/3$. Hence $M(N)=M(G)+1=\dfrac{1}{p}+1=4$