Is my implementation of the expected value correct? I conclude that the average number of iteration of this algorithm will be 1/3, but seems completely wrong. Rand() outputs either 0 or 1 (uniform) Algorithm: Call Rand() 5 times and translate the results as a binary number between 0 and 31. If this number is < 30 it is returned as the result, otherwise it is discarded and Rand() is called 5 more times.Repeat this process until a binary number between 0 and 29 is found. What is the expected running time of this algorithm in terms of iterations of calling Rand()?
My approach:
Random Variable X = number of iterations
Probability
P(X = 5) = 30/32
P(X = 10) = 2/32 * 30/32
P(X = 15) = 2/32 * 2/32 * 30/32
P(X = 5n) = (2/32)^n * 30/32
Expected Value $$ E[x] = x * p(x) = 5n * (2/32)^n * 30/32 $$
$$ 150/32*\sum\limits_{n=0}^\infty n (2/32)^n = 1/3 $$
The probability that you obtain a number that is either $30$ or $31$ will be $p = 2/32$, since each of the integers $\{0, \ldots, 31\}$ have an equal probability of occurring. Therefore, the random number $N$ of sets of 5 draws that are required until a number in $\{0, \ldots, 29\}$ is obtained is a geometric random variable, with probability mass function $$\Pr[N = k] = p^{k-1} (1-p), \quad k = 1, 2, \ldots.$$ The expected value of $N$ is $$\operatorname{E}[N] = \sum_{k=1}^\infty k \Pr[N = k] = \sum_{k=1}^\infty k p^{k-1} (1-p) = \frac{1}{1-p} = \frac{16}{15}.$$ The expected number of
Rand()calls is five times this number, or $16/3$.