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

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 \]

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