# Recursive Uniform Distribution Expectation Question

Suppose we draw some k ~ Unif(0, 1). Then, we will draw some $$u_1$$ ~ Unif(0, 1). If $$u_1 < k,$$ we stop. Else, we will draw $$u_2$$ ~ Unif(0, $$u_1$$). We will continue drawing until $$u_n < k,$$ where if we need to draw it, $$u_n$$ ~ Unif(0, $$u_{n-1}$$) What is the expected value for $$n$$? (i.e. how many draws until we get a value < k?)

I'm not sure how to calculate these like "infinite integrals"/infinite recursion, because we can see that like $$p_1=k, p_2=(1-k)*\frac{k}{u_1}, p_3=(1-k)*\frac{u_1-k}{u_1}*\frac{k}{u_2},$$ but I'm not sure how to think about the pattern/find a recursive pattern.

• Oh sorry, I wasn't super clear in the problem statement - the probability of drawing less than $k$ is constantly changing, because the distribution we pull from will change - I made an edit to the original question to make it clearer! Dec 10, 2023 at 15:49
• Ah. My apologies; the mistake was mine. Dec 10, 2023 at 17:14

Let $$u_0=1$$. First note that:

$$k|k

Therefore $$k|k and $$u_{i+1}$$ are identically distributed and $$P(k.

We conclude that $$n$$ follows a geometric distribution with parameter $$p=1/2$$.

This is easy to check with a quick simulation (in R):

m <- 1e7
k <- runif(m)
u <- runif(m)
p <- matrix(0L, 20, 2, 0, list(NULL, c("simulation", "dgeom")))

for (n in 1:20) {
i <- which(u >= k)
p[n, 1] <- length(k) - length(i)
u <- runif(i, 0, u[i])
k <- k[i]
}

p[,1] <- p[,1]/m
p[,2] <- dgeom(0:19, 0.5) # dgeom is 0-based
p
#>       simulation        dgeom
#>  [1,]  0.5003287 5.000000e-01
#>  [2,]  0.2499469 2.500000e-01
#>  [3,]  0.1247487 1.250000e-01
#>  [4,]  0.0624953 6.250000e-02
#>  [5,]  0.0312944 3.125000e-02
#>  [6,]  0.0155982 1.562500e-02
#>  [7,]  0.0077774 7.812500e-03
#>  [8,]  0.0038823 3.906250e-03
#>  [9,]  0.0019462 1.953125e-03
#> [10,]  0.0010004 9.765625e-04
#> [11,]  0.0004890 4.882812e-04
#> [12,]  0.0002456 2.441406e-04
#> [13,]  0.0001248 1.220703e-04
#> [14,]  0.0000615 6.103516e-05
#> [15,]  0.0000294 3.051758e-05
#> [16,]  0.0000164 1.525879e-05
#> [17,]  0.0000067 7.629395e-06
#> [18,]  0.0000042 3.814697e-06
#> [19,]  0.0000028 1.907349e-06
#> [20,]  0.0000006 9.536743e-07