We are in Beta and we are offering 50% off! Use code BETATESTER at checkout.
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.

Monotonic draws

Statistics Hard

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



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.



Topics

Expectation
Similar questions

Provide feedback