$K$, and $M$. This completes the proof of inequality (\[eq:ru\]).

Proof of inequality (\[eq:lru\])
--------------------------------

Now we prove that $R^*\geq \frac{R_{\textup{u}}(N,K,r)}{2}$ holds for any $N\geq \frac{K(K+1)}{2}$. In this case, we can verify that inequality (\[eq:sml\]) holds for any $s\in\{1,...,K\}$, $\alpha=1$, and $\ell=1$. Consequently, from Theorem $\ref{th:general}$, $R^*$ can be bounded as follows: $$\begin{aligned}
            R^*&\geq s-1+1-\frac{s(s-1)+2s}{2(N-1+1)}M\nonumber\\
            &=s-\frac{s^2+s}{2}\cdot \frac{M}{N}.\label{eq:largeN}
            \end{aligned}$$ Then we prove $R^*\geq \frac{R_{\textup{u}}(N,K,r)}{2}$ by considering the following $2$ possible cases: If $\frac{KM}{N}\leq1$, we have $$\begin{aligned}
                    R_{\textup{u}}(N,K,r)=K-\frac{K^2+K}{2}\cdot \frac{M}{N}
                \end{aligned}$$ as defined in Definition \[def\]. Let $s=K$, we have the following bounds from (\[eq:largeN\]) which tightly characterizes $R_{\textup{u}}(N,K,r)$: $$R^*\geq K-\frac{K^2+K}{2}\cdot \frac{M}{N}=R_{\textup{u}}(N,K,r)\geq  \frac{R_{\textup{u}}(N,K,r)}{2}.\label{eq:46}$$ If $\frac{KM}{N}> 1$, let $s=\lfloor \frac{N}{M} \rfloor$, we have $\frac{M}{N}\in[\frac{1}{s+1},\frac{1}{s}]$. Consequently, we can derive the following lower bound on $R^*$: $$\begin{aligned}
                R^*&\geq s-\frac{s^2+s}{2}\cdot \frac{M}{N}\nonumber\\
                &=\frac{N-M}{2M}+ \frac{s^2+s}{2}\cdot\frac{N}{M}\cdot \left(\frac{M}{N}-\frac{1}{s+1}\right)\cdot\left(\frac{1}{s}-\frac{M}{N}\right)\nonumber\\
                &\geq \frac{N-M}{2M}.
                \end{aligned}$$ As mentioned earlier in this section, the following upper bound can be easily proved using the results of [@yu2016exact]: $$\begin{aligned}
                R_{\textup{u}}(N,K,r)&\leq \frac{N-M}{M} (1-(1-\frac{M}{N})^K).
                \end{aligned}$$ Consequently, we have $R_{\textup{u}}(N,K,r)\leq \frac{N-M}{M}\leq 2R^* $. To conclude, we have proved $R^*\geq \frac{R_{\textup{u}}(N,K,r)}{2}$ for both cases. Hence, inequality (\[eq:lru\]) holds for large $N$ for any possible values of $K$ and $M$.

Proof of Theorem \[th:general\] {#sec:gconv}
===============================

Before proving the converse bound stated in Theorem 