





\section{Introduction} \label{sec:intro}
The \gls{IoT} enables a variety of applications, such as autonomous driving, smart homes, and smart cities, by providing wireless access to a massive number of devices. A significant fraction of IoT devices is battery limited and transmits short packets in a sporadic and uncoordinated manner~\cite{Chen2020_massiveAccess,Wu2020_massiveAccess}. This calls for a new theoretical framework that helps to understand the fundamental limits on the energy efficiency achievable in massive uncoordinated access and provide guidelines for system design. 
To this end, Polyanskiy~\cite{PolyanskiyISIT2017massive_random_access} proposed a novel formulation for the multiple-access problem, commonly referred to as unsourced multiple access that relies on three key assumptions: i) all users employ a common codebook and the decoder only aims to return a list of messages; ii) the error event is defined per user
and the error probability is averaged over the users; iii) each user sends a fixed amount of information bits within a finite-length frame. This formulation provides a unified framework within which traditional as well as modern random access protocols \cite{Berioli2016NOW} give achievability results. In \cite{PolyanskiyISIT2017massive_random_access}, an upper bound on the minimum energy per bit achievable on the Gaussian \gls{MAC} was derived. Modern random access schemes exhibit a large gap to this bound, and devising coding schemes approaching the bound is an active area of research~\cite{Ordentlich2017low_complexity_random_access,Vem2019,Fengler2019sparcs,Amalladinne2020,Amalladinne2021,Pradhan2020,Han2021}. The framework proposed in~\cite{PolyanskiyISIT2017massive_random_access} has recently been extended to the quasi-static fading channel~\cite{Kowshik2020}, multiple-antenna channel~\cite{Fengler2019nonBayesian,Shyianov2021}, and a setup with common alarm messages~\cite{Stern2019}.

In the achievability bound in~\cite{PolyanskiyISIT2017massive_random_access} and in most of its extensions, the number of active users is assumed to be fixed and known to the receiver. In practice, however, since \gls{IoT} devices access the channel at random times and in a grant-free manner, the number of active users varies over time, and hence, it is typically unknown to the receiver. Therefore, the bound in \cite{PolyanskiyISIT2017massive_random_access} may provide an overoptimistic benchmark on the performance of random-access schemes operating in the practically relevant scenario in which the number of active users is not known to the receiver. In this scenario, the decoder needs to determine the size of the list of transmitted messages. Choosing a list size smaller than the number of active users will result in \glspl{MD}\textemdash i.e., transmitted messages that are not included in the decoded list\textemdash whereas choosing it larger than the number of active users will result in \glspl{FA}\textemdash i.e., decoded messages that were not transmitted. Furthermore, additional \glspl{MD} and \glspl{FA} may occur in the decoding process.
There is a trade-off between \gls{MD} and \gls{FA} probabilities: a decoder that always outputs the whole codebook will never misdetect, but has \gls{FA} probability close to one; similarly, a decoder that always outputs an empty set will never raise a \gls{FA} but will always misdetect.
Characterizing the \gls{MD}--\gls{FA} trade-off is a fundamental engineering challenge that was not addressed in \cite{PolyanskiyISIT2017massive_random_access}. An achievability bound for the Gaussian \gls{MAC} with unknown number of active users was presented in \cite{Effros2018ISIT}. However, the authors consider the joint-user error event instead of the per-user error event, and thus, \gls{MD} and \gls{FA} are not explicitly considered. To summarize, a random-coding bound accounting for both \gls{MD} and \gls{FA}, which can serve as a benchmark for unsourced multiple access with random user activity, is missing.



Most of the practical coding schemes that have been proposed so far for common-codebook massive random access require knowledge of the number of active users.
Modern variations of the ALOHA protocol, such as irregular repetition slotted ALOHA~(IRSA)~\cite{Liva2011IRSA},
can also operate when the number of active users is unknown. However, most of the results available for these schemes pertain to the packet loss rate, which accounts only for \gls{MD}. The successive interference cancellation coding scheme proposed in \cite{Vem2019} is also analyzed in terms of \gls{MD} only. Note that minimizing the \gls{MD} probability alone can entail a high \gls{FA} probability. In~\cite{Decurninge2020}, a tensor-based communication scheme was proposed, and both \gls{MD} and \gls{FA} probabilities were reported in the performance evaluation. Another scheme for which both \gls{MD} and \gls{FA} probabilities have been reported was recently proposed in~\cite{fengler2020pilot} for the quasi-static fading \gls{MAC} and for the case in which the receiver has a large number of antennas. However, in~\cite{Decurninge2020} and~\cite{fengler2020pilot}, the \gls{MD} and \gls{FA} probabilities are not reported separately but rather through their sum.


In this work, we extend Polyanskiy's bound to the case where the number of active users is {\em random} and {\em unknown}. Our contributions are summarized as follows. We first extend the definition of a random-access code provided in~\cite{PolyanskiyISIT2017massive_random_access} to account for both \gls{MD} and \gls{FA} probabilities. We then derive a random-coding achievability bound for the Gaussian \gls{MAC}. Unlike~\cite{PolyanskiyISIT2017massive_random_access}, we do not assume that the receiver knows the number of active users. To circumvent this issue, we let the decoder seek the best list size within a predetermined interval around an estimated value of the number of active users. Our decoding metric, which is based on nearest neighbor decoding, is similar to the one used in \cite{Stern2019}. However, different from \cite{Stern2019}, we limit the decoded list size to belong to a finite-size set to avoid noise overfitting, especially in the low energy-per-bit regime. We use our random-coding bound to characterize both \gls{MD} and \gls{FA} in slotted ALOHA with multi-packet reception (SA-MPR). Finally, we derive a random-coding bound for a scheme that simply treats interference as noise, referred to as \gls{TIN}, in which the number of active users is unknown.
		
To gain engineering insights on the role of the knowledge of the number of active users, we compare our bound with the bound in~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access}. We also use our bound to benchmark the energy efficiency of SA-MPR and \gls{TIN}, which do not require \emph{a priori} knowledge of the number of active users. Finally, we consider the scheme based on sparse regression codes (SPARCs) proposed in~\cite{Fengler2019sparcs} and its enhancement in~\cite{Amalladinne2021}, which were both derived for the case of known number of active users. We adapt these schemes to the case of unknown number of active users by performing an energy-based estimation of the number of active users and by letting the decoder treat the estimate as the true value.
Numerical results pertaining to a scenario with $\revise{300}$ active users in average show that to achieve both \gls{MD} and \gls{FA} probabilities below $10^{-1}$, the required energy per bit predicted by our achievability bound is only $0.65$~dB higher than that predicted by the bound for a known number of active users~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access}. For the same setting, the required energy per bit predicted by our bound is $9$~dB, $4.1$~dB, and $3.6$~dB lower than that of the SA-MPR bound, SPARC~\cite{Fengler2019sparcs}, and enhanced SPARC~\cite{Amalladinne2021}, respectively. 
The gap between the performance of enhanced SPARC with known number of active users and with unknown number of active users is small. This suggests that, for mild requirements on $P_{\rm MD}$ and $P_{\rm FA}$, it is sufficient to adapt existing coding schemes that perform well in the case of known number of active users by simply adding an active-user estimation step and then treating the estimated number of active users as the true value.
On the contrary, when we consider \gls{MD} probability and/or \gls{FA} probability below $10^{-3}$, the gap between our bound and the bound for a known number of active users in~\cite{PolyanskiyISIT2017massive_random_access} is much larger: around $3$--$4$~dB. For these stringent requirements, it turns out that it is energy inefficient to simply treat the estimated number of active users as the true value due to the errors that occur in the estimation step. 

To summarize, our results suggest that for the Gaussian MAC, the lack of knowledge of the number of active users entails a small loss in terms of energy efficiency if the target \gls{MD} and \gls{FA} probabilities are high, as typically considered in the literature. In this case, it is effective to first estimate the number of active users, then treat this estimate as the true value, and use a coding scheme that performs well for the case where the number of active users is known.
However, for more stringent targets, the loss due to the lack of knowledge of the number of active users can be large. In this case, the approach to simply using the estimate of the number of active users to set the decoded list size results in poor energy efficiency. This calls for more sophisticated methods to handle effectively the uncertainty about the number of active users.





The remainder of the paper is organized as follows. In Section~\ref{sec:channel}, we present the channel model and define a random-access code. In Section~\ref{sec:RCU}, we propose a random-coding bound for the Gaussian \gls{MAC}, apply it to SA-MPR, and derive a bound for \gls{TIN} as well.
 In Section~\ref{sec:numerical}, we present numerical results and discussions. Section~\ref{sec:conclusions} concludes the paper. The proofs are given in the appendices.

\subsubsection*{Notation}
Lowercase boldface letters denote vectors. Random quantities are denoted with non-italic letters with sans-serif font, e.g., a scalar $\vect{r}{x}$ and a vector $\rvVec{v}$.
Deterministic quantities are denoted
with italic letters, e.g., a scalar $x$ and a vector $\bm{v}$. The $n\times n$ identity matrix is denoted by $\mat{\mathrm{I}}_n$.
The Euclidean norm is denoted by $\|\cdot\|$.
Calligraphic uppercase letters, e.g., ${\mathcal A}$, denote sets. We use $\mathfrak{P}({\mathcal A})$ to denote the set of all subsets of ${\mathcal A}$;
$[m:n] \triangleq \{m,m+1,\dots,n\}$ if $m \le n$ and $[m:n] \triangleq \emptyset$ if $m>n$; $[n] \triangleq [1:n]$; $x^+ \triangleq \max\{x,0\}$; $\ind{\cdot}$ is the indicator function. The set of natural and complex numbers are denoted by $\mathbb{N}$ and $\mathbb{C}$, respectively. We denote the Gamma function by $\Gamma(x) \triangleq \int_{0}^{\infty}z^{x-1}e^{-z}dz$, and the lower and upper incomplete Gamma functions by $\gamma(x,y) \triangleq \int_{0}^{y}z^{x-1}e^{-z}dz$ and $\Gamma(x,y) \triangleq \int_{y}^{\infty}z^{x-1}e^{-z}dz$, respectively. Finally,
${\mathcal C}{\mathcal N}(\vect{\mu},\pmb{\Sigma})$ denotes the distribution of a complex proper
Gaussian random vector with mean $\vect{\mu}$ and covariance matrix~$\pmb{\Sigma}$, and ${\rm Pois}(\lambda)$ the Poisson distribution with mean $\lambda.\!$

