This is from a sample exam in a algorithms class. We have the following premise
Say we have an array $A$ of length $2n$ which is initialised to 0, and we modify it by repeating a process which generates a uniformly random index, $i$, and sets $A[i] = 1$. We end this process when either a) We select any even index, or b) we have selected all odd indices.
The question arises as to what is the asymptotic upper bound for the expected number of selections we make given that the process ends due to:
Q1) condition b
Q2) condition a
and the probability that the termination happened due to: Q3) condition b
I am unsure on how exactly to answer Q1 and Q2
My approach for Q3 is as follows:
Basically combining over the n odd numbers, the probability that the next index is odd number is selected given that it wasn't selected before. Which is just :
$$\prod_{i=0}^{n-1} \frac{n - i}{2n - i} = \frac{n!}{\frac{2n!}{n!}} = \frac{(n!)^2}{2n!}$$ I am pretty sure this is correct
But I am not sure on how to extend this approach to Q1 and Q2. Any help or hints would be appreciated!!
$\mathsf{Q1}$: If the process ends after $X$ selections, it must be true that during the process all $n$ odd indices have been selected and none of the even indices has been selected. Additionally, the $X$th selection should be an odd index that has not been selected before. Denote as $X_i$ the # of selections used such that the $i$th new odd index is selected. We have $$ X = X_n\quad \text{and}\quad \mathsf{E}(X_1) = 1 $$ and $$ \mathsf{E}(X_i - X_{i-1}) = \sum_{k=1}^\infty \left\{k\cdot\left(\frac{i-1}{n}\right)^{k-1}\cdot\left(\frac{n - i + 1}{n}\right)\right\} = \frac{n}{n-i+1} $$ Therefore, $$ \mathsf{E}(X) = \mathsf{E}(X_n) = \mathsf{E}(X_1) + \sum_{i=2}^n \mathsf{E}(X_i - X_{i-1}) = \sum_{i=1}^n \frac{n}{n-i+1} $$ Note that $$ \mathsf{E}(X)=\sum_{i=1}^n \frac{n}{n-i+1} \leq n\sum_{i=1}^n\frac{1}{n-i+1} = O(n\log n) $$
$\mathsf{Q2}$: Suppose the process ends after $Y$ selections. Then the first $Y-1$ selections must all be odd indices and at most $n - 1$ distinct odd selections can be selected. In addition, the $Y$th selection is an even index. We have \begin{align} \mathsf{E}(Y) &= \sum_{i=1}^\infty \left\{i\cdot\Pr({\small\text{ first $i-1$ selections are all odd and at most $n-1$ distinct indices selected}})\cdot \frac{n}{2n}\right\}\\ &\leq \sum_{i=1}^\infty\left\{i\cdot\Pr({\small\text{ first $i-1$ selections are all odd}})\cdot \frac{n}{2n}\right\}\\ &= \sum_{i=1}^\infty \left\{i\cdot \left(\frac{n}{2n}\right)^{i-1}\cdot \frac{n}{2n}\right\} = \sum_{i=1}^\infty \left\{i\cdot \left(\frac{1}{2}\right)^i\right\} = 2 \end{align} Together with the fact that $Y \geq 1$, we obtain $$ \mathsf{E}(Y) = \Theta(1) $$