Probability – Expectation for Game Choosing Uniformly in [0,1] Until Decrease

expectationpr.probabilityprobability distributionsst.statistics

We are playing a game where we keep on choosing a number from the uniform distribution U(0,1). The game goes on until we have the current number less than the previously picked number, i.e. the game will stop if we get a number less than the previous number and will continue if we get a number greater than equal to the previous number. What is the expected value of the final number?

Best Answer

Let \begin{equation*} N:=\inf\{n\ge2\colon X_{n-1}>X_n\}, \end{equation*} where $X_1,X_2,\dots$ are independent random variables uniformly distributed on $[0,1]$. We want to find \begin{equation*} EX_N=\sum_{n=2}^\infty EX_n\,1(X_1\le\cdots\le X_{n-1}>X_n). \tag{1} \end{equation*}

We have \begin{equation*} \begin{aligned} &EX_n\,1(X_1\le\cdots\le X_{n-1}>X_n) \\ &=EX_n\,1(X_1\le\cdots\le X_{n-1}) \\ &-EX_n\,1(X_1\le\cdots\le X_{n-1}\le X_n), \end{aligned} \tag{2} \end{equation*} \begin{equation*} \begin{aligned} &EX_n\,1(X_1\le\cdots\le X_{n-1}) \\ &=EX_n\,P(X_1\le\cdots\le X_{n-1})=\frac12\,\frac1{(n-1)!}. \end{aligned} \tag{3} \end{equation*}

The calculation of $EX_n\,1(X_1\le\cdots\le X_{n-1}\le X_n)$ is more involved than that of $EX_n\,1(X_1\le\cdots\le X_{n-1})$, because $X_n$ and $1(X_1\le\cdots\le X_{n-1}\le X_n)$ are not independent -- in contrast with $X_n$ and $1(X_1\le\cdots\le X_{n-1})$. The main idea in the calculation of $EX_n\,1(X_1\le\cdots\le X_{n-1}\le X_n)$ is to express $X_n$ in terms of indicators, to allow a better blending with the indicator $1(X_1\le\cdots\le X_{n-1}\le X_n)$. Toward that end, note that $X_n=\int_0^{X_n} dx=\int_0^1 dx\,1(X_n>x)$ and $$1(X_n>x)1(X_1\le\cdots\le X_{n-1}\le X_n) \\ =1(X_1\le\cdots\le X_{n-1}\le X_n>x),$$ so that $$X_n\,1(X_1\le\cdots\le X_{n-1}\le X_n) \\ =\int_0^1 dx\,1(X_1\le\cdots\le X_{n-1}\le X_n>x),$$ the latter expression being indeed in terms of the indicators $1(X_1\le\cdots\le X_{n-1}\le X_n>x)$. Hence,
\begin{equation*} \begin{aligned} &EX_n\,1(X_1\le\cdots\le X_{n-1}\le X_n) \\ &=E\int_0^1 dx\,1(X_1\le\cdots\le X_{n-1}\le X_n>x) \\ &=\int_0^1 dx\,P(X_1\le\cdots\le X_{n-1}\le X_n>x) \\ &=\int_0^1 dx\,[P(X_1\le\cdots\le X_{n-1}\le X_n) \\ &\qquad\qquad-P(X_1\le\cdots\le X_{n-1}\le X_n\le x)] \\ &=P(X_1\le\cdots\le X_{n-1}\le X_n) \\ &-\int_0^1 dx\,P(X_1\le\cdots\le X_{n-1}\le X_n\le x) \\ &=\frac1{n!}-\int_0^1 dx\,x^n\frac1{n!} = \frac1{n!}-\frac1{(n+1)!}. \end{aligned} \tag{4} \end{equation*} So, by (1), (2), (3), (4), \begin{equation*} \begin{aligned} EX_N&=\sum_{n=2}^\infty \Big(\frac12\,\frac1{(n-1)!}-\frac1{n!}+\frac1{(n+1)!}\Big) \\ &=\frac e2-1\approx0.359. \end{aligned} \end{equation*}


One may also note that \begin{equation*} \begin{aligned} &EN=E\sum_{n=0}^\infty1(N>n)=\sum_{n=0}^\infty P(N>n) \\ &=\sum_{n=0}^\infty P(X_1\le\cdots\le X_n) =\sum_{n=0}^\infty \frac1{n!}=e\approx2.72. \end{aligned} \end{equation*}


Simulation with Mathematica appears to confirm these results (click on the image below to enlarge it):

enter image description here