1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Dec 10, 2023 at 15:49
  • $\begingroup$ Ah. My apologies; the mistake was mine. $\endgroup$
    – Glen_b
    Dec 10, 2023 at 17:14

1 Answer 1

1
$\begingroup$

Let $u_0=1$. First note that:

$$k|k<u\sim\text{Unif}(0,u)$$

Therefore $k|k<u_i$ and $u_{i+1}$ are identically distributed and $P(k<u_{i+1}|k<u_i)=1/2$.

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.