Let $S$ be a set of $c$ elements sampled uniformly at random from the set $\{a_{1}, a_{2}, \cdots, a_{t}\}$, and $0 \leq \delta \leq 1$.
Let $X$ be a random variable that counts the number of elements in $S$ with rank strictly less than $\lfloor \delta t \rfloor$. Prove that $\delta c - \frac{2c}{t} \leq E[X] \leq \delta k$ in the case of both sampling without replacement and with replacement.
Here's my approach, suppose it's the case that sampling without replacement: Let $X_{i}= \begin{cases}1 &\text{if i-th element we picked has rank < $\lfloor \delta t \rfloor$}\\ 0 &\text{otherwise} \end{cases}$
Thus $X =\sum_{i=1}^{c} X_{i}$, then $E[X] = \sum_{i=1}^{c} E[X_{i}] = c P(X_{i}) = cP(ith \ element \ we \ pick\ has \ rank < \lfloor \delta t \rfloor) = c\frac{\delta t -1}{t} \leq \delta c$
I guess this part proves the upper bound of the expected value if I'm not mistaken?
However, I am wondering how to prove the lower bound of the expected value and the case of sampling with replacement?
Update: I think I might figure out the lower bound as well but welcome for having any thoughts/suggestions/advices or pointing out any mistakes.
Suppose now we're sampling with replacement, we will need to sample c times from the set $\{a_{1}, \cdots, a_{t}\}$. In each sample trial, the probability of picking element with rank $<\lfloor \delta t \rfloor$ is $\frac{\delta t -1}{t}$. so $E[X] = c\frac{\delta t -1}{t} =\frac{c\delta t -c}{t} \geq \frac{c\delta t -c-c}{t} = c\delta - \frac{2c}{t}$. This proves the lower bound.