You can access a significantly larger sample of the platform's content for free by logging in with your Gmail account. Sign in now to explore.

Assume we are drawing from a uniform distribution \(X\sim U(0,1)\). We keep drawing as long as the sequence we observe is monotonically increasing. What is the expected length of the sequence?

Let’s first simulate this process:

```
np.random.seed(1)
def sample():
tot = 1
prev = 0
for i in range(100):
r = np.random.random()
if r <= prev :
return tot-1
tot+=1
prev = r
print("Expected length of monotonic draws:",round(np.mean([sample() for _ in range(100000)]),3))
```

`## Expected length of monotonic draws: 1.72`

Note that **it is very common** to be asked to code it up in an interview setting. Sometimes the interview starts with coding and then moves to the math part, or vice versa.

**Indicator variables:** Assume that the random variable \(X_i\) is 1 if we have survived up to \(i\) draw. Then the expectation of \(X_i\) can be written as:

\[ E[X_i] = \sum X_i \Pr(X_i) = \Pr(X_i=1) = \frac{1}{k!} \]

In the above, we used the fact that \(X_i\) can either be 1 or zero, along with the observation that the probability of getting a monotonic sequence at time \(k\) is \(1/k!\).

The probability of having a monotonic sequence at time \(k\) is:

\[ \Pr(X_k=1) = \frac{1}{k!} \]

The length of the sequence can be expressed as the sum of these indicator variables:

\[ X = \sum_i X_i \]

and hence the expectation of \(X\) will be:

\[ E[X] = E \bigg[\sum_i X_i\bigg] = \sum_i E[X_i] = 1 + \frac{1}{2!} + ... = e-1 \]

To see how the Euler number

`e`

can be expressed as a series see here: https://en.wikipedia.org/wiki/List_of_representations_of_e

```
import math
r = 0
for i in range(1,100):
r += 1/math.factorial(i)
print(f"Expected length of monotonic draws: {r:.2f}")
```

`## Expected length of monotonic draws: 1.72`

**Analytical expression of expectation:** An alternative way to solve this problem is to actually express and estimate the expectation of the length \(E[X]\):

\[ \begin{align*} E[X] &= \sum X \Pr(X) = 1 + \Pr(X = 2) * 2 + \Pr(X=3) * 3 + ... \end{align*} \]

We can express the \(\Pr(X=k)\) as follows:

\[ P(X=k) = P(X \geq k) - P(X \geq k+1) = \frac{1}{k!} - \frac{1}{(k+1)!} = \frac{k}{(k+1)!} \]

and hence the expectation can be expressed as:

\[ E[X]= \sum_i P(X=i) i = \sum_i \frac{i^2}{(i+1)!} = e-1 \]

Here is the code:

```
import math
r = 0
for i in range(1,100):
r += (i**2)/math.factorial(i+1)
print(f"Expected length of monotonic draws: {r:.2f}")
```

`## Expected length of monotonic draws: 1.72`

This question has strong similarities with the question on *dynamic coin flips*.

Expectation

- Gambler’s ruin win probability Medium (Gambler ruin, Random walk, Expectation)
- Covariance of dependent variables Medium (Variance, Uniform, Covariance, Expectation)
- Number of draws to get greater than 1 Medium (Normal, Geometric, CDF, Expectation)
- Dynamic coin flips Hard (Expectation, Simulation)
- Expected number of consecutive heads Medium (Expectation)