\subsubsection*{Reproducible Research} 
The Matlab code used to evaluate our random-coding bound is available at: \url{https://github.com/khachoang1412/UMA_random_user_activity}.

\section{Random-Access Channel} \label{sec:channel}
We consider a \gls{MAC} in which a random number $\vect{r}{K}_{\rm a}$ of users transmit their messages to a receiver over $n$ uses of a stationary memoryless additive white Gaussian noise channel. Here, $\vect{r}{K}_{\rm a}$ follows a distribution with \gls{PMF} $P_{\vect{r}{K}_{\rm a}}$. Let $\rvVec{x}_i \in \mathbb{C}^n$ be the signal transmitted by user~$i$ over $n$ channel uses. The corresponding channel output is given by
\begin{align} \label{eq:gaussian_MAC}
	\rvVec{y} = \sum_{i=1}^{\vect{r}{K}_{\rm a}}\rvVec{x}_i + \rvVec{z}, 
\end{align}
where $\rvVec{z} \sim {\mathcal C}{\mathcal N}(\mathbf{0},\mat{\mathrm{I}}_n)$ is the Gaussian noise, which we assume being
independent of $\{\rvVec{x}_i\}_{i=1}^{\vect{r}{K}_{\rm a}}$.
We also assume that the transmitted signals satisfy the power constraint 
$
\|\rvVec{x}_i\|^2 \le nP, ~ \forall i \in [\vect{r}{K}_{\rm a}].
$
We further assume that the receiver does not know $\vect{r}{K}_{\rm a}$ \emph{a priori}, but can choose to estimate it.  
As in~\cite{PolyanskiyISIT2017massive_random_access}, our model differs from the classical \gls{MAC} in that the total number of users is not limited, all users employ the same codebook, and the receiver decodes up to a permutation of the messages.
However, as opposed to~\cite{PolyanskiyISIT2017massive_random_access}, where the number of active users is assumed to be fixed and known, we assume that $\vect{r}{K}_{\rm a}$ is random and unknown.
We therefore need to account for both \gls{MD} and \gls{FA} probabilities.
We next rigorously define these two quantities, as well as the notion of a random-access code.\footnote{Our definition of a random-access code can be extended straightforwardly to more general \glspl{MAC} with permutation-invariant channel law, as considered in~\cite[Def.~1]{PolyanskiyISIT2017massive_random_access}.}

\begin{definition}[Random-access code for the Gaussian \gls{MAC}] \label{def:code}
	Consider the $\vect{r}{K}_{\rm a}$-user Gaussian \gls{MAC} with $\vect{r}{K}_{\rm a} \sim P_{\vect{r}{K}_{\rm a}}$.
	An $(M,n,\epsilon_{\rm MD},\epsilon_{\rm FA})$ random-access code for this channel, where $M$ is the size of the codebook, $n$ is the codeword length, and $\epsilon_{\rm MD},\epsilon_{\rm FA} \in (0,1)$, consists of:
	\begin{itemize}[leftmargin=*]
		\item A random variable $\vect{r}{U}$ defined on a set ${\mathcal U}$
			that is revealed to both the transmitters and the receiver before the start of the transmission. 
		
		\item An encoding function $f\colon {\mathcal U} \times [M] \to \mathbb{C}^n$ that produces the transmitted codeword $\rvVec{x}_i = f(\vect{r}{U},\vect{r}{w}_i)$, satisfying the power constraint, of user $i$ for a given message $\vect{r}{w}_i$ uniformly distributed over~$[M]$.
		
		\item A decoding function $g\colon {\mathcal U} \times \mathbb{C}^n \to \mathfrak{P}([M])$ that provides an estimate $\widehat{{\mathcal W}} = \{\widehat{\vect{r}{w}}_1,\dots,\widehat{\vect{r}{w}}_{|\widehat{{\mathcal W}}|}\} = g(\vect{r}{U},\rvVec{y})$ of the list of transmitted messages.
	\end{itemize}
	Let $\widetilde{{\mathcal W}} = \{\widetilde{\vect{r}{w}}_1,\dots,\widetilde{\vect{r}{w}}_{|\widetilde{{\mathcal W}}|}\}$ denote the set of distinct elements of ${\mathcal W} = \{{\vect{r}{w}}_1,\dots,{\vect{r}{w}}_{\vect{r}{K}_{\rm a}}\}$. We assume that the decoding function satisfies the following constraints on the \gls{MD} and \gls{FA} probabilities:
		\begin{align}
			\!\!\!P_{\rm MD} &\triangleq \E\Bigg[{\ind{|\widetilde{{\mathcal W}}| \ne 0} \cdot \frac{1}{|\widetilde{{\mathcal W}}|} \sum_{i=1}^{|\widetilde{{\mathcal W}}|} \P[\widetilde{\vect{r}{w}}_i \!\notin\! \widehat{{\mathcal W}}]}\!\Bigg] \!\le \epsilon_{\rm MD} \label{eq:def_pMD}\\
			\!\!\!P_{\rm FA} &\triangleq \E\Bigg[{\ind{|\widehat{{\mathcal W}}| \ne 0} \cdot \frac{1}{|\widehat{{\mathcal W}}|} \sum_{i=1}^{|\widehat{{\mathcal W}}|} \P[\hat{\vect{r}{w}}_i \notin \widetilde{{\mathcal W}}]}\Bigg] \!\le \epsilon_{\rm FA}. \label{eq:def_pFA}
		
		\end{align}
		The expectations in~\eqref{eq:def_pMD} and~\eqref{eq:def_pFA} are with respect to the size of $\widetilde{{\mathcal W}}$ and $\widehat{{\mathcal W}}$, respectively. 
\end{definition} 	

\begin{remark}
	According to Definition~\ref{def:code}, the receiver aims to produce the list of \emph{distinct} transmitted messages\textemdash there are neither \gls{MD} nor \gls{FA} if $\widehat{{\mathcal W}} = \widetilde{{\mathcal W}}$. Therefore, as opposed to~\cite[Def.~1]{PolyanskiyISIT2017massive_random_access}, the event that two users transmit the same message does not result in an error if the message is included in the list of decoded messages.
\end{remark}

In the definition of random-access code proposed in~\cite[Def.~1]{PolyanskiyISIT2017massive_random_access}, the decoder outputs a list of messages of size equal to the number of active users, which is assumed to be known. In such a setup, a \gls{MD} implies a \gls{FA}, and vice versa. Hence, the two types of errors are indistinguishable. In our setup, the number of decoded messages $|\widehat{{\mathcal W}}|$ can be different from the number of distinct transmitted messages $|\widetilde{{\mathcal W}}|$. This motivates the definition of \gls{MD} and \gls{FA} probabilities provided in~\eqref{eq:def_pMD} and~\eqref{eq:def_pFA}, respectively.



\begin{remark} \label{remark:U}
	In the next section, we shall use a random-coding argument to obtain achievability bounds. Specifically, we will construct a codebook ensemble for which~\eqref{eq:def_pMD} and~\eqref{eq:def_pFA} holds in average. Unfortunately, this does not imply that there exists a single code in this ensemble that achieves both~\eqref{eq:def_pMD} and~\eqref{eq:def_pFA}. The introduction of the random variable $\vect{r}{U}$ in Definition~\ref{def:code} allows us to circumvent this issue by enabling randomized coding strategies.
	Specifically, proceeding as in~\cite[Th.~19]{Polyanskiy2011feedback}, one can show that there exists a randomized coding strategy that achieves both \eqref{eq:def_pMD} and~\eqref{eq:def_pFA} and involves time-sharing among at most three deterministic codes (i.e., $|{\mathcal U}| \le 3$) in this ensemble.
\end{remark}






\section{Random-Coding Bound} \label{sec:RCU}

\subsection{Proposed Random-Coding Bound for $\vect{r}{K}_{\rm a}$ Random and Unknown}
We first review the random-coding bound in~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access}, which holds for the case where $\vect{r}{K}_{\rm a}$ is fixed and known to the receiver.
Let ${\mathcal W} = \{\vect{r}{w}_1, \dots, \vect{r}{w}_{K_{\rm a}}\}$ be the set of transmitted messages. Each of the active users picks a codeword $\vect{c}_{\vect{r}{w}_i}$, $i\in [\vect{r}{K}_{\rm a}]$, from a common codebook containing $M$ codewords $\vect{c}_1,\dots,\vect{c}_M$ drawn independently from the distribution ${\mathcal C}{\mathcal N}(\mathbf{0},P'\mat{\mathrm{I}}_n)$ for a fixed $P' < P$.  To convey message $\vect{r}{w}_i$, the corresponding active user transmits $\vect{c}_{\vect{r}{w}_i}$ provided that $\|\vect{c}_{\vect{r}{w}_i}\|^2 \le nP$. Otherwise, it transmits the all-zero codeword. That is, $\rvVec{x}_i = \vect{c}_{\vect{r}{w}_i} \ind{\|\vect{c}_{\vect{r}{w}_i}\|^2 \le P}$.
The receiver employs a minimum distance decoder, in which the list of decoded messages is obtained as $\widehat{{\mathcal W}} = \arg\min_{{{\mathcal W}'} \subset [M], |{{\mathcal W}'}| = K_{\rm a}} \|c({{\mathcal W}'}) - \rvVec{y}\|^2$ where $c({\mathcal W}') \triangleq \sum_{i\in {\mathcal W}'} \vect{c}_{i}$. The error analysis involves manipulations of unions of the pairwise error events via a change of measure and the application of the Chernoff bound combined with Gallager's $\rho$-trick~\cite[p.~136]{Gallager1968information}. 
An alternative bound is also obtained by writing the pairwise error event as an inequality involving information densities, and by applying the tail bound on the information density given in~\cite[Cor.~17.1]{Polyanskiy2019lecture}.

In the following, we derive a random-coding bound for the case in which $\vect{r}{K}_{\rm a}$ is random and unknown to the receiver. Specifically, we consider a random-coding scheme with the same encoder as in \cite{PolyanskiyISIT2017massive_random_access}. However, since the receiver does not know $\vect{r}{K}_{\rm a}$, we let it estimate $\vect{r}{K}_{\rm a}$ from $\rvVec{y}$, and then decide the best list size within an interval around the initial estimate of $\vect{r}{K}_{\rm a}$. Specifically, given the channel output $\vect{y}$, the receiver estimates $\vect{r}{K}_{\rm a}$ as
\begin{align} \label{eq:est_Ka}
	K_{\rm a}' = \arg\max_{K \in [K_\ell:K_u]} m(\vect{y},K),
\end{align}
where $m(\vect{y},K)$ is a suitably chosen metric, and $K_\ell$ and $K_u$ are suitably chosen lower and upper limits on $K_{\rm a}'$, respectively. The parameters $K_\ell$ and $K_u$ can, for example, be chosen based on prior knowledge (if available) on the distribution of $\vect{r}{K}_{\rm a}$.
Then, given $K_{\rm a}'$, the receiver produces a list of decoded messages as
\begin{equation} \label{eq:decoder_Ka'}
	\widehat{{\mathcal W}} = \arg\min_{{{\mathcal W}}' \subset [M], \underline{K_{\rm a}'} \le |{{\mathcal W}}'| \le \overline{K_{\rm a}'}} \|c({{\mathcal W}}') - \rvVec{y}\|^2,
\end{equation}   
where $\underline{K_{\rm a}'} =\max\{K_\ell,K_{\rm a}'-r\}$ and $\overline{K_{\rm a}'}\triangleq \min\{K_u,K_{\rm a}'+r\}$, with $r$ being a nonnegative integer.
We refer to $r$ as the {\em decoding radius}.
An error analysis of this random-coding scheme conducted along similar lines as in \cite{PolyanskiyISIT2017massive_random_access} leads to the following result.

\begin{theorem}[Random-coding bound, $\vect{r}{K}_{\rm a}$ random and unknown]  \label{thm:RCU_unknownKa}
	Fix $P' < P$, $r$, $K_\ell$, and $K_{u}$ ($K_\ell \le K_{u}$). For the $\vect{r}{K}_{\rm a}$-user Gaussian \gls{MAC} with $\vect{r}{K}_{\rm a} \sim P_{\vect{r}{K}_{\rm a}}$, there exists an $(M,n,\epsilon_{\rm MD},\epsilon_{\rm FA})$ random-access code satisfying the power constraint $P$ for which
	\begin{align}
		\epsilon_{\rm MD} &= \sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} \Bigg(P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_{u}} \sum_{t\in {\mathcal T}}\frac{t+(K_{\rm a}-\overline{K_{\rm a}'})^+}{K_{\rm a}}
		\min\{p_t,q_t, \xi(K_{\rm a},K_{\rm a}')\} \Bigg) + \tilde{p}, \label{eq:eps_MD}\\
		\epsilon_{\rm FA} &= \sum_{K_{\rm a} =K_\ell}^{K_{u}} \Bigg(P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_{u}} \sum_{t\in {\mathcal T}} \sum_{t' \in {\mathcal T}_t} 
		\frac{t'+(\underline{K_{\rm a}'}-K_{\rm a})^+}{K_{\rm a} - t - {(K_{\rm a} - \overline{K_{\rm a}'})}^+ + t' + {(\underline{K_{\rm a}'}-K_{\rm a})}^+} \notag \\ 
		&\qquad \cdot \min\{p_{t,t'}, q_{t,t'}, \xi(K_{\rm a},K_{\rm a}')\} \Bigg) + \tilde{p}, \label{eq:eps_FA}
	\end{align}	
	where 
	\begin{align}
		\tilde{p} &= 2 - \sum_{K_{\rm a} = K_\ell}^{K_{u}}P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) - \E_{\vect{r}{K}_{\rm a}}\left[\frac{M!}{M^{\vect{r}{K}_{\rm a}}(M-\vect{r}{K}_{\rm a})!} \right]
		+ \E[\vect{r}{K}_{\rm a}]  \frac{\Gamma(n,nP/P')}{\Gamma(n)}, \label{eq:p0}\\
		p_t &= \sum_{t'\in \overline{{\mathcal T}}_t} p_{t,t'}, \label{eq:pt}\\
		p_{t,t'} &= e^{-n E(t,t')}, \label{eq:ptt} \\
		E(t,t') &= \max_{\rho,\rho_1 \in [0,1]} -\rho\rho_1 t' R_1 - \rho_1 R_2 + E_0(\rho,\rho_1), \label{eq:Ett} \\
		\!\!\!\! E_0(\rho,\rho_1) &= \max_{\lambda} \rho_1 a + \ln(1-\rho_1 P_2 b), \label{eq:E0}\\%E_0(\rho,\rho_1,\lambda), \\
	
		a &= \rho \ln(1+ P' t' \lambda) + \ln(1+ P't \mu), \label{eq:a}\\ 
		b &= \rho\lambda -\frac{\mu}{1+ P't\mu}, \label{eq:b} \\ 
		\mu &= \frac{\rho \lambda}{1+P't'\lambda}, \\
		P_2 &= 1+ \big((K_{\rm a} - \overline{K_{\rm a}'})^+ + (\underline{K_{\rm a}'} - K_{\rm a})^+\big)P', \label{eq:P2}\\
	
	
	
	
	
	
	
	
		R_1 &=  \frac{1}{nt'} \ln\binom{M - \max\{K_{\rm a},\underline{K_{\rm a}'}\}}{t'}, \label{eq:R1
		\\
		R_2 &=  \frac{1}{n} \ln \binom{\min\{K_{\rm a}, \overline{K_{\rm a}'}\}}{t}, \\
		q_t &= \inf_{\gamma} \bigg(\!\P[\vect{r}{I}_{t} \!\le\! \gamma] + \sum_{t'\in \overline{{\mathcal T}}_t}\!
		\exp(n(t'R_1 \!+\! R_2) \!-\! \gamma)\!\bigg), \label{eq:qt}\\
		q_{t,t'} &= \inf_{\gamma} \Big(\P[\vect{r}{I}_{t} \!\le\! \gamma] + \exp(n(t'R_1 \!+\! R_2) \!-\! \gamma)\Big), \label{eq:qtt} \\
		{\mathcal T} &= [0:\min\{\overline{K_{\rm a}'},K_{\rm a},M\!-\!\underline{K_{\rm a}'} \!-\! (K_{\rm a} \!-\! \overline{K_{\rm a}'})^+\}], \label{eq:T} \\
		{\mathcal T}_t &= \big[\big({(K_{\rm a} - \overline{K_{\rm a}'})}^+ - {(\underline{K_{\rm a}'} - K_{\rm a})}^+ + \max\{\underline{K_{\rm a}'},1\}
		- K_{\rm a} + t\big)^+ : u_t\big],	\label{eq:Tt}	\\
		\overline{{\mathcal T}}_t &= \big[\big({(K_{\rm a} \!-\! \overline{K_{\rm a}'})}^+ - {(K_{\rm a}\!-\!\underline{K_{\rm a}'})}^+ + t\big)^+ : u_t \big], \label{eq:Tbart} \\
		u_t &= \min\big\{{(\overline{K_{\rm a}'} \!-\! K_{\rm a})}^+ \!-\! {(\underline{K_{\rm a}'}\!-\!K_{\rm a})}^+ \!+\! t, 
		\overline{K_{\rm a}'} \!-\! {(\underline{K_{\rm a}'}\!-\!K_{\rm a})}^+, M\!-\!\max\{\underline{K_{\rm a}'},K_{\rm a}\}\big\}, \\
		\!\!\!\!\!\!\xi(K_{\rm a},K_{\rm a}') &= 
		\min_{K \in [K_\ell:K_u]\colon K \ne K_{\rm a}'} \P[m\left(\rvVec{y}_0,K_{\rm a}' \right) > m\left(\rvVec{y}_0,K\right)]. \label{eq:xi}
	\end{align}

	In~\eqref{eq:xi}, $\rvVec{y}_0 \sim {\mathcal C}{\mathcal N}(\mathbf{0},(1+K_{\rm a}P')\mat{\mathrm{I}}_n)$. The random variable $\vect{r}{I}_t$ in~\eqref{eq:qt} and \eqref{eq:qtt} is defined as
	\begin{equation} \label{eq:def_It}
		\vect{r}{I}_t \triangleq \!\!\min_{{\mathcal W}_{02} \subset [(K_{\rm a} - \overline{K_{\rm a}'})^+ + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t}\!\! \imath_t(c({\mathcal W}_{01}') + c({\mathcal W}_{02});\rvVec{y} \,\vert\, c([K_{\rm a}] \setminus {\mathcal W}_0)),
	\end{equation} 
	where ${\mathcal W}_{01}' = [K_{\rm a} \!+\! 1: \underline{K_{\rm a}'}]$, ${\mathcal W}_0 = [(K_{\rm a} \!-\! \overline{K_{\rm a}'})^+] \cup {\mathcal W}_{02}$,
	and the information density is defined as 
	\begin{align}
		\imath_t(c({\mathcal W}_{0});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0))
		&\triangleq n \ln(1+(t+(K_{\rm a}\!\!-\overline{K_{\rm a}'})^+)P') \notag \\	&\quad + \frac{\|\rvVec{y} - c({\mathcal W} \setminus {\mathcal W}_0)\|^2}{1+(t+(K_{\rm a}\!-\!\overline{K_{\rm a}'})^+)P'}
		- \|\rvVec{y} - c({\mathcal W}_0) - c({\mathcal W} \setminus {\mathcal W}_0)\|^2.  \label{eq:infor_den}
	\end{align}

\end{theorem}

\begin{proof}
	See Appendix~\ref{app:proof}.
\end{proof}

Some remarks are in order.
\begin{enumerate} [label={\roman*)}]
	\item
	In numerical evaluations of the bound provided in Theorem~\ref{thm:RCU_unknownKa}, it is often convenient to set $K_\ell$ to be the largest value and $K_{u}$ the smallest value for which $\sum_{K_{\rm a} = K_\ell}^{K_{u}}P_{\vect{r}{K}_{\rm a}}(K_{\rm a})$ exceeds a predetermined threshold.  
	
	\item The term $1 - \E_{\vect{r}{K}_{\rm a}}\left[\frac{M!}{M^{\vect{r}{K}_{\rm a}}(M-\vect{r}{K}_{\rm a})!} \right]$ in $\tilde{p}$ (see~\eqref{eq:p0}) can be upper-bounded by $\E_{\vect{r}{K}_{\rm a}}\big[\binom{\vect{r}{K}_{\rm a}}{2}/M\big]$ as in \cite{PolyanskiyISIT2017massive_random_access}. 
	
	\item The term $R_1$ in~\eqref{eq:R1} can be upper-bounded by $ \frac{1}{n} \ln (M - \max\{K_{\rm a},\underline{K_{\rm a}'}\}) - \frac{1}{nt'} \ln t'!$, which allows for a numerically stable computation when $M - \max\{K_{\rm a},\underline{K_{\rm a}'}\}$ is large.
	
	\item The optimal $\lambda$ in~\eqref{eq:E0} is given by the largest real root of the cubic function $c_1x^3 + c_2x^2 + c_3x + c_4$ with $c_1 =  -\rho \rho_1(\rho\rho_1 + 1)t'P'P_2P_3^2$, $c_2 = \rho\rho_1 t'P'P_3^2 - \rho\rho_1(3-\rho_1)t'P'P_2P_3 	-\rho\rho_1(\rho_1+1)P_2P_3^2$, $c_3 = (2\rho-1)\rho_1 t'P'P_3 + \rho_1 P_3^2 - 2\rho\rho_1 P_2P_3$, and $c_4 = (\rho-1)\rho_1 t'P' + \rho_1 P_3$, 
	where~$P_2$ is given by~\eqref{eq:P2} and $P_3 \triangleq (t' + \rho t)P'$.

	
\end{enumerate}

The quantity $\xi(K_{\rm a},K_{\rm a}')$, defined in~\eqref{eq:xi}, is an upper bound on the probability that the estimation~\eqref{eq:est_Ka} of $\vect{r}{K}_{\rm a}$ outputs $K_{\rm a}'$ given that $\vect{r}{K}_{\rm a} = K_{\rm a}$, under a new measure specified in Appendix~\ref{sec:change_measure}. In the following theorem, we provide closed-form expressions for $\xi(K_{\rm a},K_{\rm a}')$ for two different estimators of $\vect{r}{K}_{\rm a}$.

\begin{theorem}[Closed-form expressions for $\xi(K_{\rm a},K_{\rm a}')$] \label{thm:xi}
	For the \gls{ML} estimation of $\vect{r}{K}_{\rm a}$, i.e., $m(\vect{y},K) \!=\! \ln p_{\rvVec{y} | \vect{r}{K}_{\rm a}}(\vect{y} | K)$, $\xi(K_{\rm a},K_{\rm a}')$ is given by
	\begin{align} \label{eq:xi_ML}
		\xi(K_{\rm a},K_{\rm a}') &\triangleq \!\!\min_{K \in [K_\ell:K_u] \colon K \ne K_{\rm a}'} \!\bigg(\ind{K \!<\! K_{\rm a}'}\frac{\Gamma(n,\zeta(K,K_{\rm a},K_{\rm a}')}{\Gamma(n)}
		+ \ind{K \!>\! K_{\rm a}'}\frac{\gamma(n,\zeta(K,K_{\rm a},K_{\rm a}'))}{\Gamma(n)}\bigg),
	\end{align}
	with 
	\begin{align}
		\zeta(K,K_{\rm a},K_{\rm a}') &\triangleq n \ln\left(\frac{1+KP'}{1+K_{\rm a}'P'}\right)(1+K_{\rm a}P')^{-1}
		\left(\frac{1}{1+K_{\rm a}'P'}-\frac{1}{1+KP'}\right)^{-1}. \label{eq:zeta_ML}
	\end{align}
	
	For an energy-based estimation of $\vect{r}{K}_{\rm a}$, i.e., $m(\vect{y},K) = - |\|\vect{y}\|^2 - n(1 + KP')|$, $\xi(K_{\rm a},K_{\rm a}')$ is given by~\eqref{eq:xi_ML} with \begin{align}
		\zeta(K,K_{\rm a},K_{\rm a}') \triangleq \frac{n}{1+K_{\rm a}P'}\left(1+\frac{K + K_{\rm a}'}{2}P'\right). \label{eq:zeta_energy}
	\end{align}
	

\end{theorem}
\begin{proof}
	See Appendix~\ref{proof:xi}.
\end{proof}

	We next analyze  $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ given in~\eqref{eq:eps_MD} and~\eqref{eq:eps_FA}, respectively, in the asymptotic regime where $P\to \infty$. We first recall that the decoder~\eqref{eq:decoder_Ka'} outputs a list of at least $\underline{K_{\rm a}'}$ codewords and at most $\overline{K_{\rm a}'}$ codewords. If $\vect{r}{K}_{\rm a} \notin [\underline{K_{\rm a}'} : \overline{K_{\rm a}'}]$, a number of \glspl{MD} or \glspl{FA} cannot be avoided. Specifically, if $\overline{K_{\rm a}'} < \vect{r}{K}_{\rm a}$, the decoder commits $\vect{r}{K}_{\rm a} - \overline{K_{\rm a}'}$ {\em initial} \glspl{MD} due to the insufficient list size; if $\underline{K_{\rm a}'} > \vect{r}{K}_{\rm a}$ the decoder commits $\underline{K_{\rm a}'} - \vect{r}{K}_{\rm a}$ {\em initial} \glspl{FA} due to the excessive list size.
	As $P\!\to\! \infty$, by assuming that no additional \gls{MD} or \gls{FA} occurs on top of these initial \glspl{MD} or \glspl{FA}, we obtain lower bounds on $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ as follows. 
	
	\begin{theorem}[Asymptotic lower bounds on $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$] \label{thm:error_floor}
		With ML or energy-based estimation of $\vect{r}{K}_{\rm a}$,
		it holds that
		\begin{align}
			\lim_{P\to\infty} \epsilon_{\rm MD} \ge \bar{\epsilon}_{\rm MD} &= \sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} \bigg(P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_{u}} \frac{(K_{\rm a}-\overline{K_{\rm a}'})^+}{K_{\rm a}}
			{\xi}(K_{\rm a},K_{\rm a}') \bigg) + \bar{p}, \label{eq:eps_MD_floor}\\
			\lim_{P\to\infty} \epsilon_{\rm FA} \ge \bar{\epsilon}_{\rm FA} &= \!\sum_{K_{\rm a} =K_\ell}^{K_{u}} \!\bigg(\!P_{\vect{r}{K}_{\rm a}}(K_{\rm a})
			\sum_{K_{\rm a}' = K_\ell}^{K_{u}} \! \frac{(\underline{K_{\rm a}'}-K_{\rm a})^+}{K_{\rm a} \!-\! {(K_{\rm a} \!-\! \overline{K_{\rm a}'})}^+ \!+\! {(\underline{K_{\rm a}'}\!-\!K_{\rm a})}^+}
			{\xi}(K_{\rm a},K_{\rm a}') \bigg) + \bar{p}, \label{eq:eps_FA_floor}
		\end{align}	
		where $\bar{p} = 2 - \sum_{K_{\rm a} = K_\ell}^{K_{u}}P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) - \E_{\vect{r}{K}_{\rm a}}\left[\frac{M!}{M^{\vect{r}{K}_{\rm a}}(M-\vect{r}{K}_{\rm a})!} \right]$, and $\xi(K_{\rm a},K_{\rm a}')$ is given by~\eqref{eq:xi_ML} with
		$\zeta(K,K_{\rm a},K_{\rm a}') = n \ln\big(\frac{K}{K_{\rm a}'}\big) K_{\rm a}^{-1}\big(\frac{1}{K_{\rm a}'} - \frac{1}{K}\big)^{-1}$ for ML estimation of $\vect{r}{K}_{\rm a}$ and $\zeta(K,K_{\rm a},K_{\rm a}') = n\frac{K+K_{\rm a}'}{2 K_{\rm a}}$ for energy-based estimation of $\vect{r}{K}_{\rm a}$. 
	\end{theorem}
	\begin{proof}
		See Appendix~\ref{proof:error_floor}.
	\end{proof}
	\begin{remark} \label{remark:error_floor}
	The lower bounds in~\eqref{eq:eps_MD_floor} and~\eqref{eq:eps_FA_floor} are tight for typical IoT settings. Indeed, equalities in~\eqref{eq:eps_MD_floor} and~\eqref{eq:eps_FA_floor} hold if the probability of having additional \glspl{MD} and \glspl{FA} vanishes, i.e., $\min\{p_t,q_t\} \to 0$ for $t \ne 0$ and $\min\{p_{t,t'},p_{t,t'}\} \to 0$ for $(t,t') \ne (0,0)$ as $P\to\infty$. With $\rho = \rho_1 = 1$,
		the optimal $\lambda$ in~\eqref{eq:E0} is given by $\lambda \!=\! 1/(2P_2)$. Thus, by replacing the maximization over $\rho$ and $\rho_1$ in~\eqref{eq:Ett} with $\rho = \rho_1 = 1$, we obtain that $E(t,t') \ge -t' R_1 - R_2 + \ln\big(1+\frac{(t+t')P'}{4P_2}\big)$. It follows that 
		\begin{align}
			p_{t,t'} &\le \binom{M\!-\!\max\{K_{\rm a}, \underline{K_{\rm a}'}\}}{t'} \binom{\min\{K_{\rm a}, \overline{K_{\rm a}'}\}}{t} \left(1+\frac{(t+t')P'}{4P_2}\right)^{-n}.  \label{eq:bound_ptt}
		
		
		
		
		
		
		\end{align}
		If $K_{\rm a} \in  [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]$, i.e., $P_2 = 1$, the right-hand side of~\eqref{eq:bound_ptt} vanishes as $P' \to\infty$. Otherwise, the right-hand side of~\eqref{eq:bound_ptt} converges to 
		\begin{align}
			\bar{p}_{t,t'} &= \binom{M-\max\{K_{\rm a}, \underline{K_{\rm a}'}\}}{t'} \binom{\min\{K_{\rm a}, \overline{K_{\rm a}'}\}}{t} \bigg(1+\frac{t+t'}{4((K_{\rm a} - \overline{K_{\rm a}'})^+ + (\underline{K_{\rm a}'} - K_{\rm a})^+)}\bigg)^{-n} \\
			&\le M^{t'} K_{\rm a}^t \bigg(1+\frac{t+t'}{4((K_{\rm a} - \overline{K_{\rm a}'})^+ + (\underline{K_{\rm a}'} - K_{\rm a})^+)}\bigg)^{-n}.
		\end{align}
		Observe that $\bar{p}_{t,t'}$ is small if $n$ is relatively large compared to $\ln M$ and $\ln K_{\rm a}$, which is true for relevant values of $n,M$ and $K_{\rm a}$ in the IoT. Specifically, in typical IoT scenarios, $M$ and $K_{\rm a}$ are in the order of $10^2$, while $K_{\rm a}/n$ is from $10^{-4}$ to $10^{-3}$\textemdash see~\cite{PolyanskiyISIT2017massive_random_access} and \cite[Rem.~3]{Zadik2019}. For example, with $(M,n) = (2^{100}, 15000)$ and $K_{\rm a} \le 300$ as considered in~\cite{PolyanskiyISIT2017massive_random_access} and many follow-up works, assume that $(K_{\rm a} - \overline{K_{\rm a}'})^+ + (\underline{K_{\rm a}'} - K_{\rm a})^+ \le 20$, then $\bar{p}_{t,t'} < 10^{-128}$ for every $t\le 300$ and $t' \le 300$. 
		As a consequence, $p_{t,t'}$ and $p_t$ are very small. We conclude that $\lim\limits_{P\to\infty} \epsilon_{\rm MD}$ and $\lim\limits_{P\to\infty} \epsilon_{\rm FA}$ approach closely $\bar{\epsilon}_{\rm MD}$ and $\bar{\epsilon}_{\rm FA}$, respectively. In other words, $\bar{\epsilon}_{\rm MD}$ and $\bar{\epsilon}_{\rm FA}$ essentially characterize the error floors of ${\epsilon}_{\rm MD}$ and ${\epsilon}_{\rm FA}$, respectively, as $P\to \infty$. We shall further validate this argument through numerical experiments in Section~\ref{sec:numerical}. 
	\end{remark}
		
	The decoding radius $r$ can be optimized according to the target \gls{MD} and \gls{FA} probabilities. On the one hand, a large decoding radius results in a reduction of the initial \glspl{MD} and \glspl{FA}, and thus a reduction of the error floors. Indeed, it is easy to verify that both $\bar{\epsilon}_{\rm MD}$ in~\eqref{eq:eps_MD_floor} and $\bar{\epsilon}_{\rm FA}$ in~\eqref{eq:eps_FA_floor} decrease with $r$. As $r \to \infty$, both $\bar{\epsilon}_{\rm MD}$ and $\bar{\epsilon}_{\rm FA}$ vanish. On the other hand, a large decoding radius leads to \emph{overfitting}, especially when $P$ is small. Specifically, when the noise dominates the signal and the interference, increasing $r$ increases the chance that the decoder~\eqref{eq:decoder_Ka'} returns a list containing codewords whose sum is closer in Euclidean distance to the noise than to the sum of the transmitted codewords.
	When $P$ is sufficiently small, numerical experiments indicate that it is optimal to set $r = 0$.
	In this case, we obtain the following achievability bound.
	\begin{corollary}[Zero decoding radius]  \label{coro:zero_decRad}
	Fix $P' < P$, $K_\ell$, and $K_{u}$ ($K_\ell \le K_{u}$). There exists an $(M,n,\epsilon_{\rm MD},\epsilon_{\rm FA})$ random-access code satisfying the power constraint $P$ for which 
	\begin{align}
		\!\epsilon_{\rm MD} &= \!\!\sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} \bigg( P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_u} \sum_{t=0}^{\psi}\frac{t\!+\!(K_{\rm a}\!-\!K_{\rm a}')^+\!}{K_{\rm a}}
		\min\{p_{t,t},q_{t,t},\xi(K_{\rm a},K'_{\rm a})\} \bigg) + \tilde{p}, \label{eq:zeroRad_MD}\\
		\!\epsilon_{\rm FA} &= \!\sum_{K_{\rm a} =K_\ell}^{K_{u}} \bigg(P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = \max\{K_\ell,1\}}^{K_u} \sum_{t=0}^{\psi} \frac{t\!+\!(K_{\rm a}' \!-\! K_{\rm a})^+\!}{K_{\rm a}'}
		\min\{p_{t,t}, q_{t,t},\xi(K_{\rm a},K'_{\rm a})\}\bigg) + \tilde{p},  \label{eq:zeroRad_FA}
	\end{align}
	where $\psi \triangleq \min\{K_{\rm a}',K_{\rm a},M-\max\{K_{\rm a}',K_{\rm a}\}\}$, and $\tilde{p}$, $p_{t,t'}$, and  $q_{t,t'}$ are given by~\eqref{eq:p0}, \eqref{eq:ptt}, and \eqref{eq:qtt}, respectively, with $r = 0$.

\end{corollary}

	If the number of active users is fixed to $K_{\rm a}$, by letting $K_{\rm a}' = K_{\rm a}$, one obtains from Corollary~\ref{coro:zero_decRad} a trivial generalization of \cite[Th.~1]{PolyanskiyISIT2017massive_random_access} to the complex case. 


\begin{remark} \label{remark:est_then_dec}
	A practical approach to adapt the coding schemes proposed for the case of known $\vect{r}{K}_{\rm a}$ to the setting where $\vect{r}{K}_{\rm a}$ is unknown is to first estimate $\vect{r}{K}_{\rm a}$ and then treat this estimate as the true $\vect{r}{K}_{\rm a}$ in the decoding process. In this way, the number of decoded messages is equal to the estimate of $\vect{r}{K}_{\rm a}$.
	This corresponds to setting the decoding radius to zero in our random-coding bound, as characterized in~Corollary~\ref{coro:zero_decRad}.

\end{remark}


\subsection{Application to Slotted ALOHA With Multi-Packet Reception}
Our random-coding bound can also be applied to SA-MPR to investigate the resulting \gls{MD}--\gls{FA} trade-off. Consider an \revisee{SA-MPR} scheme where a length-$n$ frame is divided into $L$ slots, and where each user chooses randomly a slot in which to transmit. For $K_{\rm a}$ active users, the number of users transmitting in a slot follows a binomial distribution with parameters $(K_{\rm a},1/L)$.
The \gls{PMF} of the number of active users in a slot, $\vect{r}{K}_{\rm {SA}}$,  is given by
\begin{equation} \label{eq:PMF_Ka_perSlot}
P_{\vect{r}{K}_{\rm {SA}}}(K_{\rm SA}) \!=\! \sum_{K_{\rm a}} P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \binom{K_{\rm a}}{K_{\rm SA}} L^{-K_{\rm SA}}\left(1\!-\!\frac{1}{L}\right)^{\!K_{\rm a} - K_{\rm SA}}.
\end{equation}
Existing analyses of slotted ALOHA usually assume that the decoder can detect perfectly if no user, one user, or more than one user have transmitted in a slot. Furthermore, it is usually assumed that a collision-free slot leads to successful message decoding. However, the more the slots, the shorter the slot length over which a user transmits its signal, and, hence, the higher the impact of the additive noise.
To account for both detection and decoding errors, in Corollary~\ref{coro:slotted_ALOHA} below we apply the decoder introduced in~\eqref{eq:decoder_Ka'} in a slot-by-slot manner, and obtain a random-coding bound similar to Theorem~\ref{thm:RCU_unknownKa}.

\begin{corollary}[Random-coding bound for SA-MPR] \label{coro:slotted_ALOHA}
	For the Gaussian \gls{MAC} with the number of active users distributed according to $P_{\vect{r}{K}_{\rm a}}$ and frame length $n$, an SA-MPR scheme with $L$ slots can achieve the \gls{MD} and \gls{FA} probabilities given in~\eqref{eq:eps_MD} and \eqref{eq:eps_FA}, respectively, with codebook size $M$, codeword length $n/L$, power constraint $PL$, and per-slot number of active users distributed according to $P_{\vect{r}{K}_{\rm {SA}}}$ defined in~\eqref{eq:PMF_Ka_perSlot} (i.e., $P_{\vect{r}{K}_{\rm a}}$ is replaced by $P_{\vect{r}{K}_{\rm {SA}}}$ in \eqref{eq:eps_MD} and \eqref{eq:eps_FA}).
\end{corollary}

\subsection{Random-Coding Bound for a Scheme That Treats Interference as Noise} \label{sec:TIN}
We next present a random-coding union bound with parameter $s$ (RCUs) for \gls{TIN} to account for both \gls{MD} and \gls{FA} when the number of active users is unknown. This is an extension of the dependence testing (DT) bound for TIN with a known number of active users proposed in~\cite[Sec.~III]{PolyanskiyISIT2017massive_random_access}. We consider a random-coding scheme with the same encoder as in Theorem~\ref{thm:RCU_unknownKa} and a \gls{TIN} decoder. Specifically, the receiver first estimates the number of active users $\vect{r}{K}_{\rm a}$ using the metric $m(\vect{y},K)$, as in the decoder analyzed in Theorem~\ref{thm:RCU_unknownKa}.
Then, it outputs a list composed of the $K_{\rm a}^{\prime}$ codewords that are closest to the received signal $\rvVec{y}$ in Euclidean distance, i.e.,
\begin{equation}
	\widehat{\mathcal{W}} = \arg\min_{\mathcal{W}' = \{{w}'_1,\dots,{w}'_{K'_{\rm a}}\}\subset [M]} \sum_{i=1}^{K_{\rm a}^{\prime}} \| \rvVec{y} - {\vect{c}}_{{w}'_i} \|^2. \label{eq:NN_decoder}
\end{equation}
Operationally, the receiver decodes the message of each user by treating the signals of all other users as noise. 
An error analysis of this coding scheme gives the following result. 

\begin{theorem}[Random-coding bound for TIN] \label{thm:TIN}
	Fix $P' < P$ and nonnegative integers $K_\ell \le K_{u}$. For the $\vect{r}{K}_{\rm a}$-user Gaussian \gls{MAC} with $\vect{r}{K}_{\rm a} \sim P_{\vect{r}{K}_{\rm a}}$, there exists an $(M,n,\epsilon_{\rm MD},\epsilon_{\rm FA})$ random-access code satisfying the power constraint $P$ for which, for every $s>0$, 
	\begin{align
		\epsilon_{\rm MD} &\!=\!\!\! \sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \!\! \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}}
		\big( (K_{\rm a}\!-\!K_{\rm a}^{\prime})^+ \xi(K_{\rm a},K_{\rm a}')
		\!+\! \min\{K_{\rm a},K_{\rm a}^{\prime}\}\!\min\left\{\eta(s),\xi(K_{\rm a},K_{\rm a}')\right\}\!\big) \notag \\
		&\quad +
		\tilde{p},  \label{eq:md_TIN}\\
		\epsilon_{\rm FA} &= \sum_{K_{\rm a} =K_\ell}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}^{\prime}}
		\big((K_{\rm a}^{\prime}-K_{\rm a})^+\xi(K_{\rm a},K_{\rm a}')
		+ \min\{K_{\rm a},K_{\rm a}^{\prime}\} \min\left\{\eta(s),\xi(K_{\rm a},K_{\rm a}')\right\}\big) \notag \\
		&\quad+ \tilde{p}, \label{eq:fa_TIN}
	\end{align}
	where $\tilde{p}$ is given in~\eqref{eq:p0}, $\xi(K_{\rm a},K_{\rm a}')$ is given in~\eqref{eq:xi}, and
	\begin{align}
		\eta(s) = \P[\sum\limits_{i=1}^n  \imath_s(\vect{r}{x}_{i};\vect{r}{y}_i) \le \ln\left(\frac{M-K_{\rm a}}{\vect{r}{u}}\right)].
	 \label{eq:eta_s}
	\end{align}
	Here, $\vect{r}{u}$ is uniformly distributed on $[0,1]$ and $[\vect{r}{x}_1 \dots \vect{r}{x}_n]^{\scriptscriptstyle\mathsf{T}} \sim {\mathcal C}{\mathcal N}(\mathbf{0},\bar{P} \mat{\mathrm{I}}_n)$ with $\bar{P} = P'/(1+(K_{\rm a}-1)P')$. Furthermore, given $\vect{r}{x}_i = x_i$, we have that $\vect{r}{y}_i \sim {\mathcal C}{\mathcal N}(x_i,1)$. Finally, $\imath_s(\cdot;\cdot)$ is the generalized information density, given by
	\begin{align} \label{eq:gen_infor_den}
		\imath_s(x;y) \triangleq -s|y-x|^2 + \frac{s|y|^2}{1+s\bar{P}} + \ln(1+s\bar{P}).
	\end{align}
	
\end{theorem}
\begin{proof}
	See Appendix~\ref{app:TIN}.
\end{proof}

When $\vect{r}{K}_{\rm a}$ is fixed to $K_{\rm a}$ and $K'_{\rm a} = K_{\rm a}$, by setting $K_\ell = K_u = K_{\rm a}$ and $s = 1$, we obtain from Theorem~\ref{thm:TIN} that
$
\epsilon_{\rm MD} = \epsilon_{\rm FA} = \eta(1) + 1 - \frac{M!}{M^{{K}_{\rm a}}(M-{K}_{\rm a})!} + {K}_{\rm a}  \frac{\Gamma(n,nP/P')}{\Gamma(n)}.
$
This bound is similar to the one presented in \cite[Sec.~III]{PolyanskiyISIT2017massive_random_access}. 
To simplify the computation of $\eta(s)$, we can use the normal approximation given in \cite[Eq. (7)]{Ostman20}. Specifically, the term $\eta(s)$ can be expanded as $\eta(s) = Q\big(\frac{nI_s-\ln(M-K_{\rm a})}{\sqrt{nV_s}}\big) + O\big(\frac{1}{\sqrt{n}}\big)$
where $	I_s \triangleq \mathbb{E}\left[\imath_s(\vect{r}{x}_{i};\vect{r}{y}_i)\right]$, $V_s \triangleq \mathbb{E}\left[\vert \imath_s(\vect{r}{x}_{i};\vect{r}{y}_i) - I_s \rvert^2\right]$, and $Q(\cdot)$ is the Gaussian $Q$ function.
Note that, by choosing $s=1$, we obtain the normal approximation for the AWGN channel with Gaussian input, which is capacity achieving but not optimal from a dispersion perspective~\cite{Scarlett2017}.
It then follows that 
$\eta(1)= Q\big(\frac{nC-\ln(M-K_{\rm a})}{\sqrt{nV}}\big) + O\big(\frac{1}{\sqrt{n}}\big)$,
where $C \triangleq I_1 = \ln\big(1+\frac{P'}{1+(K_{\rm a}^{\prime}-1)P'}\big)$ and $V \triangleq V_1 = \frac{2 P'}{1+K_{\rm a}^{\prime}P'}$.



\section{Numerical Experiments} \label{sec:numerical}
We numerically evaluate the proposed random-coding bound and compare it with the random-coding bound in~\cite{PolyanskiyISIT2017massive_random_access} and with the performance of some unsourced multiple access schemes, namely, SA-MPR, TIN, and the schemes in~\cite{Fengler2019sparcs,Amalladinne2021}. We assume that $\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(\E[\vect{r}{K}_{\rm a}])$. Poisson processes are commonly used to model message arrivals in packet-data networks and result in accurate models in many realistic IoT scenarios~\cite{Metzger2019}. 
We assume an information payload per user of $k \triangleq \log_2 M = 128$ bits and consider a transmission duration of $n = 19200$ complex channel uses (i.e., $38400$ real degrees of freedom). As performance metric, we consider the average energy per bit $\EbNo \triangleq nP/k$ needed to operate at given target \gls{MD} and \gls{FA} probabilities. 


In Fig.~\ref{fig:EbN0_vs_EKa}, we compare the random-coding bound provided in Theorem~\ref{thm:RCU_unknownKa} with that in~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access} in terms of the required $\EbNo$ so that neither $P_{\rm MD}$ nor $P_{\rm FA}$ exceed $10^{-1}$. For our bound, we consider the \gls{ML} estimation of $\vect{r}{K}_{\rm a}$ and set the decoding radius $r = 0$, i.e., $\overline{K_{\rm a}'} = \underline{K_{\rm a}'} = K_{\rm a}'$. Numerical experiments indicate that this choice of decoding radius is optimal for the targeted MD and FA probabilities.\footnote{We discuss the trade-offs resulting from the choice of the decoding radius later on in this section.} We choose $K_\ell$ to be the largest value and $K_u$ the smallest value for which $\P[{\vect{r}{K}_{\rm a} \notin [K_\ell,K_u]}] < 10^{-9}$. Due to computational complexity, the terms $q_t$ and $q_{t,t'}$ are evaluated for $t = 1$ and $K_{\rm a} \le 50$ only. For the bound in \cite[Th.~1]{PolyanskiyISIT2017massive_random_access}, we average over the Poisson distribution of $\vect{r}{K}_{\rm a}$. This corresponds to the scenario in which $\vect{r}{K}_{\rm a}$ is random but known to the receiver.
As can be seen, similar to the bound in~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access}, our bound exhibits two behaviors as a function of the average number of active users: one where the required $\EbNo$ is almost constant and finite-blocklength effect dominates, and one where it grows with the average number of active users and multi-user interference dominates. 
To achieve $\max\{P_{\rm MD}, P_{\rm FA}\} \le 10^{-1}$, the extra required $\EbNo$ due to the lack of knowledge of $\vect{r}{K}_{\rm a}$ is about $0.5$--$0.7$~dB.
This small gap suggests that for the mild target $\max\{P_{\rm MD}, P_{\rm FA}\} \le 10^{-1}$, lack of knowledge of the number of active users entails a small penalty in terms of energy efficiency.

In Fig.~\ref{fig:EbN0_vs_EKa}, we also show the performance of the SA-MPR bound given in Corollary~\ref{coro:slotted_ALOHA} where we
optimize $L$ and the decoding radius for each $\E[\vect{r}{K}_{\rm a}]$. We further consider the possibility to encode~$\lfloor \log_2 L\rfloor$ extra bits for each user in the slot index, and assume perfect decoding of these bits. We refer to this scheme as SA-MPR with slot-index coding. Furthermore, we plot the RCUs bound on the performance of \gls{TIN} given in Theorem~\ref{thm:TIN} optimized over $s$, and its normal approximation evaluated with $s = 1$.
We also evaluate the performance of two state-of-the-art practical schemes, namely:
\begin{itemize} [leftmargin=*]

	
	\item the SPARC scheme proposed in~\cite{Fengler2019sparcs}, which employs a concatenated coding structure, consisting of an inner approximate message passing~(AMP) decoder followed by an outer tree decoder;
	
	\item an enhancement, proposed in~\cite{Amalladinne2021}, of the SPARC scheme in~\cite{Fengler2019sparcs}, where belief propagation between the inner AMP decoder and the outer tree decoder is introduced. 
\end{itemize}
Note that 
the SPARC and enhanced SPARC schemes were proposed for the Gaussian \gls{MAC} with {known} number of active users. To adapt these schemes to the case of unknown $\vect{r}{K}_{\rm a}$, we follow the approach discussed in Remark~\ref{remark:est_then_dec}: we first employ an energy-based estimation of $\vect{r}{K}_{\rm a}$, and then treat this estimate as the true $\vect{r}{K}_{\rm a}$ in the decoding process. As shown in Fig.~\ref{fig:EbN0_vs_EKa}, \gls{TIN} (light blue) and SA-MPR (pink), even with slot-index coding, become energy inefficient as $\E[\vect{r}{K}_{\rm a}]$ increases.
The enhanced SPARC scheme (orange) achieves the closest performance to our bound for $\E[\vect{r}{K}_{\rm a}] \ge 100$ and outperforms the original SPARC scheme by about $0.5$~dB for large $\E[\vect{r}{K}_{\rm a}]$. The performance of enhanced SPARC with known $\vect{r}{K}_{\rm a}$  is only slightly better than that with unknown $\vect{r}{K}_{\rm a}$. This suggests that, for the considered mild requirements on $P_{\rm MD}$ and $P_{\rm FA}$, it is effective to adapt existing coding schemes that perform well for known $\vect{r}{K}_{\rm a}$ by simply adding a $\vect{r}{K}_{\rm a}$-estimation step, and then treating the estimate of $\vect{r}{K}_{\rm a}$ as the true value.

\begin{figure}[t!]
	\centering
		\input{fig/EbN0_vs_EKa_1e1_1e1_journal.tex}
	\caption{The required $\EbNo$ to achieve $\max\{P_{\rm MD}, P_{\rm FA}\} \le 10^{-1}$ as a function of $\E[\vect{r}{K}_{\rm a}]$ for $k=128$ bits, $n = 19200$ channel uses, and $\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(\E[\vect{r}{K}_{\rm a}])$.
	
	
	
		Solid lines represent schemes/bounds with $\vect{r}{K}_{\rm a}$ unknown; dashed lines represent schemes/bounds with $\vect{r}{K}_{\rm a}$ known.}
	\label{fig:EbN0_vs_EKa}
\end{figure}

In Fig.~\ref{fig:Pe_vs_EbN0}, we plot the bounds on $P_{\rm MD}$ and $P_{\rm FA}$ in Theorem~\ref{thm:RCU_unknownKa} as a function of $\EbNo$ for $\E[\vect{r}{K}_{\rm a}] \in \{50,200\}$, and different decoding radius $r$. We also show the bound in~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access} for $\vect{r}{K}_a$ known.
The \gls{MD} and \gls{FA} probabilities drop at a certain $\EbNo$, and then saturate to error floors. The existence of a waterfall region and an error-floor region is more evident in the case $\E[\vect{r}{K}_{\rm a}] = 200$. The error floors are due to the initial \glspl{MD} and \glspl{FA}, and are characterized by $\bar{\epsilon}_{\rm MD}$ and $\bar{\epsilon}_{\rm FA}$ in Theorem~\ref{thm:error_floor}. We observe that setting $r =0$  leads to $\epsilon_{\rm MD} = \epsilon_{\rm FA}$ and  turns out optimal in the low $\EbNo$ regime, where noise overfitting is the  bottleneck. This is in agreement with the results reported in Fig.~\ref{fig:EbN0_vs_EKa}. An increase of the decoding radius results in a performance improvement in the moderate and high $\EbNo$ regime, where setting $r =0$ yields high error floors. Our numerical results indicate that zero decoding radius should be used when the target \gls{MD} and \gls{FA} probabilities are higher than about $2\times 10^{-2}$; otherwise, the decoding radius needs to be increased. Remarkably, as illustrated in Fig.~\ref{fig:Pe_vs_EbN0}, there is a sharp difference between the case $r = 0$ and the case $r > 0$ in terms of the $\EbNo$ value at which the waterfall region starts. Moreover, this $\EbNo$ value appears to coincide for all positive  $r$.\footnote{Characterizing analytically this $\EbNo$ value is challenging since $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ are given in terms of sums in which each addend involves the optimization of the three intermediate parameters $(\lambda, \rho, \rho_1)$.}



\begin{figure}[t!]
	\centering
	\subfigure[$\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(50)$]{\input{fig/Pe_vs_EbN0_journal_k128_EKa50.tex}}
	\subfigure[$\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(200)$]{\input{fig/Pe_vs_EbN0_journal_k128_EKa200.tex}}
	\caption{The bounds~\eqref{eq:eps_MD} and~\eqref{eq:eps_FA} on the \gls{MD} and \gls{FA} probabilities as functions of $\EbNo$ for $k=128$ bits, $n = 19200$ channel uses, and some values of $r$, as well as their large-$P$ limits given in~\eqref{eq:eps_MD_floor} and~\eqref{eq:eps_FA_floor}.
	
	}
	\label{fig:Pe_vs_EbN0}
\end{figure}

When asymmetric requirements on $P_{\rm MD}$ and $P_{\rm FA}$ are considered, one can adjust the decoding interval $[\underline{K_{\rm a}'}: \overline{K_{\rm a}'}]$ in~\eqref{eq:decoder_Ka'} to achieve different \gls{MD}-\gls{FA} trade-offs. Specifically, one can set $\underline{K_{\rm a}'} =\max\{K_\ell,K_{\rm a}'-r_\ell\}$ and $\overline{K_{\rm a}'}\triangleq \min\{K_u,K_{\rm a}'+r_u\}$ where $(r_\ell,r_u)$ is a pair of lower and upper decoding radii. The random-coding bound in Theorem~\ref{thm:RCU_unknownKa} can be extended accordingly. In Fig.~\ref{fig:EbN0_vs_EKa_2}, we consider this extension and show the required $\EbNo$ to achieve more stringent requirements on $P_{\rm MD}$ and $P_{\rm FA}$, namely, $\{P_{\rm MD} \le 10^{-1}, P_{\rm FA} \le 10^{-3}\}$, $\{P_{\rm MD} \le  10^{-3}, P_{\rm FA} \le 10^{-1}\}$, and $\max\{P_{\rm MD}, P_{\rm FA}\} \le  10^{-3}$. We increase $r_\ell$ and $r_u$ such that the error floors lie below these target \gls{MD} and \gls{FA} probabilities, and no significant reduction in $\EbNo$ can be achieved by increasing $r_\ell$ and $r_u$ further. For example, for $\{P_{\rm MD} \le 10^{-1}, P_{\rm FA} \le 10^{-3}\}$, $\{P_{\rm MD} \le  10^{-3}, P_{\rm FA} \le 10^{-1}\}$, and $\max\{P_{\rm MD}, P_{\rm FA}\} \le  10^{-3}$, we respectively set $(r_\ell,r_u) = (3,0)$, $(0,3)$, and $(3,3)$ for $\E[\vect{r}{K}_{\rm a}] = 50$, and $(r_\ell,r_u) = (6,1)$, $(1,6)$, and $(6,6)$ for $\E[\vect{r}{K}_{\rm a}] = 200$. We observe that the required $\EbNo$ is almost the same for the two requirements with $P_{\rm FA} \le 10^{-3}$, and it is slightly lower for the requirement with $P_{\rm FA} \le 10^{-1}$. We also plot the bound for $\vect{r}{K}_{\rm a}$ known~\cite[Th.~1]{PolyanskiyISIT2017massive_random_access}. In contrast to the scenario in Fig.~\ref{fig:EbN0_vs_EKa}, where the gap between our bound and the bound for $\vect{r}{K}_{\rm a}$ known was small, the gap is now significantly larger. Specifically, our bound suggests that one needs additional $3$--$4$~dB in $\EbNo$ when $P_{\rm MD}$ and/or $P_{\rm FA}$ are required to be lower than $10^{-3}$. This gap tends to be smaller as $\E[\vect{r}{K}_{\rm a}]$ increases. The slope of the curves for the bound in Theorem~\ref{thm:RCU_unknownKa} suggests that the dominating factor for $\E[\vect{r}{K}_{\rm a}] \le 300$ is still the finite-blocklength effect, and the multi-user interference will kick in for higher $\E[\vect{r}{K}_{\rm a}]$.

In Fig.~\ref{fig:EbN0_vs_EKa_2}, we also show the required $\EbNo$ for the enhanced SPARC scheme with $\vect{r}{K}_{\rm a}$ known/unknown. We further plot a lower bound on this $\EbNo$ value resulting from counting the \glspl{MD} and \glspl{FA} that occur in the estimation step only, while assuming that no additional \gls{MD} or \gls{FA} occurs in the decoding step. Recall that we adapt the enhanced SPARC scheme to the case of unknown $\vect{r}{K}_{\rm a}$ by simply treating the estimate of $\vect{r}{K}_{\rm a}$ as the true $\vect{r}{K}_{\rm a}$. The performance of the enhanced SPARC scheme with $\vect{r}{K}_{\rm a}$ unknown is very close to the lower bound and drastically worse than enhanced SPARC with $\vect{r}{K}_{\rm a}$ known. This confirms that the estimation step is indeed the bottleneck. 
Furthermore, the lower bound for enhanced SPARC exhibits a large gap to the achievability bound in Theorem~\ref{thm:RCU_unknownKa}. For example, the gap is about $7$~dB for only $25$ active users in average. This large gap suggests that this approach, which simply uses the estimate of $\vect{r}{K}_{\rm a}$ to set the decoded list size and relies on existing coding schemes proposed for $\vect{r}{K}_{\rm a}$ known, becomes energy inefficient for stringent requirements on $P_{\rm MD}$ and/or $P_{\rm FA}$. This calls for more sophisticated methods to overcome the bottleneck of estimating $\vect{r}{K}_{\rm a}$ and handle effectively the uncertainty about the number of active users.
\begin{figure}[t!]
	\centering
	\input{fig/EbN0_vs_EKa_otherReq_journal.tex}
	\caption{The required $\EbNo$ to achieve $\{P_{\rm MD} \le 10^{-1}, P_{\rm FA} \le  10^{-3}\}$, $\{P_{\rm MD} \le  10^{-3}, P_{\rm FA} \le 10^{-1}\}$, or $\max\{P_{\rm MD}, P_{\rm FA}\} \le  10^{-3}$
		as a function of $\E[\vect{r}{K}_{\rm a}]$ for $k=128$ bits, $n = 19200$ channel uses, and $\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(\E[\vect{r}{K}_{\rm a}])$.
	
	
	
	
	}
	\label{fig:EbN0_vs_EKa_2}
\end{figure}

In Fig.~\ref{fig:Pe_vs_EbN0_2}, we plot the bounds $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ in Theorem~\ref{thm:RCU_unknownKa} as a function of $\EbNo$ for $\E[\vect{r}{K}_{\rm a}] \in \{50,200\}$ for the decoding radii considered in Fig.~\ref{fig:EbN0_vs_EKa_2}. Solid lines represent $\epsilon_{\rm MD}$, while dashed lines represent $\epsilon_{\rm FA}$. We observe again that the waterfall region of either $\epsilon_{\rm MD}$ or $\epsilon_{\rm FA}$ starts at a similar $\EbNo$ value for various values of $(r_\ell,r_u)$ different from $(0,0)$. The $\EbNo$ value that satisfies the requirements on both $P_{\rm MD}$ and $P_{\rm FA}$ is dictated by the $\EbNo$ value that satisfy the requirement on $P_{\rm FA}$. This explains why the $\EbNo$ values according to Theorem~\ref{thm:RCU_unknownKa}, shown in Fig.~\ref{fig:EbN0_vs_EKa_2}, is similar for the two requirements with $P_{\rm FA} \le 10^{-3}$.
\begin{figure}[t!]
	\centering
	\subfigure[$\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(50)$]{\input{fig/Pe_vs_EbN0_journal_k128_EKa50_2.tex}}
	\subfigure[$\vect{r}{K}_{\rm a} \sim \mathrm{Pois}(200)$]{\input{fig/Pe_vs_EbN0_journal_k128_EKa200_2.tex}}
	\caption{The bounds on the \gls{MD} and \gls{FA} probabilities as a function of $\EbNo$ for $k=128$ bits and $n = 19200$ channel uses with $r_\ell$ and $r_u$ selected corresponding to Fig.~\ref{fig:EbN0_vs_EKa_2}.
		 Solid lines represent $\epsilon_{\rm MD}$; dashed lines represent $\epsilon_{\rm FA}$.
	
	}
	\label{fig:Pe_vs_EbN0_2}
\end{figure}






\section{Conclusions} \label{sec:conclusions}
To account for the random user activity in the \gls{IoT}, we proposed a formulation for unsourced multiple access where both the identity and the number of active users are unknown. We derived a random-coding bound for the Gaussian MAC that reveals a trade-off between misdetection and false alarm. Our bound \revisee{provides an estimate of} the penalty in terms of energy efficiency due to the lack of knowledge of the number of active users, and serves as a benchmark to assess the performance of practical schemes. Numerical results show that for the Gaussian MAC, if the target misdetection and false-alarm probabilities are sufficiently high, e.g., $10^{-1}$, the lack of knowledge of the number of active users entails a small loss. In this case, it is effective to adapt a coding scheme that performs well for the case of known number of active users, by first estimating the number of active users and then treating this estimate as the true value in the decoding process. However, for stringent target misdetection and false-alarm probabilities, e.g., $10^{-3}$, numerical results indicate that the loss due to the lack of knowledge of the number of active users is significant. In this case, adapting existing coding schemes proposed for known number of active users by simply treating the estimate of the number of active users as perfect is energy inefficient even for a small number of active users. Therefore, more sophisticated methods are needed to handle effectively the uncertainty about the number of active users. 




\appendices
\section{Proof of Theorem~\ref{thm:RCU_unknownKa}} \label{app:proof}
The following well-known results will be used in the proof.

\begin{lemma}[{Change of measure~\cite[Lemma~4]{Ohnishi2021}}] \label{lem:change_measure}
	Let $p$ and $q$ be two probability measures. Consider a random variable $\vect{r}{x}$ supported on ${\mathcal H}$ and a function $f \colon {\mathcal H} \to [0,1]$. It holds that 
	\begin{align}
		\E_p[f(\vect{r}{x})] \le \E_q[f(\vect{r}{x})] + d_{\rm TV}(p,q)
	\end{align}
	where $d_{\rm TV}(p,q)$ denotes the total variation distance between $p$ and $q$.





\end{lemma}


\begin{lemma}[{Chernoff bound~\cite[Th. 6.2.7]{DeGroot2012ProbStats}}] \label{lem:Chernoff}
	For a random variable $\vect{r}{x}$ with moment-generating function $\E[e^{t \vect{r}{x}}]$ defined for all $|t| \le b$, it holds for all $\lambda \in [0,b]$ that
	\begin{align}
		\P[\vect{r}{x} \le x] \le e^{\lambda x} \E[e^{-\lambda \vect{r}{x}}].
	\end{align}
\end{lemma}

\begin{lemma} [{Gallager's $\rho$-trick~\cite[p.~136]{Gallager1968information}}] \label{lem:Gallager}
	It holds that $\P[\cup_i A_i] \le (\sum_{i} \P[A_i])^\rho$ for every $\rho \in [0,1]$.
\end{lemma}
\begin{lemma} \label{lem:chi2}
	Let $\rvVec{x} \sim {\mathcal C}{\mathcal N}(\vect{\mu},\sigma^2\mat{\mathrm{I}}_n)$. It holds that 
	\begin{align}
		\E[e^{-\gamma \|\rvVec{x}\|^2}] = (1\!+\!\gamma\sigma^2)^{-n} \exp\bigg(\!-\frac{\gamma\|\vect{\mu}\|^2}{1+\gamma\sigma^2}\bigg), \quad \forall \gamma \!>\! -\frac{1}{\sigma^2}. \label{eq:tmp363}
	\end{align} 
\end{lemma}

We present next an error analysis of the random-coding scheme introduced in Section~\ref{sec:RCU}.
Denote by ${\mathcal W}_0$ the set of misdetected messages, i.e., ${\mathcal W}_0 \triangleq \widetilde{{\mathcal W}} \setminus \widehat{{\mathcal W}}$, and by ${\mathcal W}_0'$ the set of falsely alarmed messages, i.e., ${\mathcal W}_0' \triangleq \widehat{{\mathcal W}} \setminus \widetilde{{\mathcal W}}$. The \gls{MD} and \gls{FA} probabilities, defined respectively in~\eqref{eq:eps_MD} and \eqref{eq:eps_FA}, can be expressed as the average fraction of misdetected and falsely alarmed messages as 
\begin{align}
	P_{\rm MD} &= \E[\ind{|\widetilde{{\mathcal W}}| \ne 0} \cdot \md], \label{eq:pMD}\\
	P_{\rm FA} &= \E[\ind{|\widehat{{\mathcal W}}| \ne 0} \cdot \fa]. \label{eq:pFA}
\end{align}


\subsection{Change of Measure} \label{sec:change_measure}
 Since $\ind{|\widetilde{{\mathcal W}}| \ne 0} \cdot \md$ and $\ind{|\widehat{{\mathcal W}}| \ne 0} \cdot \fa$ are nonnegative random variables that are upper-bounded by one, we can apply Lemma~\ref{lem:change_measure}. Specifically, we replace the measure over which the expectation is taken by the one under which: 
i) there are at least $K_\ell$ and at most $K_{u} \ge \overline{K_{\rm a}'}$ active users, i.e., $K_\ell\le\vect{r}{K}_{\rm a} \le K_{u}$; ii) the active users transmit distinct messages, i.e., $|\widetilde{{\mathcal W}}| = \vect{r}{K}_{\rm a}$ and $\widetilde{\vect{r}{w}}_1,\dots,\widetilde{\vect{r}{w}}_{\vect{r}{K}_{\rm a}}$ are sampled uniformly without replacement from $[M]$;  iii) $\rvVec{x}_i = \vect{c}_{\vect{r}{w}_i}, \forall i$, instead of $\rvVec{x}_i = \vect{c}_{\vect{r}{w}_i} \ind{\|\vect{c}_{\vect{r}{w}_i}\|^2 \le nP}$. 
It then follows from \cite[Eq. (41)]{Kowshik2020fundamental} that the total variation between the original measure and the new one is
upper-bounded by $\P[{\vect{r}{K}_{\rm a} \notin [K_\ell:K_u]}] + \P[ |\widetilde{{\mathcal W}}| < \vect{r}{K}_{\rm a}] + \P[\overline{U}]$, where
$U \triangleq \{\|\vect{c}_{\vect{r}{w}_i}\|^2 \le nP, \forall i \in [\vect{r}{K}_{\rm a}] \}$ and $\overline{U}$ denotes the complement of~$U$.
We compute these probabilities
as follows:
\begin{itemize}[leftmargin=*]
	\item To compute the first probability, we simply use that $\P[{\vect{r}{K}_{\rm a} \notin [K_\ell:K_u]}] = 1 - \sum_{K_{\rm a} = K_\ell}^{K_{u}}P_{\vect{r}{K}_{\rm a}}(K_{\rm a})$.
	
	\item To evaluate $\P[ |\widetilde{{\mathcal W}}| < \vect{r}{K}_{\rm a}]$, consider a given $\vect{r}{K}_{\rm a} = K_{\rm a}$. Since ${\vect{r}{w}}_1,\dots,{\vect{r}{w}}_{K_{\rm a}}$ are drawn uniformly and independently from $[M]$, there are $M^{K_{\rm a}}$ possible $K_{\rm a}$-tuples. Among them, $\frac{M!}{(M-K_{\rm a})!}$ tuples have nonduplicate elements. Therefore, $\P[ |\widetilde{{\mathcal W}}| = K_{\rm a} \,\vert\, \vect{r}{K}_{\rm a} = K_{\rm a}] = \frac{M!}{(M-K_{\rm a})!} \frac{1}{M^{K_{\rm a}}}$. As a consequence, $\P[ |\widetilde{{\mathcal W}}| < \vect{r}{K}_{\rm a}] = 1 - \P[ |\widetilde{{\mathcal W}}| = \vect{r}{K}_{\rm a}] = 1- \E_{\vect{r}{K}_{\rm a}}\Big[\frac{M!}{M^{\vect{r}{K}_{\rm a}}(M-\vect{r}{K}_{\rm a})!}\Big]$.

	
	\item The probability $\P[\overline{U}]$ can be finally evaluated as
	\begin{align}
		\P[\overline{U}] &= \E_{\vect{r}{K}_{\rm a}}\Bigg[{\P[\bigcup_{i=1}^{\vect{r}{K}_{\rm a}} \|\vect{c}_{\vect{r}{w}_i}\|^2 > nP]}\Bigg] \\
		&\le \E_{\vect{r}{K}_{\rm a}} \Bigg[\sum_{i=1}^{\vect{r}{K}_{\rm a}}{\P[\|\vect{c}_{\vect{r}{w}_i}\|^2 > nP]}\Bigg] \label{eq:tmp675}\\
		&= \E[\vect{r}{K}_{\rm a}]  \frac{\Gamma(n,nP/P')}{\Gamma(n)}, \label{eq:tmp676}
	\end{align}
	where \eqref{eq:tmp675} follows from the union bound and \eqref{eq:tmp676} holds since $\|\vect{c}_{\vect{r}{w}_i}\|^2$ follows the Gamma distribution with shape $n$ and scale $P'$.
\end{itemize}
From the above calculations, we deduce that the total variation between the two measures is upper-bounded by $\tilde{p}$ defined in~\eqref{eq:p0}.
Hence, applying Lemma~\ref{lem:change_measure} to the random quantities $\ind{|\widetilde{{\mathcal W}}| \ne 0} \cdot \md$ and $\ind{|\widehat{{\mathcal W}}| \ne 0} \cdot \fa$, we consider implicitly the new measure from now on at a cost of adding $\tilde{p}$ to the original expectations. 

It remains to bound the \gls{MD} and \gls{FA} probabilities given in~\eqref{eq:pMD} and \eqref{eq:pFA}, respectively, under the new measure. For the sake of clarity, in Appendix~\ref{sec:special_case}, we shall prove a bound on $P_{\rm MD}$ and $P_{\rm FA}$ for a special case where i) $\vect{r}{K}_{\rm a}$ and $\vect{r}{K}'_{\rm a}$ are fixed and $r = 0$, i.e., there are always $K_{\rm a}$ users transmitting and the decoder always outputs a list of size $K'_{\rm a}$; ii) $K'_{\rm a} < \min\{K_{\rm a}, M-K_{\rm a}\}$. Later, in Appendix~\ref{sec:general_case}, we shall show how to extend the proof to the general case where $\vect{r}{K}_{\rm a}$ and $\vect{r}{K}'_{\rm a}$ are random and $r \ge 0$.

\subsection{A Special Case} \label{sec:special_case}
In the aforementioned special case, \eqref{eq:eps_MD} and \eqref{eq:eps_FA} become   
\begin{align}
	\epsilon_{\rm MD} &= \sum_{t = 0}^{K_{\rm a}'}\frac{t+K_{\rm a}-K_{\rm a}'}{K_{\rm a}} \min\{p_{t,t},q_{t,t}\} + \tilde{p}, \label{eq:eps_MD_simp}\\
	\epsilon_{\rm FA} &= \sum_{t = 0}^{K_{\rm a}'}  \frac{t}{K'_{\rm a}} \min\{p_{t,t}, q_{t,t}\} + \tilde{p}, \label{eq:eps_FA_simp}
\end{align}		
where $p_{t,t}$ and $q_{t,t}$ will be given shortly. The task is to show that $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ are indeed upper bounds of $P_{\rm MD}$ and $P_{\rm FA}$, respectively, in this special case.

Since the decoded list size $K'_{\rm a}$ is smaller than the number of transmitted messages~$K_{\rm a}$, $K_{\rm a} \!-\! {K_{\rm a}'}$ messages are initially misdetected, and there can be $t \!\in\! [0:K_{\rm a}']$ additional \glspl{MD} occurring during the decoding process. Exploiting symmetry, we assume \gls{wlog} that $\widetilde{{\mathcal W}} \!=\! [K_{\rm a}]$ and that the list of messages that are initially misdetected due to insufficient decoded list size is ${\mathcal W}_{01} = [{K}_{\rm a} \!-\! {K_{\rm a}'}]$.
Furthermore, let ${\mathcal W}_{02} = {\mathcal W}_{0} \setminus {\mathcal W}_{01}$ denote the set of $t$ additional \glspl{MD}.  Note that ${\mathcal W}_{02}$ is a generic subset of $[K_{\rm a} \!-\! {K_{\rm a}'} \!+\! 1:K_{\rm a}]$. Note also that $t$ is the number of \glspl{FA}, i.e., $|{\mathcal W}_0'| \!=\! t$. The relation between these sets of messages is depicted in Fig.~\ref{fig:venn_special_case}.
\begin{figure}
	\centering
	\begin{tikzpicture}[thick,scale=.9, every node/.style={scale=.9}]
		\def\radiusB{2cm}
		\def\radius{0.9*\radiusB}
		\def\mycolorbox#1{\textcolor{#1}{\rule{2ex}{2ex}}}
		\colorlet{colori}{gray!80}
		\colorlet{colorii}{gray!20}
		
	
		\coordinate (ceni) at (0,0);
		\coordinate[xshift=.95*\radiusB] (cenii);
		
		\coordinate (edge1a) at (-\radiusB,0.1cm);
		
		\coordinate (edge2a) at (\radiusB-\radius-.1cm,.1cm);
		
	
		\draw[fill=colori,fill opacity=0.5] (ceni) circle (\radiusB);
		\draw[fill=colorii,fill opacity=0.5] (cenii) circle (\radius);
		\draw (ceni) circle (\radiusB);
		
		\draw (edge1a) to (edge2a);
		
		\draw[-latex] (-1.35*\radiusB,-0.6*\radiusB) node[below,xshift=-.4cm,text width=3cm,font=\linespread{1}\selectfont,align=center] {\small Distinct transmitted messages $\widetilde{{\mathcal W}}$} -- (-.87*\radiusB,-0.5*\radiusB);
		\draw[-latex] (2*\radiusB,-0.6*\radiusB) node[below,xshift=.3cm,text width=2cm,font=\linespread{1}\selectfont,align=center] {\small Decoded messages $\widehat{{\mathcal W}}$} -- (1.7*\radiusB,-0.5*\radiusB);
		
		\node[yshift=1.25*\radiusB,xshift=-1.25cm,text width=4cm,font=\linespread{1}\selectfont,align=center] {\small \glspl{MD}: \\ ${\mathcal W}_0 = {\mathcal W}_{01} \cup {\mathcal W}_{02} = \widetilde{{\mathcal W}} \setminus \widehat{{\mathcal W}}$};
		
		\node[yshift=1.15*\radiusB,xshift=1cm,text width=4cm,font=\linespread{1}\selectfont,align=center] at (cenii) {\small \glspl{FA}: \\ ${\mathcal W}_0' = \widehat{{\mathcal W}} \setminus \widetilde{{\mathcal W}}$};
		
	
		\node[xshift=1cm,text width=1.5cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small correctly decoded messages $\widetilde{{\mathcal W}} \cap \widehat{{\mathcal W}}$};
		
		\node[yshift=.43*\radiusB,xshift=-.7cm,text width=2.3cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small $~~~~{K}_{\rm a}-K_{\rm a}'$ initial \glspl{MD} $~~~{\mathcal W}_{01}~~~$};
		
		\node[yshift=-.45*\radiusB,xshift=-.4*\radiusB,text width=1.8cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small $t$ additional \glspl{MD} $~~~~~~{\mathcal W}_{02}~~~$};
		
		
		\node[yshift=0cm,xshift=.45*\radiusB,text width=1.5cm,font=\linespread{1}\selectfont,align=center] at (cenii) {\small $t$ \glspl{FA} $~~~{\mathcal W}'_{0}~~~$};
	
	
	\end{tikzpicture}
	\caption{A diagram depicting the relation between the sets of messages defined for the special case in Appendix~\ref{sec:special_case}.}
	\label{fig:venn_special_case}
\end{figure}

Using the above definitions, the set of transmitted messages can be expressed as ${\mathcal W} = \widetilde{{\mathcal W}} = {\mathcal W}_{01} \cup {\mathcal W}_{02} \cup (\widetilde{{\mathcal W}} \setminus {\mathcal W}_0)$, and the received signal is $\rvVec{y} = c({\mathcal W}_{01}) + c({\mathcal W}_{02}) + c(\widetilde{{\mathcal W}} \setminus {\mathcal W}_0) + \rvVec{z}$. Since the messages in ${\mathcal W}_{01}$ are always misdetected, the best approximation of ${\mathcal W}$ that the decoder can produce is ${\mathcal W}_{02} \cup (\widetilde{{\mathcal W}} \setminus {\mathcal W}_0)$. However, under the considered error event $\widetilde{{\mathcal W}} \to \widehat{{\mathcal W}}$, the messages in ${\mathcal W}_{02}$ are misdetected by the ones in ${\mathcal W}_0'$, and thus the actual decoded list is ${\mathcal W}_{0}' \cup (\widetilde{{\mathcal W}} \setminus {\mathcal W}_0)$. Therefore, $\widetilde{{\mathcal W}} \to \widehat{{\mathcal W}}$ implies that $\|\rvVec{y} - c({\mathcal W}_{0}') - c({\mathcal W} \setminus {\mathcal W}_0)\|^2 < \|\rvVec{y} - c({\mathcal W}_{02}) - c({\mathcal W} \setminus {\mathcal W}_0))\|^2$, which is equivalent to
\begin{align}
 \|c({\mathcal W}_{01}) + c({\mathcal W}_{02})- c({\mathcal W}_{0}') + \rvVec{z}\|^2
< \|c({\mathcal W}_{01}) + \rvVec{z}\|^2. \label{eq:tmp1798}
\end{align}
Let $F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')$ denote the set of $({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')$ such that~\eqref{eq:tmp1798} holds. 

We now compute the expectations in~\eqref{eq:pMD} and \eqref{eq:pFA}.
Recall that, under assumptions just stated, we have $|{\mathcal W}_0| =  t + K_{\rm a} - K'_{\rm a}$, $|{\mathcal W}_0'| = |{\mathcal W}_{02}| = t$, and $|\widehat{{\mathcal W}}| = K'_{\rm a}$. 
It follows from \eqref{eq:pMD} and \eqref{eq:pFA} that, after the change of measure in Appendix~\ref{sec:change_measure}, $P_{\rm MD}$ and $P_{\rm FA}$ can be bounded as
\begin{align}
	P_{\rm MD} &\le \sum_{t=0}^{K'_{\rm a}} \frac{t+K_{\rm a}-{K_{\rm a}'}}{K_{\rm a}} \P[|{\mathcal W}_{02}| = t] + \tilde{p},  \label{eq:tmp850_simp}\\
	P_{\rm FA} &\le \sum_{t=0}^{K'_{\rm a}} \frac{t}{K_{\rm a}'} \P[|{\mathcal W}_{02}| = t] + \tilde{p}. \label{eq:tmp853_simp}
\end{align} 
Next, we proceed to bound $\P[|{\mathcal W}_{02}| = t]$ 
following two approaches. The first approach is based on error exponent analyses, resulting in the term $p_{t,t}$ in~\eqref{eq:eps_MD_simp}. The second approach is a variation of the DT bound \cite[Th.~17]{Polyanskiy2010}, resulting in $q_{t,t}$ in~\eqref{eq:eps_MD_simp}.

\subsubsection{The Error-Exponent-Based Approach}  \label{sec:1st_approach}
By writing the event $|{\mathcal W}_{02}| = t$ as a union of the pairwise error events $F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0})$, we have that 
\begin{align}
	&\P[{|{\mathcal W}_{02}| = t}]
	= \P[\bigcup_{{\mathcal W}_{02} \subset [K_{\rm a} - {K_{\rm a}'} + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} \bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t} F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')]. \label{eq:tmp901_simp} 
\end{align}
Next, given $c({\mathcal W}_{01})$, $c({\mathcal W}_{02})$, and $\rvVec{z}$, it holds for every $\lambda > -\frac{1}{tP'}$ that
\begin{align}
	\P[F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')]
	&\le e^{\lambda \|c({\mathcal W}_{01}) + \|\rvVec{z}\|^2}
	\E_{c({\mathcal W}_{0}')}\Big[e^{-\lambda \|c({\mathcal W}_{01}) + c({\mathcal W}_{02})- c({\mathcal W}_{0}') + \rvVec{z}\|^2}\Big] \label{eq:tmp766_simp}\\
	&= e^{\lambda \|c({\mathcal W}_{01}) + \rvVec{z}\|^2} (1+\lambda tP')^{-n}
	\exp\bigg(-\frac{\lambda\|c({\mathcal W}_{01}) + c({\mathcal W}_{02}) + \rvVec{z}\|^2}{1+\lambda t P'}\bigg), \label{eq:tmp768_simp}
\end{align}
where \eqref{eq:tmp766_simp} follows from the Chernoff bound in Lemma~\ref{lem:Chernoff}, and \eqref{eq:tmp768_simp} follows by computing the expectation in~\eqref{eq:tmp766_simp} using Lemma~\ref{lem:chi2}.
Next, we apply Gallager's $\rho$-trick in Lemma~\ref{lem:Gallager} and conclude that, given $c({\mathcal W}_{01})$, $c({\mathcal W}_{02})$, and $\rvVec{z}$, it holds for every $\rho \in [0,1]$ that
\begin{align}


	&\P[\bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t} F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')] \\
	&\le \binom{M-K_{\rm a}}{t}^\rho (1+\lambda tP')^{-n\rho}
	\exp\Bigg(\lambda \rho \bigg(\|c({\mathcal W}_{01}) + \rvVec{z}\|^2 -\frac{\|c({\mathcal W}_{01}) \!+\! c({\mathcal W}_{02}) \!+\! \rvVec{z}\|^2}{1+\lambda t P'}\bigg)\Bigg). \label{eq:tmp803_simp}
\end{align}
Taking the expectation over $c({\mathcal W}_{02})$ using Lemma~\ref{lem:chi2}, we obtain for given $c({\mathcal W}_{01})$ and $\rvVec{z}$ that
\begin{align}
	\P[\bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t} F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')]
	&\le \binom{M-K_{\rm a}}{t}^\rho (1\!+\!\lambda tP')^{-n\rho} \Big(1+\frac{\lambda \rho t P'}{1\!+\!\lambda tP'}\Big)^{-n} \notag \\
	&\quad \cdot \exp\Bigg(\!\lambda\rho \bigg(1-\frac{1}{1+\lambda P't(1+\rho)}\bigg)\|c({\mathcal W}_{01}) + \rvVec{z}\|^2\Bigg) \\
	&= \binom{M-K_{\rm a}}{t}^\rho \exp\left(b_0\|c({\mathcal W}_{01})  + \rvVec{z}\|^2 - na_0\right), \label{eq:tmp811}
\end{align}
where $a_0$ and $b_0$ are obtained by taking $t' = t$ in~\eqref{eq:a} and \eqref{eq:b}, respectively. 
Now applying Gallager's $\rho$-trick again, we obtain that, for every $\rho_1 \in [0,1]$,
\begin{align}
	&\P[\bigcup_{{\mathcal W}_{02} \subset [K_{\rm a} - {K_{\rm a}'} + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} \bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t} F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{0}')] \notag \\
	&\le \binom{K_{\rm a}'}{t}^{\rho_1} \binom{M-K_{\rm a}}{t}^{\rho\rho_1} 
	\E[\exp\left(\rho_1 b_0\|c({\mathcal W}_{01}) + \rvVec{z}\|^2 - n\rho_1 a_0\right)]  \label{eq:tmp797_simp} \\
	&= \binom{K_{\rm a}'}{t}^{\rho_1} \binom{M-K_{\rm a}}{t}^{\rho\rho_1} e^{-n\rho_1 a_0} \big(1-\rho_1P_2b_0\big)^{-n}, \label{eq:tmp800_simp}
\end{align}
where the last equality follows by computing the expectation in~\eqref{eq:tmp797_simp} jointly over $c({\mathcal W}_{01})$ and $\rvVec{z}$ using Lemma~\ref{lem:chi2}, and by setting $P_2= 1+(K_{\rm a} - K_{\rm a}')P'$. Finally, substituting the result into \eqref{eq:tmp901_simp}, we obtain 
\begin{align}
	\P[|{\mathcal W}_{02}| = t]
	&\le \binom{K_{\rm a}'}{t}^{\rho_1} \binom{M-K_{\rm a}}{t}^{\rho\rho_1} e^{-n\rho_1 a_0} \big(1-\rho_1P_2b_0\big)^{-n}
	\triangleq p_{t,t}. \label{eq:tmp1148_simp}
\end{align}

\subsubsection{The DT-Based Approach} \label{sec:2nd_approach}
Next, we present an alternative bound on $\P[{|{\mathcal W}_{02}| = t}]$. Consider the channel law $P_{\rvVec{y} \,\vert\, c({\mathcal W}_{0}), c({\mathcal W} \setminus {\mathcal W}_0)}$ with input $c({\mathcal W}_{0})$ and output $\rvVec{y}$ where $|{\mathcal W}_{02}| = t$. The corresponding information density~\cite[Def. 17.1]{Polyanskiy2019lecture} 
is given by
\begin{align}
	\imath_t(c({\mathcal W}_{0});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0))
	&= n \ln(1+(t+K_{\rm a}-K_{\rm a}')P') + \frac{\|\rvVec{y} - c({\mathcal W} \setminus {\mathcal W}_0)\|^2}{1+(t+K_{\rm a}-K_{\rm a}')P'} \notag \\
	&\quad - \|\rvVec{y} - c({\mathcal W}_0) - c({\mathcal W} \setminus {\mathcal W}_0)\|^2. 


\end{align}
Note that~\eqref{eq:tmp1798} is equivalent to $\imath_t(c({\mathcal W}_{0}');\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)) > \imath_t(c({\mathcal W}_{02});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)).$ 
Let
	$\vect{r}{I}_t \triangleq \displaystyle\min_{{\mathcal W}_{02} \subset [K_{\rm a} - {K_{\rm a}'} + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} \imath_t(c({\mathcal W}_{02});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)).$
For a fixed arbitrary $\gamma$, it follows that
\begin{align}
	&\P[{|{\mathcal W}_{02}| = t}] \notag \\






	&=\P[I_{t} \le \gamma]\P[{|{\mathcal W}_{02}| = t \;\big|\; I_{t} \le \gamma}]
	+ \P[I_{t} > \gamma]\P[{|{\mathcal W}_{02}| = t \;\big|\; I_{t} > \gamma}] \\
	&\le \P[I_{t} \le \gamma] + \P[{|{\mathcal W}_{02}| = t \;\big|\; I_{t} > \gamma}] \label{eq:tmp838_simp}\\

	&= \P[I_{t} \le \gamma] \notag \\
	&\quad+ \P[ \! \bigcup_{{\mathcal W}_{02} \subset [K_{\rm a} - {K_{\rm a}'} + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} \! \bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t} \!\! \!\big\{\imath_t(c({\mathcal W}_{0}');\rvVec{y} \,\vert\, c({\mathcal W} \setminus\! {\mathcal W}_0))
	\!>\! \imath_t(c({\mathcal W}_{02});\rvVec{y} \,\vert\, c({\mathcal W} \setminus\! {\mathcal W}_0))\big\} \Big| I_{t} \!>\! \gamma\!] \label{eq:tmp814_simp} \\
	&\le  \P[I_{t} \le \gamma] + \P[\bigcup_{{\mathcal W}_{02} \subset [K_{\rm a} - {K_{\rm a}'} + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} \bigcup_{{\mathcal W}_{0}' \subset [K_{\rm a}+1:M] \atop |{\mathcal W}_{0}'| = t}
	\big\{\imath_t(c({\mathcal W}_{0}');\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)) > \gamma\big\}]. \label{eq:tmp383_simp}
\end{align}
Here, \eqref{eq:tmp814_simp} follows by writing explicitly the event $\{|{\mathcal W}_{02}| = t\}$, and \eqref{eq:tmp383_simp} by relaxing the inequality inside the second probability.
Using that $\P[\imath(x;\vect{r}{y}) > \gamma] \le e^{-\gamma}, \forall x$~\cite[Cor.~17.1]{Polyanskiy2019lecture}, we obtain
\begin{align}
	\P[\imath_t(c({\mathcal W}_{0}');\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)) > \gamma] \le e^{-\gamma}.
\end{align}
Then, by applying the union bound and taking the infimum over $\gamma$, we conclude that
\begin{align}
	\P[{|{\mathcal W}_{02}| = t}]
	&\le \inf_{\gamma} \bigg( \P[\vect{r}{I}_t \le \gamma] +  \binom{K_{\rm a}'}{t}  \binom{M-K_{\rm a}}{t}  e^{-\gamma} \bigg)
	\triangleq q_{t,t}. \label{eq:tmp1201_simp}
\end{align}
This concludes the DT-based approach.

It follows from \eqref{eq:tmp1148_simp} and \eqref{eq:tmp1201_simp} that
$\P[|{\mathcal W}_{02}| = t] \le \min\left\{p_{t,t}, q_{t,t} \right\}$.
Introducing this bound into \eqref{eq:tmp850_simp} and \eqref{eq:tmp853_simp}, we obtain that the \gls{MD} and \gls{FA} probabilities, averaged over the Gaussian codebook ensemble, are upper-bounded by $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ given in~\eqref{eq:eps_MD_simp} and \eqref{eq:eps_FA_simp}, respectively. 



\subsection{The General Case}  \label{sec:general_case}
We now explain how the result in the special case considered in the previous subsection can be extended to the general case where $\vect{r}{K}_{\rm a}$ and $\vect{r}{K}'_{\rm a}$ are random and $r \ge 0$. 
For random $\vect{r}{K}_{\rm a}$ and $\vect{r}{K}'_{\rm a}$, one has to take into account all the possible combinations of the number of transmitted messages and decoded messages when computing the expectations in~\eqref{eq:pMD} and \eqref{eq:pFA}. Consider the event that $K_{\rm a}$ users are active and the estimation of $K_{\rm a}$ results in $K_{\rm a}'$, which we denote by $K_{\rm a} \to K_{\rm a}'$. As in the special case, we assume \gls{wlog} that $\widetilde{{\mathcal W}} = [{K}_{\rm a}]$. Furthermore, exploiting symmetry, we let ${\mathcal W}_{01} = [({K}_{\rm a} - \overline{K_{\rm a}'})^+]$ the list of $({K}_{\rm a} - \overline{K_{\rm a}'})^+$ initial \glspl{MD} due to insufficient decoded list size, and ${\mathcal W}_{02} = {\mathcal W}_0 \setminus {\mathcal W}_{01}$ denote the list of $t$ additional \glspl{MD} occurring during the decoding process. 
Note also that,
if $\underline{K_{\rm a}'} > K_{\rm a}$, the decoder always outputs more than $K_{\rm a}$ messages. Hence, at least $\underline{K_{\rm a}'} - K_{\rm a}$ decoded messages are falsely alarmed. Exploiting symmetry, we let \gls{wlog} ${\mathcal W}_{01}' = [{K}_{\rm a} + 1: \underline{K_{\rm a}'}]$ the list of $(\underline{K_{\rm a}'}-{K}_{\rm a})^+$ initial \glspl{FA} due to excessive decoded list size, and ${\mathcal W}_{02}' = {\mathcal W}_0' \setminus {\mathcal W}_{01}'$ denote the list of $t'$ additional \glspl{FA} occurring during the decoding process. In Fig.~\ref{fig:venn}, we depict the relation between these sets of messages. Under these assumptions, ${\mathcal W}_{02}$ and ${\mathcal W}_{02}'$ are generic subsets of $[({K}_{\rm a} - \overline{K_{\rm a}'})^+ + 1:{K}_{\rm a}]$  and $[\max\{{K}_{\rm a},\underline{K_{\rm a}'}\}+1 : M]$, respectively.

\begin{figure}
	\centering
	\begin{tikzpicture}[thick,scale=.9, every node/.style={scale=.9}]
		\def\radius{2.2cm}
		\def\radiusB{0.9*\radius}
		\def\mycolorbox#1{\textcolor{#1}{\rule{2ex}{2ex}}}
		\colorlet{colori}{gray!80}
		\colorlet{colorii}{gray!20}
		
	
		\coordinate (ceni) at (0,0);
		\coordinate[xshift=1.05*\radius] (cenii);
		
		\coordinate (edge1a) at (-\radiusB,0.1cm);
		\coordinate(edge1b) at (\radiusB,-.2cm);
		
		\coordinate (edge2a) at (\radius-\radiusB-.1cm,.1cm);
		\coordinate (edge2b) at (\radius+\radiusB+.3cm,-.2cm);
		
	
		\draw[fill=colori,fill opacity=0.5] (ceni) circle (\radiusB);
		\draw[fill=colorii,fill opacity=0.5] (cenii) circle (\radius);
		\draw (ceni) circle (\radiusB);
		
		\draw (edge1a) to (edge2a);
		\draw (edge1b) to (edge2b);
		
		\draw[-latex] (-1.1*\radius,-0.6*\radius) node[below,xshift=-.4cm,text width=3cm,font=\linespread{1}\selectfont,align=center] {\small Distinct transmitted messages $\widetilde{{\mathcal W}}$} -- (-0.77*\radius,-0.5*\radius);
		\draw[-latex] (2.13*\radius,-0.6*\radius) node[below,xshift=.3cm,text width=2cm,font=\linespread{1}\selectfont,align=center] {\small Decoded messages $\widehat{{\mathcal W}}$} -- (1.93*\radius,-0.5*\radius);
		
		\node[yshift=1.1*\radius,xshift=-1.25cm,text width=4cm,font=\linespread{1}\selectfont,align=center] {\small \glspl{MD}: \\ ${\mathcal W}_0 = {\mathcal W}_{01} \cup {\mathcal W}_{02} = \widetilde{{\mathcal W}} \setminus \widehat{{\mathcal W}}$};
		
		\node[yshift=1.2*\radius,xshift=1.25cm,text width=4cm,font=\linespread{1}\selectfont,align=center] at (cenii) {\small \glspl{FA}: \\ ${\mathcal W}_0' = {\mathcal W}'_{01} \cup {\mathcal W}'_{02} = \widehat{{\mathcal W}} \setminus \widetilde{{\mathcal W}}$};
		
	
		\node[xshift=1cm,text width=1.5cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small correctly decoded messages $\widetilde{{\mathcal W}} \cap \widehat{{\mathcal W}}$};
		\node[yshift=.43*\radius,xshift=-.68cm,text width=2.3cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small $~~~~({K}_{\rm a}-\overline{K_{\rm a}'})^+$ initial \glspl{MD} $~~~{\mathcal W}_{01}~~~$};
		\node[yshift=-.4*\radius,xshift=-.37*\radius,text width=1.8cm,font=\linespread{1}\selectfont,align=center] at (ceni) {\small $t$ additional \glspl{MD} $~~~~~~{\mathcal W}_{02}~~~$};
		\node[yshift=.4*\radius,xshift=.27*\radius,text width=1.7cm,font=\linespread{1}\selectfont,align=center] at (cenii) {\small $(\underline{K_{\rm a}'}-{K}_{\rm a})^+$ initial \glspl{FA} $~~~{\mathcal W}'_{01}~~~$};
		\node[yshift=-1.2cm,xshift=.28*\radius,text width=1.9cm,font=\linespread{1}\selectfont,align=center] at (cenii) {\small $t'$ additional \glspl{FA} $~~~{\mathcal W}'_{02}~~~$};
	
	
	\end{tikzpicture}
	\caption{A diagram depicting the relation between the sets of messages defined for the general case in Appendix~\ref{sec:general_case}.}
	\label{fig:venn}
\end{figure}

Note that in the special case considered in Appendix~\ref{sec:special_case}, $t$ can take value from $0$ to $K'_{\rm a}$ while $t' = t$. In the general case, instead:
\begin{itemize}
	\item The possible values of $t$ belong to the set ${\mathcal T}$ defined in~\eqref{eq:T}. This is because the number of \glspl{MD}, given by $t+{(K_{\rm a}-\overline{K_{\rm a}'})}^+$, is upper-bounded by the total number $K_{\rm a}$ of transmitted messages, and by $M-\underline{K_{\rm a}'}$ (since at least $\underline{K_{\rm a}'}$ messages are returned).
	
	\item Given $t$, the integer $t'$ takes value in $\overline{{\mathcal T}}_t$ defined in~\eqref{eq:Tbart} because: i) the decoded list size, given by $K_{\rm a} - t - {(K_{\rm a} - \overline{K_{\rm a}'})}^+ + t' + {(\underline{K_{\rm a}'}-K_{\rm a})}^+$, must be in $[\underline{K_{\rm a}'} : \overline{K_{\rm a}'}]$; ii) the number of \glspl{FA}, given by $t'+ (\underline{K_{\rm a}'}-K_{\rm a})^+$, is upper-bounded by the number $M-K_{\rm a}$ of messages that are not transmitted, and by the maximal number $\overline{K_{\rm a}'}$ of decoded messages.
	
	\item If the decoded list size is further required to be strictly positive,
	then $t'$ takes value in ${\mathcal T}_t$ defined in~\eqref{eq:Tt}.
\end{itemize}

Using the above definitions, the best approximation of $\widetilde{{\mathcal W}}$ that the decoder can produce is ${\mathcal W}_{01}' \cup {\mathcal W}_{02} \cup ({\mathcal W} \setminus {\mathcal W}_0)$, while the actual decoded list, under $\widetilde{{\mathcal W}} \to \widehat{{\mathcal W}}$, is ${\mathcal W}_{01}' \cup {\mathcal W}'_{02} \cup ({\mathcal W} \setminus {\mathcal W}_0)$. Therefore, $\widetilde{{\mathcal W}} \to \widehat{{\mathcal W}}$ implies that $\|\rvVec{y} - c({\mathcal W}_{01}') - c({\mathcal W}'_{02}) - c({\mathcal W} \setminus {\mathcal W}_0)\|^2 < \|\rvVec{y} - c({\mathcal W}_{01}') - c({\mathcal W}_{02}) - c({\mathcal W} \setminus {\mathcal W}_0)\|^2$, which is equivalent to
\begin{align}
\|c({\mathcal W}_{01}) + c({\mathcal W}_{02})- c({\mathcal W}_{01}') - c({\mathcal W}_{02}') + \rvVec{z}\|^2
	< \|c({\mathcal W}_{01}) - c({\mathcal W}_{01}') + \rvVec{z}\|^2. \label{eq:eventF}
\end{align}
Let $F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{01}',{\mathcal W}_{02}')$ denote the set of $({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{01}',{\mathcal W}_{02}')$ such that~\eqref{eq:eventF} holds.



We now compute the expectations in $P_{\rm MD}$ given by~\eqref{eq:pMD} and $P_{\rm FA}$ given by~\eqref{eq:pFA}.
Given $|{\mathcal W}_{02}| = t$ and $|{\mathcal W}_{02}'| = t'$, we have that $|{\mathcal W}_0| = t+(\vect{r}{K}_{\rm a} - \overline{K_{\rm a}'})^+$, $|{\mathcal W}_0'| = t + (\underline{K_{\rm a}'}-\vect{r}{K}_{\rm a})^+$, and $|\widehat{{\mathcal W}}| = \vect{r}{K}_{\rm a} - t - (\vect{r}{K}_{\rm a} - \overline{K_{\rm a}'})^+ + t' + (\underline{K_{\rm a}'}-\vect{r}{K}_{\rm a})^+$. 
It follows from \eqref{eq:pMD} and \eqref{eq:pFA} that, after the change of measure in Appendix~\ref{sec:change_measure}, $P_{\rm MD}$ and $P_{\rm FA}$ can be bounded as
\begin{align}
	P_{\rm MD} &\le \sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_{u}} \sum_{t\in {\mathcal T}}\frac{t+(K_{\rm a}-\overline{K_{\rm a}'})^+}{K_{\rm a}}
	\P[|{\mathcal W}_{02}| = t, K_{\rm a} \to K_{\rm a}']
	+ \tilde{p},  \label{eq:tmp850}\\
	P_{\rm FA} &\le \sum_{K_{\rm a} =K_\ell}^{K_{u}} \bigg(P_{\vect{r}{K}_{\rm a}}(K_{\rm a}) \sum_{K_{\rm a}' = K_\ell}^{K_{u}}  \sum_{t\in {\mathcal T}} \sum_{t' \in {\mathcal T}_t}
	 \frac{t'+(\underline{K_{\rm a}'} - K_{\rm a})^+}{K_{\rm a} \!-\! t \!-\! {(K_{\rm a} \!-\! \overline{K_{\rm a}'})}^+ \!\!+\! t' \!+\! {(\underline{K_{\rm a}'}\!-\!K_{\rm a})}^+\!} \notag \\
	&\qquad \quad \cdot \P[|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', K_{\rm a} \to K_{\rm a}'] \bigg) + \tilde{p}. \label{eq:tmp853}
\end{align} 

Next, we proceed to bound the joint probability $\P[|{\mathcal W}_{02}| = t,K_{\rm a} \to K_{\rm a}']$ in \eqref{eq:tmp850} and the joint probability $\P[|{\mathcal W}_{02}| = t,|{\mathcal W}_{02}'| = t',K_{\rm a} \to K_{\rm a}']$ in \eqref{eq:tmp853}. Let
	$A(K_{\rm a},K_{\rm a}') \triangleq 
	\{m(\rvVec{y},K_{\rm a}') > m(\rvVec{y},K), \forall K \ne K_{\rm a}'\}$.
Since the event $K_{\rm a} \to K_{\rm a}'$ implies that $|\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]$ and that $A(K_{\rm a},K_{\rm a}')$ occurs,
we have 
\begin{align}
	\P[|{\mathcal W}_{02}| = t, K_{\rm a} \to K_{\rm a}']
	&\le \P[{{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}|\in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}}],A(K_{\rm a},K_{\rm a}')}] \\
	&\le \min\left\{\P[{|{\mathcal W}_{02}| \!=\! t, |\widehat{{\mathcal W}}|\in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}],  \P[A(K_{\rm a},K_{\rm a}')] \right\}, \label{eq:tmp883}

\end{align}
where \eqref{eq:tmp883} follows from the fact that the joint probability is upper-bounded by each of the individual probabilities. 
Similarly, it follows that
\begin{multline}
	\P[|{\mathcal W}_{02}| = t,|{\mathcal W}_{02}'| = t', K_{\rm a} \to K_{\rm a}']
	\\ \le \min\Big\{\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}|\in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}],
	 \P[A(K_{\rm a},K_{\rm a}')] \Big\}. \label{eq:tmp1054}
\end{multline}
We next present the bounds on the probabilities $\P[A(K_{\rm a},K_{\rm a}')]$, $\P[{|{\mathcal W}_{02}| \!=\! t,  |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$, and $\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t',  |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$.

\subsubsection{Bound on $\P[A(K_{\rm a},K_{\rm a}')]$} \label{sec:bound_xi}
We have
\begin{align}
	\P[A(K_{\rm a},K_{\rm a}')] 
	&= \P[m(\rvVec{y},K_{\rm a}') > m(\rvVec{y},K), \forall K \ne K_{\rm a}'] \\ 
	&\le\min_{K \in [K_\ell:K_u] \colon K \ne K_{\rm a}'}\P[m(\rvVec{y},K_{\rm a}') > m(\rvVec{y},K)] \\

	&= \xi(K_{\rm a},K_{\rm a}'). \label{eq:tmp1077}
\end{align}
Note that under the new measure, $\rvVec{y} \sim {\mathcal C}{\mathcal N}(\mathbf{0},(1+K_{\rm a} P')\mat{\mathrm{I}}_n)$. 

\subsubsection{Bounds on $\P[{|{\mathcal W}_{02}| = t,  |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$} \label{sec:bound_tMDs}
As in Appendix~\ref{sec:special_case}, we follow two approaches to bound $\P[{|{\mathcal W}_{02}| = t,  |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$. The first approach is based on error exponent analyses and the second approach is based on the DT bound. In the first approach, we write the event $\{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]\}$ as a union of the pairwise events and obtain
\begin{align}
	&\P[{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \notag \\



	&= \P[\bigcup_{t' \in \overline{{\mathcal T}}_t} \bigcup_{{\mathcal W}_{02} \subset [(K_{\rm a} - \overline{K_{\rm a}'})^+ + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t}

	\bigcup_{{\mathcal W}_{02}' \subset [\max\{K_{\rm a},\underline{K_{\rm a}'}\}+1:M] \atop |{\mathcal W}_{02}'| = t'}
	F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{01}',{\mathcal W}_{02}') ]. \label{eq:tmp901} 
\end{align}
Then, by applying the Chernoff bound, Gallager's $\rho$-trick, and Lemma~\ref{lem:chi2}  following similar steps as in Appendix~\ref{sec:1st_approach}, we obtain
\begin{align}
	\P[{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \le p_t \label{eq:tmp1148}
\end{align}
with $p_t$ given by~\eqref{eq:pt}.  In the second approach, we consider the channel law $P_{\rvVec{y} \,\vert\, c({\mathcal W}_{0}), c({\mathcal W} \setminus {\mathcal W}_0)}$ with input $c({\mathcal W}_{0})$ and output $\rvVec{y}$ where $|{\mathcal W}_{02}| \!=\! t$. The corresponding information density $\imath_t(c({\mathcal W}_{0});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0))$ is defined in~\eqref{eq:infor_den}. Note that~\eqref{eq:eventF} is equivalent to $\imath_t(c({\mathcal W}_{01}')+c({\mathcal W}_{02}');\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)) > \imath_t(c({\mathcal W}_{01}') + c({\mathcal W}_{02});\rvVec{y} \,\vert\, c({\mathcal W} \setminus {\mathcal W}_0)).$ 
Then, by proceeding as in Appendix~\ref{sec:2nd_approach}, we obtain 
\begin{align}
	\P[{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \le q_t \label{eq:tmp1201}
\end{align}
with $q_t$ given by~\eqref{eq:qt}.

\subsubsection{Bounds on $\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$} 
First, we have that 
\begin{align}
	&\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \notag \\
	&= \P[\bigcup_{{\mathcal W}_{02} \subset [(K_{\rm a} - \overline{K_{\rm a}'})^+ + 1:K_{\rm a}] \atop |{\mathcal W}_{02}| = t} 
	\bigcup_{{\mathcal W}_{02}' \subset [\max\{K_{\rm a},\underline{K_{\rm a}'}\}+1:M] \atop |{\mathcal W}_{02}| = t'}
	F({\mathcal W}_{01},{\mathcal W}_{02},{\mathcal W}_{01}',{\mathcal W}_{02}')]. \label{eq:tmp365}
\end{align}
Note that  $\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$ differs from  $\P[{|{\mathcal W}_{02}| = t, |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}]$ in~\eqref{eq:tmp901} only in that the union over ${t'\in \overline{{\mathcal T}}_t}$ is absent. By applying the Chernoff bound, Gallager's $\rho$-trick, and Lemma~\ref{lem:chi2} following similar steps as in Appendix~\ref{sec:1st_approach}, we conclude that
\begin{align}
	\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \le  p_{t,t'} \label{eq:tmp1217}
\end{align}
with $p_{t,t'}$ given by~\eqref{eq:ptt}.
Alternatively, bounding $\P\Big[|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]\Big]$ as in Appendix~\ref{sec:2nd_approach}, we obtain 
\begin{align}
	\P[{|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', |\widehat{{\mathcal W}}| \in [\underline{K_{\rm a}'}:\overline{K_{\rm a}'}]}] \le q_{t,t'} \label{eq:tmp1226}
\end{align}
with $p_{t,t'}$ given by~\eqref{eq:qtt}.

\vspace{.3cm}
It now follows from \eqref{eq:tmp883}, \eqref{eq:tmp1077}, \eqref{eq:tmp1148}, and \eqref{eq:tmp1201} that 
\begin{align}
	\P[|{\mathcal W}_{02}| = t, K_{\rm a} \to K_{\rm a}'] \le \min\left\{p_t, q_t, \xi(K_{\rm a},K_{\rm a}') \right\}.
\end{align}
From \eqref{eq:tmp1054}, \eqref{eq:tmp1077}, \eqref{eq:tmp1217}, and \eqref{eq:tmp1226}, we obtain that 
\begin{align}
	\P[|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', K_{\rm a} \to K_{\rm a}']
	&\le \min\left\{p_{t,t'}, q_{t,t'}, \xi(K_{\rm a},K_{\rm a}') \right\}.
\end{align}
Substituting these bounds on $\P[|{\mathcal W}_{02}| = t, K_{\rm a} \to K_{\rm a}']$ and $\P[|{\mathcal W}_{02}| = t, |{\mathcal W}_{02}'| = t', K_{\rm a} \to K_{\rm a}']$ into \eqref{eq:tmp850} and \eqref{eq:tmp853}, we deduce that the \gls{MD} and \gls{FA} probabilities, averaged over the Gaussian codebook ensemble, are upper-bounded by $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ given in~\eqref{eq:eps_MD} and \eqref{eq:eps_FA}, respectively. Finally, by proceeding as in \cite[Th.~19]{Polyanskiy2011feedback}, one can show that there exists a randomized coding strategy that achieves \eqref{eq:eps_MD} and \eqref{eq:eps_FA} and involves time-sharing among at most three deterministic codes, as explained in Remark~\ref{remark:U}.


\section{Proof of Theorem~\ref{thm:xi}}
\label{proof:xi}
Let $\rvVec{y}_0 \sim {\mathcal C}{\mathcal N}(\mathbf{0},(1+K_{\rm a}P')\mat{\mathrm{I}}_n)$.
The probability density function of $\rvVec{y}_0$ is given by
$
	p_{\rvVec{y}_0}(\vect{y}_0) = \frac{1}{\pi^n (1+K_{\rm a} P')^n} \exp\left(-\frac{\|\vect{y}_0\|^2}{1+K_{\rm a} P'}\right).
$
Therefore, with \gls{ML} estimation of $\vect{r}{K}_{\rm a}$, we have that
$
	m(\rvVec{y}_0,K) = \ln p_{\rvVec{y}_0}(\vect{y}_0) = - \frac{\|\vect{y}_0\|^2}{1+K P'} - n\ln(1+K P') - n \ln \pi.
$
As a consequence, the event $m\left(\rvVec{y}_0,K_{\rm a}'\right) > m\left(\rvVec{y}_0,K\right)$ can be written as $\frac{\|\rvVec{y}_0\|^2}{1+K_{\rm a}' P'} + n\ln(1+K_{\rm a}' P') < \frac{\|\rvVec{y}_0\|^2}{1+K P'} + n\ln(1+K P')$, or equivalently, 
\begin{equation}
	\|\rvVec{y}_0\|^2 \left(\frac{1}{1+K_{\rm a}'P'} - \frac{1}{1+KP'}\right) < n \ln\left(\frac{1+KP'}{1+K_{\rm a}'P'}\right). \label{eq:eventKa}
\end{equation}
Using the fact that $\|\rvVec{y}_0\|^2$ follows a Gamma distribution with shape $n$ and scale $1+K_{\rm a} P'$, we deduce that $\xi(K_{\rm a},K_{\rm a}')$ is given by~\eqref{eq:xi_ML} 	with $
\zeta(K,K_{\rm a},K_{\rm a}')$ given by~\eqref{eq:zeta_ML}.

For energy-based estimation, i.e., $m(\vect{y},K) = -\big|\|\vect{y}\|^2 - n(1 + KP') \big|$, we can show after some manipulations that the event  $m\left(\rvVec{y}_0,K_{\rm a}'\right) > m\left(\rvVec{y}_0,K\right)$ is equivalent to
\begin{align}
	\begin{cases}
		\|\rvVec{y}_0\|^2 > n\left(1 + \frac{K_{\rm a} + K_{\rm a}'}{2}P'\right), &\text{if~} K_{\rm a}' < K_{\rm a}, \\
		\|\rvVec{y}_0\|^2 < n\left(1 + \frac{K_{\rm a} + K_{\rm a}'}{2}P'\right), &\text{if~} K_{\rm a}' > K_{\rm a}. 
	\end{cases}
\end{align}
Thus, using that $\|\rvVec{y}_0\|^2$ is Gamma distributed, we deduce that $\xi(K_{\rm a},K_{\rm a}')$ is given by~\eqref{eq:xi_ML} with $\zeta(K,K_{\rm a},K_{\rm a}')$ given by~\eqref{eq:zeta_energy}.





\section{Proof of Theorem~\ref{thm:error_floor}} \label{proof:error_floor}
First, the optimal value of $P'$ minimizing the bounds must grow with $P$ since otherwise $\tilde{p}$ will be large. Therefore, as $P\to \infty$, we can assume without loss of optimality that $P' \to \infty$. Next, when $t = t' = 0$, we can verify that $a = b = 0$, thus $E_0(\rho,\rho_1) = 0$ and $E(0,0) = 0$, achieved with $\rho = \rho_1 = 0$. Therefore, $p_0 = p_{0,0} = e^{-n\cdot 0} = 1$. We can also verify that $q_0$ and $q_{0,0}$ both converge to $1$ as $P' \to \infty$.
When $P' \to \infty$, $\xi(K_{\rm a},K_{\rm a}')$ given in Theorem~\ref{thm:xi} converges to the right-hand side of \eqref{eq:xi_ML} with $\zeta(K,K_{\rm a},K_{\rm a}') = n \ln\big(\frac{K}{K_{\rm a}'}\big) K_{\rm a}^{-1}\big(\frac{1}{K_{\rm a}'} - \frac{1}{K}\big)^{-1}$ for ML estimation of $\vect{r}{K}_{\rm a}$ and $\zeta(K,K_{\rm a},K_{\rm a}') = n\frac{K+K_{\rm a}'}{2 K_{\rm a}}$ for energy-based estimation of $\vect{r}{K}_{\rm a}$. Furthermore, the last term in $\tilde{p}$ given by~\eqref{eq:p0} vanishes and thus $\tilde{p} \to \bar{p}$. Finally, the lower bounds $\bar{\epsilon}_{\rm MD}$ and $\bar{\epsilon}_{\rm FA}$ follows by substituting the asymptotic values of $p_0$, $q_0$, $p_{0,0}$, $q_{0,0}$, $\xi(K_{\rm a},K_{\rm a}')$, and $\tilde{p}$ computed above into $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$, and by setting $\min\{p_t,q_t\}$ to zero for $t \ne 0$, and setting $\min\{p_{t,t'},q_{t,t'}\}$ to zero for $(t,t')\ne (0,0)$.



\section{Proof of Theorem~\ref{thm:TIN}} \label{app:TIN}

We first apply the same change of measure as in Appendix~\ref{sec:change_measure}
at a cost of adding the term $\tilde{p}$. Then $P_{\rm MD}$ and $P_{\rm FA}$ can be bounded as
\begin{IEEEeqnarray}{lCl}
	P_{\rm MD} 
	&\leq& \sum_{K_{\rm a} = \max\{K_\ell,1\}}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \!\frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}} \sum\limits_{j=1}^{K_{\rm a}} \mathbb{P}\left[\vect{r}{w}_j \notin \widehat{{\mathcal W}},K_{\rm a} \!\to\! K_{\rm a}^{\prime}\right] + \tilde{p} \\
	&\leq& \sum_{K_{\rm a} = \max\{K_\ell,1\}}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}} \sum\limits_{j=1}^{K_{\rm a}} \min\left\{\P[\vect{r}{w}_j \notin \widehat{{\mathcal W}}],\P[K_{\rm a}\to K_{\rm a}^{\prime}]\right\} + \tilde{p}, \label{eq:md_alt_0}\\
	P_{\rm FA} 
	&\leq& \sum_{K_{\rm a} =K_\ell}^{K_{u}} \sum_{K_{\rm a}^{\prime} =K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}^{\prime}} \sum\limits_{j=1}^{K_{\rm a}^{\prime}} \P[\widehat{\vect{r}{w}}_j \notin \mathcal{W},K_{\rm a}\to K_{\rm a}^{\prime} ] + \tilde{p}, \\
	&\leq& \sum_{K_{\rm a} =K_\ell}^{K_{u}} \sum_{K_{\rm a}^{\prime} =K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}^{\prime}} \sum\limits_{j=1}^{K_{\rm a}^{\prime}} \min\left\{\P[\widehat{\vect{r}{w}}_j \notin \mathcal{W}],\P[K_{\rm a}\to K_{\rm a}^{\prime} ]\right\} + \tilde{p}. \label{eq:fa_alt_0}
\end{IEEEeqnarray}

Given that the decoded list size is $K_{\rm a}'$, if ${K_{\rm a}'} < K_{\rm a}$, the decoder commits at least $K_{\rm a} - {K_{\rm a}'}$ \glspl{MD}. On the contrary, if $K_{\rm a}' > K_{\rm a}$, the decoder commits at least ${K_{\rm a}'} - K_{\rm a}$ \glspl{FA}. We assume \gls{wlog} that the last $({K}_{\rm a} - {K_{\rm a}'})^+$ transmitted codewords are initially misdetected due to insufficient decoded list size, and that the last $({K_{\rm a}'}-{K}_{\rm a})^+$ decoded codewords are initially false-alarmed  due to excessive decoded list size. Then $\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big] = 1$, $\forall j \in [\min\{K_{\rm a},K_{\rm a}'\} + 1: K_{\rm a}]$, and $\P[\widehat{\vect{r}{w}}_j \notin \mathcal{W}] = 1$, $\forall j\in [\min\{K_{\rm a},K_{\rm a}'\} + 1: K_{\rm a}']$. As a consequence, we can write \eqref{eq:md_alt_0} and \eqref{eq:fa_alt_0} as
\begin{align}
	P_{\rm MD} &\leq \sum_{K_{\rm a} =\max\{K_\ell,1\}}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}} \Biggl( (K_{\rm a}-K_{\rm a}^{\prime})^+ \P[K_{\rm a}\to K_{\rm a}^{\prime}]  \notag \\
	&\qquad + \sum\limits_{j=1}^{\min\{K_{\rm a},K_{\rm a}^{\prime}\}} \!\!\min\left\{\P[\vect{r}{w}_j \notin \widehat{{\mathcal W}}],\P[K_{\rm a}\to K_{\rm a}^{\prime}]\right\}\Biggr) + \tilde{p}, \label{eq:md_alt2_0}\\
	P_{\rm FA} &\leq \sum_{K_{\rm a} =K_\ell}^{K_{u}} \sum_{K_{\rm a}^{\prime} = K_\ell}^{K_{u}} \frac{P_{\vect{r}{K}_{\rm a}}(K_{\rm a})}{K_{\rm a}^{\prime}} \Biggl((K_{\rm a}^{\prime}-K_{\rm a})^+\P[K_{\rm a}\to K_{\rm a}^{\prime}]  \notag \\
	&\qquad + \sum\limits_{j=1}^{\min\{K_{\rm a},K_{\rm a}^{\prime}\}} \min\left\{\P[\widehat{\vect{r}{w}}_j \notin {{\mathcal W}}],\P[K_{\rm a}\to K_{\rm a}^{\prime}]\right\}\Biggr) + \tilde{p}.\label{eq:fa_alt2_0}
\end{align}
We proceed to bound the probabilities $\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big]$ and $\P[\widehat{\vect{r}{w}}_j \notin \widetilde{\mathcal{W}}]$ for $j\in [\min\{K_{\rm a},K_{\rm a}'\}]$.

\subsubsection{Bound on $\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big]$ for $j\in [\min\{K_{\rm a},K_{\rm a}'\}]$}
The event $\vect{r}{w}_j \notin \widehat{{\mathcal W}}$ 
implies that at least one codeword that was not transmitted is closer to $\rvVec{y}$ than $\vect{c}_{\vect{r}{w}_j}$. 
Therefore, for a given codebook $\{\vect{c}_1,\dots,\vect{c}_M\}$, $\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big]$ can be upper-bounded as
\begin{align}
	\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big]

	&\le \P[{\exists i \in [M] \setminus {\mathcal W} \colon \lVert\rvVec{y}-\vect{c}_{i}\rVert^2\leq \lVert\rvVec{y}-\vect{c}_{\vect{r}{w}_j}\rVert^2 }] \\
	&= \P[\bigcup\limits_{i \in [M] \setminus {\mathcal W}}\left\{\lVert\rvVec{y}-\vect{c}_{i}\rVert^2\leq \lVert\rvVec{y}-\vect{c}_{\vect{r}{w}_j}\rVert^2\right\}]. \label{eq:tmp2070_0}
\end{align}
By applying the union bound on~\eqref{eq:tmp2070_0}, using the fact that the codewords are independent and identically distributed, we conclude that 
\begin{align}
	\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big] &\le \E_{\rvVec{y}, \rvVec{c}}\left[ \min\left\{1, (M-K_{\rm a}) \P[\lVert\rvVec{y}-\tilde{\rvVec{c}}\rVert^2\leq \lVert\rvVec{y}-\rvVec{c}\rVert^2 \,\vert\, \rvVec{y}, \rvVec{c}]  \right\}\right],
\end{align}
where $\{\rvVec{y}, \rvVec{c}, \tilde{\rvVec{c}}\}$ has the same joint distribution as $\{\rvVec{y}, \vect{c}_{\vect{r}{w}_j}, \vect{c}_i\}$, $i \in [M] \setminus {\mathcal W}$. 
Next, by applying the Chernoff bound and proceeding as in~\cite[App.~A]{Ostman20}, we obtain the following RCUs bound~\cite[Th. 16]{Polyanskiy2010} for every $s>0$:
\begin{align} \label{eq:tmp2154_0}
	\P[\vect{r}{w}_j \notin \widehat{{\mathcal W}}] \le \E[ \min\left\{1, \exp\bigg(\ln(M-K_{\rm a}) - \sum\limits_{i=1}^n  \imath_s(\vect{r}{x}_{i};\vect{r}{y}_i)\bigg)\right\}]
\end{align}
with $\imath_s(x;y)$ given by~\eqref{eq:gen_infor_den} and $\{\vect{r}{x}_i,\vect{r}{y}_i\}$ defined in Theorem~\ref{thm:TIN}. Finally, by observing that, for every
positive random variable $\vect{r}{v}$, it holds that $\E[\min\{1, \vect{r}{v}\}] =
\P[\vect{r}{v} \ge \vect{r}{u}]$ where $\vect{r}{u}$ is uniformly distributed on $[0,1]$, we obtain that the right-hand side of~\eqref{eq:tmp2154_0} is given by $\eta_s$ defined in~\eqref{eq:eta_s}.

\subsubsection{Bound on $\P[\widehat{\vect{r}{w}}_j \notin \widetilde{{\mathcal W}}]$ for $j\in [\min\{K_{\rm a},K_{\rm a}'\}]$}
The event $\widehat{\vect{r}{w}}_j \notin \widetilde{{\mathcal W}} = \{\vect{r}{w}_1,\dots,\vect{r}{w}_{K_{\rm a}}\}$ implies that $\widehat{\vect{r}{w}}_j$ is closer to $\rvVec{y}$ than at least one transmitted codeword.
In this case, we assume \gls{wlog} that $\|\rvVec{y} - \vect{c}_{\widehat{\vect{r}{w}}_j}\|^2 \le \|\rvVec{y} - \vect{c}_{\vect{r}{w}_1}\|^2$. It follows that
\begin{align}
	\P[\widehat{\vect{r}{w}}_j \notin \widetilde{{\mathcal W}}] 

	&\le \P[\bigcup_{\widehat{\vect{r}{w}}_j \in [M] \setminus {\mathcal W}}  \{\|\rvVec{y} - \vect{c}_{\widehat{\vect{r}{w}}_j}\|^2 \le \|\rvVec{y} - \vect{c}_{\vect{r}{w}_1}\|^2\} ]. \label{eq:tmp2098_0}
\end{align}
Next, by applying the union bound,
 then applying the Chernoff bound and proceeding as in \cite[App.~A]{Ostman20}, we deduce that $\P[\widehat{\vect{r}{w}}_j \notin \widetilde{{\mathcal W}}]$ is upper-bounded by the right-hand side of \eqref{eq:tmp2154_0}, which can be expressed as $\eta_s$ defined in~\eqref{eq:eta_s}.

\vspace{.2cm}
Furthermore, the probability $\P[K_{\rm a}\!\to\! K_{\rm a}^{\prime}]$ can be upper-bounded by $\xi(K_{\rm a},K_{\rm a}')$ as in Appendix~\ref{sec:bound_xi}. By substituting the bounds on $\P\big[\vect{r}{w}_j \notin \widehat{{\mathcal W}}\big]$, $\P[\widehat{\vect{r}{w}}_j \notin \widetilde{{\mathcal W}}]$, and $\P[K_{\rm a}\to K_{\rm a}^{\prime}]$ into~\eqref{eq:md_alt2_0} and~\eqref{eq:fa_alt2_0}, we deduce that $P_{\rm MD}$ and $P_{\rm FA}$, averaged over the Gaussian codebook ensemble, are upper-bounded by $\epsilon_{\rm MD}$ and $\epsilon_{\rm FA}$ given in~\eqref{eq:md_TIN} and \eqref{eq:fa_TIN}, respectively. Finally, by proceeding as in \cite[Th.~19]{Polyanskiy2011feedback}, one can show that there exists a randomized coding strategy that achieves \eqref{eq:eps_MD} and \eqref{eq:eps_FA} simultaneously, and involves time-sharing among at most three deterministic codes.

\bibliographystyle{IEEEtran}

\section*{Solutions}%
}






\IfFileExists{MinionPro.sty}{
}{
}





