Bounding the expected number of samples without replacement to select items with given non-uniform probability distributions We have a set $S$ of $n$ items $i_1, i_2, \ldots, i_n$ that we select and remove (i.e., without replacement) from $S$ in a sequential fashion. The probability to select each of them at the beginning of the process is known and respectively equal to $p_1, p_2, \ldots, p_n$, where for each $j\in\{1,2,\ldots, n\}$ there exists a positive integer $n_{j}$ such that $p_j=\frac{n_{j}}{2n}$ where $1\le n_{j} \le n$. Without loss of generality, assume $p_1\ge p_2\ge \ldots \ge p_n$. Let $S_t$ be the set of items at trial $t$, i.e., after having selected (and removed) $t-1$ items. The probability to select each item $i_j\in S_t$ at trial $t$ is equal to $\frac{p_j}{\sum_{k\in S_t} p_k}$.

Question(s): Let $K_j\in\{1,2,\ldots,n\}$ be the unique trial where $i_j$ is selected. Let $M_j\in\{1,2,\ldots,n\}$ be the first trial where $i_1, i_2,\ldots, i_j$ are all selected. Can we prove or disprove that there are two positive constants $\alpha$ and $\beta$ (independent of $n$ and the given probabilities $p_k$ for $1\le k\le n$) such that the following bounds hold?
$$\mathbb{E}[K_j],\mathbb{E}[M_j]\in\left[\frac{\alpha}{p_j},\frac{\beta}{p_j}\right]$$


Note: This question originated from a discussion (for a general version of this problem) in Probabilistic problem on sampling items without replacement with different probabilities and it is a more general version of Bounding the expected number of samples to select items with different probabilities and combinatorial constraints .
 A: We can do both, that is, we can show the result for $K_j$, which gives the lower bound for $M_j$. The upper bound for $M_j$ does not hold.
