Return to Question

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform $[0,1]$ distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ \Pr(\text{length} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2 $$ $$ \Pr(\text{length} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3 $$ $$ \Pr(\text{length} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $$ \Pr(\text{length} = n) $$

I know the final answer is structured $$ \mathbb E(\text{length of a monotonically increasing sequence}) = \sum_{n=1}^{\infty}n\Pr(\text{length} = n) $$

Any ideas on how to answer this question?

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform $[0,1]$ distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ \Pr(\text{length} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2 $$ $$ \Pr(\text{length} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3 $$ $$ \Pr(\text{length} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $\Pr(\text{length} = n)$. I know the final answer is structured $$ \mathbb E(\text{length}) = \sum_{n=1}^{\infty}n\Pr(\text{length} = n) $$

Any ideas on how to answer this question?

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform[0,1] distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ prob(length = 1) = \int_0^1 \int_0^{x_1} dx_2 dx_1 = 1/2 $$ $$ prob(length = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} dx_3 dx_2 dx_1 = 1/3 $$ $$ prob(length = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} dx_4 dx_3 dx_2 dx_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $$ prob(length = n) $$

I know the final answer is structured $$ E(length\ of\ a\ monotonically\ increasing\ sequence) = \sum_{n=1}^{\infty}n*prob(length = n) $$

Any ideas on how to answer this question?

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform $[0,1]$ distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ \Pr(\text{length} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2 $$ $$ \Pr(\text{length} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3 $$ $$ \Pr(\text{length} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $$ \Pr(\text{length} = n) $$

I know the final answer is structured $$ \mathbb E(\text{length of a monotonically increasing sequence}) = \sum_{n=1}^{\infty}n\Pr(\text{length} = n) $$

Any ideas on how to answer this question?

Suppose we are drawing from a uniform[0,1] distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ prob(length = 1) = \int_0^1 \int_0^{x_1} dx_2 dx_1 = 1/2 $$ $$ prob(length = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} dx_3 dx_2 dx_1 = 1/3 $$ $$ prob(length = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} dx_4 dx_3 dx_2 dx_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $$ prob(length = n) $$

I know the final answer is structured $$ E(length\ of\ a\ monotonically\ increasing\ sequence) = \sum_{n=1}^{\infty}n*prob(length = n) $$

Any ideas on how to answer this question?

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform[0,1] distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ prob(length = 1) = \int_0^1 \int_0^{x_1} dx_2 dx_1 = 1/2 $$ $$ prob(length = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} dx_3 dx_2 dx_1 = 1/3 $$ $$ prob(length = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} dx_4 dx_3 dx_2 dx_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $$ prob(length = n) $$

I know the final answer is structured $$ E(length\ of\ a\ monotonically\ increasing\ sequence) = \sum_{n=1}^{\infty}n*prob(length = n) $$

Any ideas on how to answer this question?