I use $[n]=\{1,\dots,n\}$ and assume that $S=[n]$ with probabilities $\sum_{i=1}^np_i=1$, but I don't fix an order on the $p_i$.
This doesn't change anything, it only simplifies the notation, which is really useful here. Also, I only need $p_i\ge\frac{1}{2n}$, the numerator doesn't have to be an integer, and we do not need $p_i\le\frac{1}{2}$.
Let $I_1,I_2,\dots$ be iid with $P(I_1=i)=p_i$ for $i\in[n]$ and let $X=(I_1,\dots,I_n)$, so for $X$ we draw with replacement.
Let $\mathcal D=\{x\in[n]^n:\{x_k:k\in[n]\}=[n]\}$ be the set of distinct outcomes.
Let $Y\in\mathcal D$ be given by $P(Y=y)=P(X=y|X\in\mathcal D)$ for $y\in\mathcal D$, i.e. $Y$ is $X$ conditional to all values being distinct.
Then $Y$ has exactly the required distribution, which means the following.
Let $t\in[n]$ and fix distinct values $(y_1,\dots,y_{t-1})\in[n]^{t-1}$, i.e. $|\{y_j:j\in[t-1]\}|=t-1$.
Let $S_t=[n]\setminus\{y_j:j\in[t-1]\}$ be the remaining values, and let $i\in S_t$.
Then we have $P(Y_t=i|Y_1=y_1,\dots,Y_{t-1}=y_{t-1})=\frac{p_i}{\sum_{j\in S_t}p_j}$.
So, $Y$ is chosen without replacement.
Now, for $i\in[n]$ let $K_i=\min\{t\in[n]:Y_t=i\}$ and further let $K'_i=\min\{t\in\mathbb Z_{>0}:I_t=i\}$. Notice that $K'_i\ge 1$ is geometric with parameter $p_i$ and hence $\mathbb E[K'_i]=\frac{1}{p_i}$. We show that $\mathbb E[K_i]\le\mathbb E[K'_i]=\frac{1}{p_i}$. This can be achieved using rejection sampling.
For this purpose let $I'_{t,s}$ for $t,s\in\mathbb Z_{>0}$ be iid with the same law as $I_1$. Then we recursively define $Y'_t$ and $S'_t$ by $S'_t=\min\{s\in\mathbb Z_{>0}:\forall t'\in[t-1]\,Y'_{t'}\neq I'_{t,s}\}$ and set $Y'_t=I'_{t,S'_t}$ for $t\in[n]$.
Intuitively, whenever we obtain a value that was already chosen, we reject it and repeat the experiment, until we obtain a new value, hence the name rejection sampling. With some additional effort (this is not all too easy, but a standard result), it can be seen that $Y'=(Y'_1,\dots,Y'_n)$ has the same distribution as $Y$, and $I'_{1,1},I'_{2,1}\dots$ has the same distribution as $I_1,I_2,\dots$ by definition. Now, let $\tilde K_i=\min\{t\in[n]:Y'_t=i\}$ and $\tilde K'_i=\min\{t\in\mathbb Z_{>0}:I'_{t,1}=i\}$ be the corresponding stopping times.
At time $t=\tilde K'_i$ we choose $i$ for the first time in $I'_{1,1},I'_{2,1},\dots$ and if we have not already chosen it before for $Y'$, meaning that $\tilde K_i<t=\tilde K'_i$, then by the definition (of $S'_t=1$) we will choose it now since $Y'_t=I'_{t,1}$ and thereby $\tilde K_i=t=\tilde K'_i$.
In a nutshell: Under the rejection sampling coupling we have $\tilde K_i\le\tilde K'_i$ and hence $\mathbb E[K_i]=\mathbb E[\tilde K_i]\le\mathbb E[\tilde K'_i]=\mathbb E[K'_i]=\frac{1}{p_i}$. Notice that we did not make any assumptions whatsoever, this holds always (in all questions so far), and gives the constant $\beta=1$.
As mentioned in the answer to one of the related questions, we have $M_i\ge K_i$ and hence $\mathbb E[M_i]\ge\mathbb E[K_i]$, so the lower bound for $\mathbb E[K_i]$ implies the lower bound for $\mathbb E[M_i]$. Now, we derive a different coupling using the following observation. Let $T=\{t\in[n]:t-1\le\frac{n}{2}\}$ be the steps where we have chosen at most half of the elements. For any $t\in T$ and any $S_t$ we have $|S_t|=n-(t-1)\ge\frac{n}{2}$ and $\sum_{i\in S_i}p_i\ge|S_i|\frac{1}{2n}\ge\frac{1}{4}$, i.e. we have so many elements left that they still have at least probability $\frac{1}{4}$. But this tells us that for any $i\in S_t$ and any previous choice $y=(y_1,\dots,y_{t-1})$ we have $P_i(y)=P(Y_t=i|Y_1=y_1,\dots,Y_{t-1}=y_{t-1})\le 4p_i$. Clearly, we also have $P_i(y)\le 1$, so $P_i(y)\le q_i$ with $q_i=\min(1,4p_i)$. Now, we consider iid Bernoulli variables $B_1,B_2,\dots$ with success probability $q_i$. Now, for any $t\in T$ and any past choices $y=(y_1,\dots,y_{t-1})$ we can couple $Y_t$ given $Y_1=y_1,\dots,Y_{t-1}=y_{t-1}$ and $B_t$ such that $Y_t=i$ whenever $B_t=1$ (with probability $P_i(y)$ we have $Y_t=i$ and $B_t=1$, with probability $q_i-P_i(y)$ we still have $B_t=1$ but $Y_t\neq i$, and with $1-q_i$ we have $B_t=0$ and $Y_t\neq i$). Now, let $B_0=1-\max\{B_t:t\in T\}$ and $K'_i=\min\{t\in T\cup\{0\}:B_t=1\}$.
Now, consider the step $t=K_i$, i.e. the first step with $Y_t=i$. If we have $t\in T$, then by the construction of our coupling we have $B_t=1$, which means that $K'_i\le t=K_i$. If we have $t\not\in T$, then we have $K'_i<t=K_i$ because $K'_i\in T\cup\{0\}$. This shows that $K'_i\le K_i$ and hence $\mathbb E[K'_i]\le\mathbb E[K_i]$. Now, let $K''_i$ be geometric with probability $q_i$, then $K'_i$ has the same law as $\unicode{120793}\{K'_i\in T\}K'_i$.
This gives $\mathbb E[K_i]\ge\mathbb E[\unicode{120793}\{K'_i\in T\}K'_i]=\sum_{t=0}^\infty P(\unicode{120793}\{K'_i\in T\}K'_i>t)$. Let $t_+=\max T=\max\mathbb Z_{\le\frac{n}{2}+1}$ and notice that $P(\unicode{120793}\{K'_i\in T\}K'_i\le t)=P(K'_i>t_+)+P(K'_i\le t)$. Now, recall that $P(K'_i>t)=\sum_{t'=t+1}^\infty(1-q_i)^{t'-1}q_i=q_i(1-q_i)^{t}\sum_{t'=0}^\infty(1-q_i)^{t'}=\frac{q_i(1-q_i)^t}{1-(1-q_i)}=(1-q_i)^t$, where we notice that this also holds for $q_i=1$. This gives
\begin{align*}
\mathbb E[K_i]
&\ge\sum_{t=0}^{t_+-1}(1-[(1-q_i)^{t_+}+1-(1-q_i)^t])=\sum_{t=0}^{t_+-1}(1-q_i)^t-t_+(1-q_i)^{t_+}\\
&=\frac{1-(1-q_i)^{t_+}}{1-(1-q_i)}-t_+(1-q_i)^{t_+}
=\left(1-(1-q_i)^{t_+}-q_it_+(1-q_i)^{t_+}\right)\frac{1}{q_i}
\end{align*}
We use $(1-q_i)^{t_+}=\exp(t_+\ln(1-q_i))\le e^{-t_+q_i}$ which also holds for $q_i=1$. We have $t_+\ge\frac{n}{2}+\frac{1}{2}>\frac{n}{2}$ and $q_i\ge\frac{2}{n}$, hence $t_+q_i>1$, thereby $(1-q_i)^{t_+}<e^{-1}$ and $q_it_+(1-q_i)^{t_+}\le q_it_+e^{-q_it_+}<e^{-1}$. Finally, notice that $\frac{1}{4}q_i\le p_i$ (since $\frac{1}{4}q_i=p_i$ for $p_i\le\frac{1}{4}$ and otherwise $\frac{1}{4}q_i\le\frac{1}{4}<p_i$) and thereby $\mathbb E[K_i]\ge\frac{\alpha}{p_i}$ with $\alpha=\frac{1}{4}(1-2e^{-1})$.
We establish the last claim, namely that no upper bound can exist for $M_i$.
For this purpose recall that $M_i\ge K_j$ for all $j\le i$ and hence $\mathbb E[M_i]\ge\mathbb E[K_j]\ge\frac{\alpha}{p_j}$. This shows that $\mathbb E[M_i]\ge\alpha\max_{j\le i}\frac{1}{p_j}$ (which is a significantly better lower bound!). But we can choose $p_i=\frac{2n-(n-1)}{2n}=\frac{n+1}{2n}=\frac{1}{2}+\frac{1}{2n}$ and $p_j=\frac{1}{2n}$ for $j\neq i$. Then we have $\mathbb E[M_i]\ge 2\alpha n$ by the above (for $i>1$), but $\frac{c}{p_i}\le 2c$ is bounded for all $c\in\mathbb R_{>0}$ (so this is smaller than $2\alpha n$ for sufficiently large $n$).
