Random Access Channel Coding in the Finite Blocklength Regime
Recep Can Yavas Victoria Kostina Michelle Effros
cs.IT math.IT 94A24 E.4

Moral attitudes and willingness to induce cognitive enhancement and repair with brain stimulation
    John D. Medaglia^1,2∗, David Yaden^3, Chelsea Helion^4, Madeline Haslam^5

	^1Department of Psychology, Drexel University

	Philadelphia, PA, 19104, USA

	^2Department of Neurology, Perelman School of Medicine, University of Pennsylvania

	Philadelphia, PA, 19104, USA

	^3Department of Psychology, University of Pennsylvania

	Philadelphia, PA, 19104, USA
	
	^4Department of Psychology, Columbia University

	Philadelphia, PA, 19104, USA
	
	^5Department of Psychology, Washington College

	Chestertown, MD, 21620, USA
	
∗ To whom correspondence should be addressed: john.d.medaglia@drexel.edu

	
    
========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. As in the model recently introduced  by Polyanskiy for the Multiple Access Channel (MAC) with a fixed, known number of transmitters, the channel is assumed to be invariant to permutations on its inputs, and all active transmitters employ identical encoders. Unlike the Polyanskiy model, in the proposed scenario, neither the transmitters nor the receiver knows which transmitters are active. We refer to this agnostic communication setup as the Random Access Channel (RAC). Scheduled feedback of a finite number of bits is used to synchronize the transmitters. The decoder is tasked with determining from the channel output the number of active transmitters, k, and their messages but not which transmitter sent which message. The decoding procedure occurs at a time n_t depending on the decoder's estimate, t, of the number of active transmitters, k, thereby achieving a rate that varies with the number of active transmitters. Single-bit feedback at each time n_i, i ≤ t, enables all transmitters to determine the end of one coding epoch and the start of the next. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2^k - 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.



Channel coding, random access channel, finite blocklength regime, achievability, second-order asymptotics, rateless codes.



§ INTRODUCTION

é à Access points like WiFi hot spots and cellular base stations are, for wireless devices, the gateway to the
network. Unfortunately, access points
are also the network's most critical bottleneck. 
As more kinds of devices become network-reliant, both the
number of communicating devices and the diversity of their communication needs grow.
Little is known  
about how to code under high variation in the number and variety of communicators. 

Multiple-transmitter single-receiver channels are well understood in information theory when the number and identities of transmitters are fixed and known. Unfortunately, even in this known-transmitter regime, information-theoretic solutions are too complex to implement. As a result, orthogonalization methods, such as TDMA, FDMA, and orthogonal CDMA, are used instead. Orthogonalization strategies simplify coding by allocating resources (e.g., time slots) among the transmitters, but applying such methods to discrete memoryless MACs can at best attain a sum-rate equal to the single-transmitter capacity of the channel, which is often significantly smaller than the maximal
multi-transmitter sum-rate.

Most random access protocols currently in use rely on collision avoidance, which cannot surpass the single-transmitter capacity of the channel and may be significantly worse since the unknown transmitter set makes it difficult to schedule or coordinate among transmitters. Collision avoidance is achieved through variations of the legacy (slotted) ALOHA and carrier sense multiple access (CSMA) algorithms.  
ALOHA, which uses random transmission times and back-off schedules, achieves only about 37% of the single-transmitter capacity of the channel <cit.>.  In CSMA, each transmitter tries to avoid collisions by verifying the absence of other traffic before starting a transmission over the shared channel; when collisions do occur, 
all transmissions are aborted, and a jamming signal is sent to ensure that all transmitters are aware of the collision. The procedure starts again at a random time, which again introduces inefficiencies. The state of the art in random access coding is “treating interference as noise,” which is part of newer CDMA-based standards. While this strategy can deal with random access better than ALOHA, it is still far inferior to the theoretical limits.

Even from a purely theoretical perspective, a satisfactory solution to random access  remains to be found. The MAC model in which a fixed number, k, out of the total available K transmitters are active was studied by
D'yachkov and Rykov <cit.> and Mathys <cit.> for zero-error coding on a noiseless adder MAC, and by Bassalygo and Pinsker <cit.> for an asynchronous model in which the information is considered erased if more than one transmitter is active at a time. See <cit.> for a more detailed history.


Two-layer MAC decoders, with outer layer codes that work to remove channel noise and inner layer codes that work to resolve conflicts, are proposed in <cit.>. Like the codes in <cit.>, 
the codes in <cit.> are designed for a predetermined number of transmitters, k; 
it is not clear how robust they are to randomness in the transmitters' arrivals and departures. In <cit.>, Minero et al. study a random access model in which the receiver knows the transmitter activity pattern, and the transmitters opportunistically send data at the highest possible rate. The receiver recovers only a portion of the messages sent, depending on the current level of activity in the channel. 



 §.§ Our Contributions and Related Works

This paper poses the question of whether it is possible, in a scenario where no one knows how many transmitters are active, for the receiver to almost always recover the messages sent by all active transmitters. Surprisingly, we find that not only is reliable decoding possible in this regime, but, for the class of permutation-invariant channels considered in <cit.>, our proposed RAC code performs as well in its capacity and dispersion terms as the best-known code for a MAC with the transmitter activity known a priori <cit.>. 
Since the capacity region of a MAC varies with the number of transmitters, 
it is tempting to believe that the transmitters of a random access system must somehow vary their codebook size 
in order to match their transmission rate to the capacity region of the MAC in operation. 
Instead, we here allow the decoder to vary its decoding time 
depending on the observed channel output—thereby adjusting the rate at which each transmitter communicates 
by changing not the size but the blocklength of each transmitter's codebook.

Codes that can accommodate variable decoding times are called rateless codes. Rateless codes originate with the work of Burnashev <cit.>, who computed the error exponent of variable-length coding over a known point-to-point channel. Polyanskiy et al. <cit.> provide a dispersion-style analysis of the same scenario.  A practical implementation of rateless codes for an erasure channel with an unknown erasure probability appears in <cit.>. An analysis of rateless coding over an unknown binary symmetric channel appears in <cit.> and is extended to an arbitrary discrete memoryless channel in <cit.> using a decoder that tracks Goppa's empirical mutual information and decodes once that quantity passes a threshold. In <cit.>, Jeffrey's prior is used to weight unknown channels. A rateless code for noiseless random access communication is described in <cit.>; each user transmits replicas of its message in multiple time slots, possibly colliding with the messages of other transmitters. At the end of each time slot, the decoder attempts to apply successive interference cancellation starting with the messages received without collision and subsequently removing the associated interference from the time slots in which replicas are transmitted. The decoder then decides whether to terminate an epoch or to ask the transmitters to send more replicas. 





Unlike the codes described in <cit.>, which allow truly arbitrary decoding times,  in this paper we allow decoding only at a predetermined list of possible times n_0, n_1, n_2, …. This strategy both eases practical implementation and reduces feedback. In particular, the schemes in<cit.> transmit a single-bit acknowledgment message from the decoder to the encoder(s) once the decoder completes its decoding process. Because the decoding time is random, this so-called “single-bit” feedback forces the transmitter(s) to listen to the channel constantly, at every time step trying to discern whether or not a transmission was received. This either requires full-duplex devices or doubles the effective blocklength and can be quite expensive.  Thus while the receiver technically sends only “one bit” of feedback, the transmitters receive one bit of feedback (with the alphabet {}) in every time step, giving a feedback rate of 1 bit per channel use rather than a total of 1 bit.  In our framework, feedback bits are sent only at times n_0 <n_1 < ⋯ < n_t, where each n_i is the pre-determined decoding time used if the receiver believes that i transmitters are active. Thus the transmitters must listen only at a sparse collection of time steps. The total number of feedback bits equals one plus the receiver's estimate of the number of transmitters, giving a feedback rate approaching 0 bits per channel use as the blocklength grows. 

In the central portion of this paper, we view the random access channel as a collection of all possible MACs that might arise as a result of the transmitter activity pattern. Barring the intricacies of multiuser decoding, the model that views an unknown channel as a collection of possible channels without assigning an a priori probability to each is known as the compound channel model <cit.>. In the context of single-transmitter compound channels, it is known that if the decoding time is fixed, the transmission rate cannot exceed the capacity of the weakest channel from the collection <cit.>, though the dispersion may be better (smaller) <cit.>. With feedback and a variable decoding time, one can do much better <cit.>.  


In <cit.>, Polyanskiy argues for removing the transmitter identification task from the physical layer encoding and decoding procedures of a MAC. As he points out, such a scenario was previously discussed by Berger <cit.> in the context of conflict resolution. Polyanskiy further suggests studying MACs whose conditional channel output distributions are insensitive to input permutations.  For such channels, if all transmitters use the same codebook, then the receiver can at best hope to recover the messages sent without recovering who transmitted which message (the transmitter identity). In some networks the transmitter identification task can be insignificant. For example, in some sensor networks, we might be interested in the collected measurements but indifferent to the identities of the collecting sensors. In scenarios where transmitter identity is required, it can be included in the payload.

In sec:raccode, we propose a code for a random access communication channel model built from a family of permutation-invariant MACs. Our code employs identical encoders at all transmitters and identity-blind decoding at the receiver. Although not critical for the feasibility of our approach, these assumptions lead to a number of pleasing simplifications of both our scheme and its analysis. For example, using identical encoders at all transmitters simplifies design and implementation. Further, the collection of MACs comprising our compound RAC model can be parameterized by the number of active transmitters rather than by the full transmitter activity pattern. If the maximum number of transmitters is finite, the analysis of identity-blind decoding differs little from traditional analyses that use independent realizations of a random codebook at each transmitter. We elaborate on this small difference in sec:transiden, where we discuss an extension of our strategy to allow for transmitter identity decoding. 

We provide a second-order analysis of the rate universally achieved by our multiuser scheme over all transmitter activity patterns,  taking into account the possibility that the decoder may misdetect the current activity pattern and decode for the wrong channel.  Leveraging our observation that for a symmetric MAC, the fair rate point is not a corner point of the capacity region, we are able to show that a single-threshold decoding rule attains the fair rate point. This differs significantly from traditional MAC analyses, which use 2^k-1 simultaneous threshold rules.  In the context of a MAC with a known number of transmitters, second-order analyses of multiple-threshold decoding rules are given in <cit.> (finite alphabet MAC) and in <cit.> (Gaussian MAC). A non-asymptotic analysis of variable-length coding with “single-bit" feedback over a (known) Gaussian MAC appears in <cit.>. 

Other relevant recent works on the MAC include the following. 
To account for massive numbers of transmitters, in <cit.>, Chen and Guo introduce a notion of capacity for the multiple access scenario in which the maximal number of transmitters grows with the blocklength and an unknown subset of transmitters is active at a given time. They show that time sharing, which achieves the conventional MAC capacity, is inadequate to achieve capacity in that regime. In <cit.>, Sarwate and Gastpar show that rate-0 feedback, such as the feedback in our approach, does not increase the capacity of the discrete memoryless MAC. In compound MACs, limited feedback can increase capacity. For example, one strategy uses a simple training phase to estimate the channel state and employs feedback to send the state estimate to the transmitter. Such schemes cannot increase the capacity beyond the rate achievable when the state is known to the encoders and the decoder <cit.>.

The sparse recovery problem is identical to a special case of the RAC problem in which each transmitter sends only its “signature" to the receiver. Here, the decoder's only task is to determine who is active. Active transmitters in this variant of the RAC problem may correspond to defective items or positive test outcomes in the sparse recovery problem, and successful decoding is identified with successfully detecting the set of defective or confirmed-positive elements. A group testing problem in which an unknown subset of k defective items out of K items total is observed through an OR MAC, is studied in <cit.>; this problem is a special case of the sparse recovery problem. In these works, the decoder reaches a conclusion about tested items at a fixed blocklength n. Atia and Saligrama <cit.> consider a noiseless group testing scenario in which the number of transmitted elements, k, does not grow with the total number of elements, K, showing that the smallest possible number of measurements needed to detect the defective items is O(k logK/k). In in <cit.>, Scarlett and Cevher extend this result to the scenario where k scales as O(K^θ) for θ∈ (0, 1). In <cit.>, Scarlett and Cevher derive the information-theoretic limits of the exact and partial support recovery problems for general probabilistic models, where exact recovery refers to detecting all k defective items, and partial recovery refers to detecting at least s out of k defective items. While we consider a nonvanishing average error probability and operate in the central limit theorem regime, <cit.> assume vanishing average error probability and operate in the large deviations regime. The main difference between the decoder designs in  <cit.> and our decoder design is that  <cit.> use 2^k - 1 simultaneous information density threshold tests at a single blocklength n, while our decoder uses a single information density threshold test at multiple decoding times, allowing successful detection with a computationally less complex decoder even when the number of active transmitters to be detected is unknown. 










 §.§ Paper Organization


Our system model and proposed communication strategy are laid out in sec:setup. The main result, showing that for a nontrivial class of channels our proposed RAC code performs as well in terms of capacity and dispersion as the best-known code for a MAC with the transmitter activity known a priori, is presented in sec:main. The proofs are presented in sec:raccode. sec:furtherDis includes discussions of the effect of using maximum likelihood decoding, the choice of an input distribution in the random code design, the difficulties in proving a converse, an extension of our strategy that enables transmitter identity decoding, and performance bounds under the per-user error probability criterion. Interestingly, the problem of decoding for k ≥ 1 unknown transmitters is substantially different from the problem of detecting whether there are any active transmitters at all. In sec:analysis_0test, we employ universal hypothesis testing to solve the latter problem. sec:summary concludes the paper with a discussion of our results and their implications.






§ PROBLEM SETUP

For any positive integers i,j, let [i]={1,…,i} and
[i:j]={i,…,j}, where [i:j]=∅ when i>j.
We denote an n dimensional vector by x^n = (x_1, …, x_n). When the dimension of a vector x^n is clear from the context, we denote x^n by . All-zero and all-one vectors are denoted by 0 and 1, respectively. For a collection of length-n vectors x_1^n, …, x_K^n and any subset 𝒞⊆ [K], we denote the corresponding sub-collection of vectors by x_𝒞^n = (x_c^n  c ∈𝒞). For collection of vectors x_𝒞^n and index i ∈ [n], x_𝒞, i denotes the collection of scalars obtained by taking i-th coordinate from each vector in x_𝒞^n. For any vectors x_𝒞 and y_𝒞, we write x_𝒞≤ y_𝒞 if x_c ≤ y_c for all c ∈𝒞, x_𝒞π= y_𝒞 if there exists a permutation π of y_𝒞 such that x_𝒞 = π(y_𝒞), and 
x_𝒞π≠ y_𝒞 if x_𝒞≠π(y_𝒞) for all permutations π of y_𝒞. For any set 𝒜 and integer k ≤ |𝒜|, 𝒜k = {ℬℬ⊆𝒜, |ℬ| = k }. For a random variable X, we write X ∼ P_X to specify that X is distributed according to distribution P_X. We use Q(·) to denote the Gaussian complementary cumulative distribution function, giving Q(x) ≜1/√(2π)∫_x^∞exp{-u^2/2} du.
We employ the standard o(·) and O(·) notations, giving f(n) = o(g(n)) if lim_n →∞|f(n)/g(n)| = 0 and f(n) = O(g(n)) if lim sup_n →∞|f(n)/g(n)| < ∞.

A stationary, memoryless, symmetric, random access channel (henceforth called simply a RAC)
is a memoryless channel with one receiver and an unknown number of
transmitters. It is described by a family of stationary, memoryless MACs

    {(^k, P_Y_k | X_[k](y_k|x_[k]),
    _k)}_k=0^K ,

each indexed by a number of transmitters, k; the maximal number of transmitters is K ≤∞. When k = 0, no transmitters are active; we discuss this case separately below.
For k ≥ 1, the k-transmitter MAC has input alphabet ^k, output alphabet _k,
and conditional distribution P_Y_k | X_[k].
When k transmitters are active, the RAC output is Y=Y_k. The input and output alphabets 𝒳 and 𝒴_k can be abstract.



 §.§ Assumptions on the Channel

We assume that the impact of a channel input
on the channel output is independent of the transmitter from which it comes; therefore,
each channel in (<ref>)
is assumed to be permutation-invariant <cit.>, giving

    P_Y_k | X_[k](y_k | x_[k]) = P_Y_k | X_[k](y_k | x̂_[k])

for all x̂_[k]π= x_[k] and y_k ∈𝒴_k, k ∈ [K].
We further assume that for any s<k,
an s-transmitter MAC is physically identical to a k-transmitter MAC
operated with s active and k-s silent transmitters. At each time step of the communication period, each silent transmitter transmits a silence symbol, here denoted by 0∈. This reducibility constraint gives 

    P_Y_s | X_[s](y|x_[s]) = P_Y_k
    | X_[k](y|x_[s],0^k-s)

for all s < k, x_[s]∈_[s], and y∈_s.
An immediate consequence of reducibility is that _s
⊆_k for any s < k. Another consequence is that when there are no active transmitters, the MAC (^0, P_Y_0 | X_[0](y|x_[0]), _0 ) satisfies 𝒳^0 = {0} and P_Y_0 | X_[0](y|x_[0]) = P_Y_k | X_[k](y|0^k) for all k.



 §.§ RAC Communication Strategy

We here propose a new RAC communication strategy.
In the proposed strategy, communication occurs in epochs, with each epoch beginning in the time step following the previous epoch's end. Each epoch ends when the receiver's scheduled broadcast to all transmitters indicates a decoding event, signaling that the prior transmission can stop and a new transmission can begin. 
At this point, each transmitter
decides whether to be active or silent in the new epoch;
the decision is binding for the length of the epoch,
meaning that a transmitter must either actively transmit for all time steps
in the epoch
or remain silent for the same period.
Thus, while
the total number of transmitters, K, is potentially unlimited and can change arbitrarily from one epoch to the next, the number of
active transmitters, k, remains constant throughout each epoch.

Each active transmitter uses the epoch to describe a message W from the alphabet [M]. When the active transmitters are [k], the messages are W_[k]∈[M]^k, where the messages W_1, …, W_k of different transmitters are independent and uniformly distributed. The proposed strategy fixes the potential decoding times n_0 < n_1 < ⋯ < n_K.[We focus the exposition on the scenario where the decoding blocklengths are ordered both for simplicity and because a particular choice of ordered blocklengths emerges as optimal within our architecture (see (<ref>) in sec:achproof, below).]
The receiver chooses to end the epoch (without decoding) at time n_0 if it believes at time n_0 that no transmitters are active and chooses to end the epoch and decode at time n_t if it believes at time n_t that the number of active transmitters is t. The transmitters are informed of the decoder's decision through a single-bit feedback Z_s at each time n_s with s∈{0, 1, …, t}; here Z_s=0 for all s<t and Z_t=1, with “1” signaling the end of one epoch and the beginning of the next. Since the blocklength for a given epoch is the decoding time chosen by the receiver, the result is a rateless code. As we show in Section <ref> below, with an
appropriately designed decoding rule, correct decoding is performed at time n_k with high probability.

It is important to stress that in this domain
each transmitter knows nothing about the set of active
transmitters 𝒜⊂ℕ beyond its own membership
and what it learns from the receiver's feedback,
and the receiver knows nothing about 𝒜 beyond what it learns
from the channel output Y; we call this agnostic random access.
In addition, since designing a different encoder
for each transmitter is expensive from the perspective
of both code design and code operation, as in <cit.>,
we assume through most of this paper that every transmitter employs the same encoder; we call this identical encoding. Under the assumptions of permutation-invariance
and identical encoding,
what the transmitters and receiver can learn about  is quite limited.
Together, these properties imply that the decoder can at best distinguish
which messages were transmitted rather than by whom they were sent. 
In practice, transmitter identity could be included
in the header of each log M-bit message
or at some other layer of the stack;
transmitter identity is not, however, handled by the RAC code.
Instead, since the channel output statistics depend on
the dimension of the channel input
but not the identity of the active transmitters,
the receiver's task is to decode the messages transmitted
but not the identities of their senders.
We therefore assume without loss of generality
that |𝒜|=k implies 𝒜=[k].
Thus the family of k-transmitter MACs in (<ref>)  fully describes the behavior of a RAC.[sec:transiden treats a variant of our RAC communication strategy that enables decoding of transmitter identity. Mathematically, the variants are quite similar. ]






 §.§ Code Definition












The following
definition formalizes our code.

For any number of messages M, ordered blocklengths n_0 < n_1 < ⋯ < n_K, and error probabilities ϵ_0, …, ϵ_K, an (M, { (n_k, ϵ_k) }_k = 0^K ) RAC code comprises a (rateless) encoding function

    𝖿 𝒰× [M] →𝒳^n_K

and a collection of decoding functions

    𝗀_k  𝒰×𝒴_k^n_k→ [M]^k ∪{𝖾},    k = 0, 1, …, K,


where 𝖾 denotes the erasure symbol, which is the decoder's output when it is not ready to decode. At the start of each epoch, a common randomness random variable U ∈𝒰, with U ∼ P_U, is generated independently of the transmitter activity and revealed to the transmitters and the receiver,

thereby  initializing the encoders and the decoder. If k transmitters are active, then with probability at least 1 - ϵ_k, the k messages are correctly decoded
at time n_k. That is,[Recall that π= and π≠ denote equality and inequality up to a permutation.]

    1/M^k   ∑_w_[k]∈ [M]^kℙ[𝗀_k(U, Y_k^n_k) π≠ w_[k]⋃
       .⋃_t = 0^k-1𝗀_t(U, Y_k^n_t) ≠ | . W_[k] = w_[k]] ≤ϵ_k,

where W_[k] are the independent and equiprobable messages of transmitters [k], and the given probability is calculated using the conditional distribution P_Y_k^n_k | X_[k]^n_k = P_Y_k | X_[k]^n_k; here X_i^n_k = 𝖿(U, W_i)^n_k, i = 1, …, k. At time n_s, the decoder outputs the erasure symbol “𝖾" if it decides that the number of active transmitters is not s.
If k = 0 transmitters are active, the unique message “", denoted [M]^0 ≜{} to simplify the notation, is decoded at time n_0 with probability at least 1-ϵ_0. That is,

    𝗀_0(U, Y_0^n_0) ≠ | W_[0] = ≤ϵ_0.



In Definition <ref>, we index the family of possible codes by the elements of some set 𝒰 and include u ∈𝒰 as an argument for both the RAC encoder and the RAC decoder. We then represent encoding as the application of a code indexed by some random variable U ∈𝒰 chosen independently for each new epoch. Deterministic codes are represented under this code definition by setting the distribution on U as U = u_0 = 1 for some u_0 ∈𝒰. 
In practice, we can implement a RAC code with random code choice U using common randomness. Common randomness available to the transmitters and the receiver allows all nodes to choose the same random variable U to specify a new codebook in each epoch. Operationally, this common randomness can be implemented by allowing the receiver to choose random instance U at the start of each epoch and to broadcast that value to the transmitters just after the feedback bit that ends the previous epoch. Alternatively, all communicators can use synchronized pseudo-random number generators. Broadcasting the value of U increases the epoch-ending feedback from 1 bit to ⌈log |𝒰|⌉ + 1 bits; thm:caratheodory shows that |𝒰| ≤ K + 1 suffices to achieve the optimal performance. 

In sec:raccode, we employ a general random coding argument to show that a given error vector (ϵ_0, …, ϵ_K) is achievable when averaged over the ensemble of codes. Unfortunately, this traditional approach does not show the existence of a deterministic RAC code (i.e., a code with |𝒰| = 1) that achieves the given error vector (ϵ_0, …, ϵ_K). The challenge here is that our proof showing that the random code's expected error probability meets each of the K + 1 error constraints does not suffice to show that any of the codes in the ensemble meets all of our error constraints simultaneously. A similar issue arises in <cit.>. For example, in <cit.>, a variable-length feedback code is designed with the aim of achieving average error probability no greater than ϵ and expected decoding time no greater than ℓ. To design a single code satisfying both constraints, <cit.> relies on common randomness. Similarly, <cit.> describes a variable-length feedback code designed to satisfy an error exponent criterion for every channel in a continuum of binary symmetric or Z channels. Their proof that a single, deterministic code can simultaneously satisfy this continuum of constraints exploits the ordering among the channels in the given family. While channel symmetry can sometimes be leveraged to show the existence of a deterministic code <cit.>, the symmetries in a RAC are quite different from those in point-to-point channels. We leave the question of whether a single-code solution exists for the RAC 
to future work.


The code model introduced in Definition <ref> employs identical encoding in addition to common randomness. Under identical encoding, each transmitter uses the same encoder, 𝖿, to form a codeword of length n_K. That codeword is fed into the channel symbol by symbol. According to Definition <ref>, if k transmitters are active, then with probability at least 1 - ϵ_k, the decoder recovers the transmitted messages correctly after observing the first n_k channel outputs. As noted previously, the decoder 𝗀_k does not attempt to recover transmitter identity; successful decoding means that the list of messages in the decoder output coincides with the list of messages sent. The error event defined in Definition <ref> differs from the one in <cit.>. Our definition (<ref>) requires that all transmitted messages are decoded correctly. In contrast, <cit.> bounds a per-user probability of error (PUPE),
which measures the fraction of transmitted messages that are missing from the list of decoded messages. In sec:PUPE, we discuss the error probability for our code under the PUPE criterion.




 §.§ Information Density Definitions

The following definitions are useful for the discussion that follows.
When k transmitters are active, the input distribution is P_X_[k], and the marginal output distribution is P_Y_k.
The information density and conditional information density are defined[We here employ notation for discrete alphabets. In the general case, it can be replaced by the logarithm of the Radon-Nikodym derivative, giving 
_k(x_𝒜;y_k) = logdP_Y_k| X_𝒜2.5pt = x_𝒜2.5pt/dP_Y_k(y_k).] as

    _k(x_𝒜;y_k)    ≜logP_Y_k|X_𝒜(y_k|x_𝒜)/P_Y_k(y_k)
    _k(x_𝒜 ; y_k | x_ℬ)    ≜logP_Y_k|X_𝒜, X_ℬ(y_k| x_𝒜,x_ℬ)/P_Y_k | X_B(y_k| x_ℬ)

for any 𝒜,ℬ⊆ [k], x_𝒜∈𝒳_𝒜, x_ℬ∈𝒳_ℬ, and y_k ∈𝒴_k;
here _k(x_𝒜 ; y_k | x_ℬ) ≜_k(x_𝒜 ; y_k) when ℬ=∅ and _k(x_𝒜 ; y_k|x_ℬ) ≜ 0 when y_k ∉𝒴_k or 𝒜 = ∅.
The corresponding mutual informations are

    I_k(X_𝒜 ; Y_k)    ≜𝔼[_k(X_𝒜 ; Y_k)]  
    
    I_k(X_𝒜 ; Y_k | X_ℬ)    ≜𝔼[_k(X_𝒜 ; Y_k | X_ℬ)].

Throughout the paper, we also denote for brevity

    I_k    ≜ I_k(X_[k]; Y_k)
    
     V_k    ≜_k(X_[k]; Y_k).

The multi-letter information density and conditional information densities are defined as

    _k(x_𝒜^n;y_k^n)    ≜logP_Y_k^n|X_𝒜^n(y_k^n|x_𝒜^n)/P_Y_k^n(y_k^n)
    _k(x_𝒜^n ; y_k^n | x_ℬ^n)    ≜logP_Y_k^n|X_𝒜^n, X_ℬ^n(y_k^n| x_𝒜^n,x_ℬ^n)/P_Y_k^n | X_ℬ^n(y_k^n| x_ℬ^n).






 §.§ Assumptions on the Input Distribution
 
To ensure the existence of codes satisfying the error constraints in
Definition <ref>, we assume that there exists a P_X such that when X_1, X_2, …, X_K are distributed i.i.d. P_X, then the conditions in  (<ref>)–(<ref>) below are satisfied. 

The friendliness assumption states that for all s ≤ k ≤ K,

    I_k(X_[s]; Y_k | X_[s+1:k] =  0^k-s)
    ≥ I_k(X_[s]; Y_k | X_[s+1:k]).

Friendliness implies that by remaining silent, inactive transmitters enable communication by the active transmitters at rates at least as large as those achievable if the inactive transmitters had actively participated and their codewords were known to the receiver.

The interference assumption states that for any s and t,
X_[s] and X_[s+1:t] are conditionally dependent given Y_k, giving 

    P_X_[t] | Y_k≠ P_X_[s]|Y_k  P_X_[s+1:t]|Y_k  ∀  1 ≤ s < t ≤ k,  ∀ k.

Assumption (<ref>) eliminates trivial RACs in which transmitters do not interfere.

In order for the decoder to be able to distinguish the time-n_0 output Y_0^n_0 that results when no transmitters are active from the time-n_0 output Y_k^n_0 that results when k ≥ 1 transmitters are active, we assume that there exists a δ_0 > 0 such that the output distributions satisfy

    sup_y ∈𝒴_K| F_k(y) - F_0(y) |≥δ_0   for all  k ∈ [K],

where F_k(y) denotes the cumulative distribution function (CDF) of P_Y_k for k ∈{0, …, K}.[Although the CDF is defined for real-valued random variables, i.e., 𝒴_k ⊆𝒴_K ⊆ℝ is required, it can be generalized to abstract alphabets by introducing a partial order ≤ on the set 𝒴_K. Then F_k(y) ≜Y_k ≤ y.] The measure of discrepancy between distributions on the left-hand side of (<ref>) is known as the Kolmogorov-Smirnov distance. The assumption in (<ref>) is only needed to detect the scenario when no transmitters are active; the remainder of the code functions proceed unhampered when (<ref>) fails. When K is finite, (<ref>) is equivalent to P_Y_0≠ P_Y_k for all k ∈ [K].

Finally, the moment assumptions 
 
    Var[_k(X_[k] ; Y_k) ]    > 0 
    [|_k(X_[k]; Y_k) - I_k(X_[k]; Y_k) |^3]    <∞

enable the second-order analysis presented in Theorem <ref>, below.

In the case when _t(X_[s] ; Y_k) > -∞ almost surely, we also require 

    Var[_t(X_[s] ; Y_k) ]    < ∞  ∀ s ≤ t ≤ k  .

Moment assumptions like (<ref>)–(<ref>) are common in the finite-blocklength literature, e.g.,  <cit.>. 

In the discussion that follows, we say that a channel satisfies our channel assumptions ((<ref>), (<ref>), (<ref>)–(<ref>)) if there exists an input distribution P_X under which those conditions are satisfied. All discrete memoryless channels (DMCs) satisfy finite second- and third-moment assumptions
(<ref>)–(<ref>) <cit.>, as do Gaussian noise channels. Common channel models from the literature typically satisfy a non-zero second-moment assumption (<ref>) as well.
Example channels that meet our channel assumptions ((<ref>), (<ref>), and (<ref>)–(<ref>)) include the Gaussian RAC, 

    Y_k = ∑_i = 1^k X_i  + Z,

where each X_i ∈ℝ operates under power constraint P and
Z ∼𝒩(0, N) for some N > 0, 
and the adder-erasure RAC <cit.>,

    Y_k =
    ∑_i = 1^k X_i,    w.p.  1 - δ
    𝖾   w.p. δ,

where X_i ∈{0, 1} and Y_k ∈{ 0, …, k}∪{𝖾}. In <cit.>, the adder-erasure RAC (<ref>) is used to model a scenario where a digital encoder and decoder communicate over an analog channel using a modulator and demodulator. The modulator converts the bits into analog signals; the channel output equals the sum of the transmitted signals plus random noise; the demodulator quantizes that output, declaring an erasure, 𝖾, if reliable quantization is not possible due to high noise. Thus, one can view the adder-erasure RAC as a discretization of the Gaussian RAC.

For the Gaussian RAC, _t(X_[s];Y_k)>-∞ almost surely, and (<ref>) is satisfied. For the adder-erasure RAC, _t(X_[s] ; Y_k) = -∞ for some channel realizations and user activity patterns, and (<ref>) is not required.

We conclude this section with a series of lemmas that describe the natural orderings possessed by RACs that satisfy our permutation-invariance, reducibility, friendliness, and interference constraints  ((<ref>), (<ref>), (<ref>), and  (<ref>)). These properties are key to the feasibility of the approach proposed in our achievability argument in sec:main. Proofs are relegated to app:proofs.

The first lemma shows that the quality of the channel for each active transmitter deteriorates as the number of active transmitters grows (even though the sum capacity may increase). 

 
Let X_1, X_2, …, X_k∼ i.i.d.  P_X. Under permutation-invariance (<ref>),  reducibility (<ref>), friendliness (<ref>), and interference (<ref>),

    I_k/k < I_s/s   k > s ≥ 1.



The second lemma shows that a similar relationship holds even when the number of transmitters is fixed.

Let X_1, X_2, …, X_k∼i.i.d. P_X. Under permutation-invariance (<ref>), reducibility (<ref>) and interference (<ref>), 

    1/k I_k(X_[k]; Y_k) < 1/s I_k(X_[s]; Y_k | X_[s+1:k])    k > s ≥ 1.


lem:mutualinfo ensures that the equal-rate point of the k-MAC lies on the sum-rate boundary and away from all the corner points of the rate region achieved with P_X. In their work on the group testing problem <cit.>, Malyutov and Mateev prove a non-strict version of (<ref>) for permutation-invariant channels (<ref>). They use this non-strict version of (<ref>) to conclude that their achievability and converse results in <cit.> coincide for permutation-invariant channels. Adding the reducibility (<ref>) and interference (<ref>) assumptions to the permutation-invariance assumption (<ref>) enables us to prove the strict inequality in lem:mutualinfo, which in turn enables the use of a single threshold rule at the decoder, as discussed in sec:raccode.

lemma:expectation compares the expected values of the information densities for different channels. 


Let X_1, X_2, …, X_k ∼i.i.d. P_X. If a RAC is permutation-invariant (<ref>), reducible (<ref>), friendly (<ref>), and exhibits interference (<ref>), then for any 1 ≤ s ≤ t < k,

    𝔼[_t(X_[s]; Y_k)] ≤ I_k(X_[s]; Y_k) < I_t(X_[s]; Y_t).



The orderings in lem:mutualinfofriendly–<ref> are used in bounding the performance of our agnostic random access code.



§ MAIN RESULT




 §.§ An Asymptotic Achievability Result

Our main result is the following bound on achievable rates for the RAC.
(Achievability) 
For any RAC 
    {(^k, P_Y_k | X_[k](y_k|x_[k]), _k)}_k=0^K
 satisfying (<ref>) and (<ref>), any K < ∞, and any fixed P_X satisfying (<ref>)–(<ref>), 
there exists an (M, {(n_k, ϵ_k) }_k = 0^K ) code provided that

    k log M ≤ n_k I_k - √(n_k V_k) Q^-1(ϵ_k) - 1/2log n_k + O(1)

for all k ∈ [K], 
and

    n_0 ≥ c_0 log n_1 + o(log n_1),

where c_0 is a known positive constant. The O(1) term in (<ref>) is constant with respect to n_1; it depends on the number of active transmitters, k, but not on the total number of transmitters, K.































The code in thm:ach assigns equal rates R_[k]=(R,…,R), R=log M/n_k, to all active transmitters. 
The sum-rate kR converges as O(1/√(n_k)) to I_k(X_[k]; Y_k)
for some input distribution P_X_[k](x_[k])=∏_i=1^kP_X(x_i) for all k. Note that
P_X is independent of the number of active transmitters, k. 
If the RAC is discrete and memoryless and a single P_X maximizes I_k(X_[k]; Y_k) for every k, then
the achievable rate in (<ref>) not only converges to the symmetrical rate point
on the capacity region of the MAC in operation but also achieves the best-known second-order term <cit.>[Note that we are comparing the RAC achievable rate with rate-0 feedback 
to the MAC capacity without feedback.  
Wagner et al. <cit.> show that if a discrete, memoryless, point-to-point channel has at least two capacity-achieving input distributions and their dispersions V_1 (<ref>) are distinct, then using one-bit feedback improves the achievable second-order term. Although rate-0 feedback does not change the capacity region of a discrete memoryless MAC <cit.>, in light of <cit.> it is plausible that even one-bit feedback can improve the achievable second-order term for some MACs.] (see sec:comparison for details.)

To better understand thm:ach, consider a channel satisfying (<ref>)–(<ref>) for which the same distribution P_X maximizes I_k for all k.  For example, for the adder-erasure RAC in (<ref>), setting P_X to be Bernoulli(1/2) maximizes I_k for all k. By lem:mutualinfofriendly, for M large enough and any ϵ_1, ϵ_2, …, ϵ_K, one can pick n_1 < n_2 < ⋯ < n_K so that equality holds in (<ref>) for all k.
Therefore, thm:ach certifies that for some channels, rateless codes with encoders that are, until feedback, agnostic to the transmitter activity pattern perform as well in both first- and second-order terms as the best-known scheme  <cit.> designed with complete knowledge of transmitter activity. Moreover for any fixed 0 < ϵ_0 < 1, the probability that at time n_0 ≥ c_0 log n_1 + o(log n_1) the decoder correctly detects the scenario where no transmitters are active is no smaller than 1-ϵ_0. Thus, a new epoch can begin very quickly when no transmitters are active in the current epoch. 
  
  The constant c_0 in (<ref>) depends on the output distributions P_Y_k, k = 0, …, K, and on the hypothesis test chosen in sec:analysis_0test but not on the target probability of error ϵ_0. In contrast, the o(log n_1) term in (<ref>) depends on ϵ_0. See sec:analysis_0test (eq. (<ref>)) for an example where we bound the dependence of the o(log n_1) term on ϵ_0 under the log-likelihood ratio test. 
  
 Our achievability result in thm:ach assumes that the total number of transmitters, K, is constant. The asymptotic regime in which K grows with the decoding times, n_1, n_2, …, n_K, seeks to characterize scenarios with massive numbers of communicators <cit.>. Understanding the fundamental limits of random access communications in that regime presents an interesting challenge for future work.
  
 

 §.§ Comparison With the Existing Achievability Results
 
 

  §.§.§ Discrete Memoryless RACs

Our achievable region (thm:ach) is consistent with the achievability results for the 2-transmitter MACs given in <cit.>. The proofs in <cit.> use i.i.d. random code design, an approach that we follow in thm:ach. In <cit.>, Scarlett et al. use constant-composition codes.


In <cit.>, the achievable rate region of a discrete memoryless MAC is expressed as a three-dimensional vector inequality that relies on a 3 × 3 dispersion matrix 𝖵_2 defined in <cit.>; the entry of 𝖵_2 at location (3, 3) is V_2 (<ref>) for some input distribution (P_X_1, P_X_2). 
For rate pairs approaching interior (i.e., non-corner) points on the sum-rate boundary for (P_X_1^*, P_X_2^*), i.e., rate pairs satisfying

    (R_1, R_2) ∈{   (r_1 + o(1), r_2 + o(1)) 
       r_1 < I_2(X_1^*; Y_2^*|X_2^*) 
       r_2 < I_2(X_2^*; Y_2^*|X_1^*) 
       r_1 + r_2 = I_2(X_1^*, X_2^*; Y_2^*) },


the achievable region in <cit.> reduces to the scalar inequality

    R_1 + R_2 ≤ I_2^* -√(V_2^*/n)Q^-1(ϵ) + O( log n/n),

where 

    I_2^* ≜ I_2(X_1^*, X_2^*; Y_2^*)

is the sum-rate capacity and V_2^* is the dispersion V_2 (<ref>) evaluated using (P_X_1^*, P_X_2^*). The bound in (<ref>) implies that
the only component of 𝖵_2 employed in the second-order characterization of the region (<ref>) is V_2^*.  
The result in (<ref>) is proved in <cit.>. 

In <cit.>, Scarlett et al. use constant-composition codes to show that the dispersion matrix 𝖵_2 in the second-order achievable region can be improved to 𝖵̃_2, defined in <cit.>. Further, they show that 𝖵̃_2 ≼𝖵_2, where ≼ designates positive semidefinite order. Therefore, the second-order rate region that is obtained using constant-composition codes includes that achieved with i.i.d. random coding when the target error probability satisfies ϵ < 1/2. Scarlett et al. <cit.> present two examples for which 𝖵̃_2 ≺𝖵_2, demonstrating that the inclusion can be strict. The (3,3) component of 𝖵̃_2 is

    Ṽ_2^*    = V_2^* - _2(X_1^*, X_2^*; Y_2^*) | X_1^*
         - _2(X_1^*, X_2^*; Y_2^*) | X_2^*,

where P_X_1^* P_X_2^* P_Y_2^*|X_1^*, X_2^* = P_X_1^* P_X_2^* P_Y_2|X_1, X_2. The right side of (<ref>) is achievable with V_2^* replaced by Ṽ_2^*. In lem:scarlett, below, we derive a saddle point condition for general MACs without cost constraints. lem:scarlett implies that

    Ṽ_2^* = V_2^*.

This means that while constant-composition code design can yield achievability results with second-order terms superior to those derived through i.i.d. code design, on the sum-rate boundary that superior performance is observed only at corner points. For any rate point approaching an interior point on the sum-rate boundary, the i.i.d. random code design employed in this paper achieves first- and second-order performance identical to that achieved by constant-composition code design.





















































 
Let P_Y_2|X_1, X_2 be a 2-transmitter MAC with finite sum-rate capacity. Assume that the σ-algebra on the abstract input alphabets 𝒳_i includes all singletons on 𝒳_i, i = 1, 2.

Let (X_1^*, X_2^*, Y_2^*) ∼ P_X_1^* P_X_2^* P_Y_2|X_1, X_2, where (P_X_1^*, P_X_2^*) is a sum-rate capacity achieving input distribution, i.e., 

    I_2^* ≜ I_2(X_1^*, X_2^*; Y_2^*) = sup_P_X_1 P_X_2 I_2(X_1, X_2; Y_2) < ∞.

Then, for i = 1, 2, 

    _2(X_1^*, X_2^*; Y_2^*) | X_i^*   = I_2^*,

where (<ref>) holds P_X_i^*-almost surely.


See app:scarlett. 

A version of lem:scarlett for discrete memoryless MACs appears in <cit.>. The result is proved by verifying that (<ref>) satisfies the Karush-Kuhn-Tucker (KKT) conditions for the maximization problem in (<ref>) (Although the maximization problem in (<ref>) is not convex, it satisfies a regularity condition ensuring the necessity of the KKT conditions for optimality <cit.>.) We extend <cit.> to general MACs by demonstrating a saddle point condition for MACs. The saddle point condition is more general in the sense that it applies to abstract alphabets. 





From (<ref>), we deduce that

    _2(X_1^*, X_2^*; Y_2^*) | X_i^* = 0,    i = 1, 2.

Substituting (<ref>) into (<ref>), we obtain (<ref>).


The result in (<ref>)–(<ref>) extends the following well-known properties of point-to-point DMCs to MACs. In <cit.>, the KKT conditions in (<ref>)–(<ref>) for point-to-point DMCs are

    I_1^*    ≜max_P_X_1 I_1(X_1; Y_1) 
    _1(X_1^*; Y_1^*) | X_1^*   = I_1^*    if  P_X_1^*(x_1) > 0 
    _1(X_1^*; Y_1^*) | X_1^* = x_1   ≤ I_1^*    if  P_X_1^*(x_1) = 0;

these conditions are necessary and sufficient for optimality.
As noted in <cit.>, (<ref>)–(<ref>) indicate that for a capacity-achieving input distribution P_X_1^*, 

    _1(X_1^*; Y_1^*) | X_1^* = 0.

From (<ref>) and the law of total variance, it follows that the unconditional and conditional variances of _1(X_1^*; Y_1^*) given X_1^* are equal, i.e.,

    V_1 = _1(X_1^*; Y_1^*)|X_1^*.
 
For point-to-point DMCs, Moulin <cit.> shows that the second-order term Ṽ_1 achievable using constant-composition coding equals the right-hand side of (<ref>), meaning that i.i.d. random code design and constant-composition random code design achieve the same fundamental limits for point-to-point DMCs.



  §.§.§ The Gaussian RAC

While the RAC code definition (Definition <ref>) does not impose cost constraints on the codewords, cost constraints can be added where needed. In the case of the Gaussian RAC defined in (<ref>), the maximal power constraint P on the codewords requires that

    ‖(u, w)^n_k‖^2 ≤ n_k P

for all u ∈𝒰, w ∈ [M], and k ∈ [K], where ‖·‖ denotes the Euclidean norm. If any encoder attempts to transmit a codeword that does not satisfy (<ref>), we count that event as an error. Hence, the maximal power constraints add the term 

    ⋃_j = 1^k ⋃_i = 1^k {‖ X_i^n_j‖^2 > n_j P }

to the error terms in (<ref>). 

For the Gaussian k-MAC under maximal power constraints, drawing codewords i.i.d. according to distribution P_X ∼𝒩(0, P-δ_n_k) for any δ_n_k→ 0 as n_k →∞ yields a worse second-order performance bound than the one achieved by drawing codewords uniformly at random from the n_k-dimensional power sphere <cit.>. MolavianJazi and Laneman <cit.> and Scarlett et al. <cit.> derive the improved second-order term for the Gaussian MAC by drawing codewords uniformly at random over an n_k-dimensional power sphere and by combining constant-composition code design with a quantization argument, respectively. In <cit.>, for the Gaussian MAC and RAC, we prove the achievability of the same second-order term as <cit.> with an improved third-order term 1/2log n_k. The proof employs codewords designed by concatenating spherically distributed sub-blocks and a maximum likelihood decoding rule combined with a threshold rule based on the output power.















 §.§ An Example RAC

The following example investigates rates achievable for the adder-erasure RAC in (<ref>).

For the adder-erasure RAC, the capacity achieving distribution is the equiprobable (Bernoulli(1/2)) distribution for all k. (See the proof of thm:ikvk in Appendix <ref>.) For this channel, one can exactly calculate I_k and V_k for this channel for every k (labelled “True” in fig:ikvk). The approximating characterizations

    I_k =   (1-δ) ( 1/2logπ e k/2 - log e/12 k^2 )+ O(k^-3) 
       V_k = (1 - δ) [ δ/4log^2 π e k/2 + log^2 e/2  - log^2 e/2 k
          - ( log e/2 + δlogπ e k/2/12) log e/k^2] + O( log k/k^3)  ,
  
which capture the first- and second-order behavior of I_k and V_k for each k, are, nonetheless, useful since they highlight how each depends on k and δ. These values, without the O(·) terms in (<ref>)–(<ref>), are labelled “Approximation" in fig:ikvk.
The approximations are quite tight even for small k. Both I_k and √(V_k) are of order O(log k), indicating that as k grows, the sum-rate capacity grows, albeit slowly, while the per-user rate vanishes as log k/k. The dispersion V_k also grows, and the speed of approach to the sum-rate capacity is slower. Interestingly, the dispersion behavior is different for the pure adder RAC (δ = 0), in which case V_k = log^2 e/2  + 1/k is almost constant as a function of k. The derivation of (<ref>) and (<ref>) relies on an approximation for the probability mass function of the (k, 1/2) Binomial distribution using a higher order Stirling's approximation (app:adder). 
 
 

fig:rk shows the approximate rate per transmitter, R_k = log M/n_k (neglecting the O(1) term in (<ref>)), achieved by the proposed scheme as a function of the number of active transmitters, k, and the choice of blocklength n_1 for a fixed error probability ϵ_k = 10^-6 for all k. Fixing n_1 and ϵ_k fixes the maximum achievable message size, M, according to (<ref>). The remaining n_k for k ≥ 2 are found by choosing the smallest n_k that satisfies (<ref>) using the given M and ϵ_k. Each curve illustrates how the rate per transmitter (R_k) decreases as the number of active users k increases. The curves differ in their choice of blocklength n_1 and the resulting changes in M and n_0, n_2, …, n_K. Here n_1 is fixed to 20, 100, 500 and 2500. For a fixed k, the points on the same vertical line demonstrate how the gap between the per-user capacity and the finite-blocklength achievable rate decreases as blocklength increases.




 §.§ A Non-asymptotic Achievability Result

Theorem <ref> follows from Theorem <ref>, stated next,
which bounds the error probability of the RAC code 
defined in Section <ref>.  
When k transmitters are active, the error probability ϵ_k captures both errors in the estimate t of k 
and errors in the reproduction _[t] of W_[k] when t=k. Theorem <ref> is formulated for an arbitrary choice of a statistic h𝒴^n_0↦ℝ used to decide whether any transmitters are active. Possible choices for h(·) appear in (<ref>) and (<ref>) in sec:analysis_0test, below.


Fix constants γ_0, λ_s, t^k ≥ 0, and γ_t > 0 for all 1 ≤ s ≤ t ≤ k.
For any RAC 
    {(^k, P_Y_k | X_[k](y_k|x_[k]), _k)}_k=0^K
 satisfying (<ref>) and (<ref>), any K ≤∞[Note that while thm:ach requires K<∞, thm:nonasymp allows K=∞. For K=∞, (<ref>) holds for every finite k since the bound on ϵ_k depends only on the RAC with at most k active transmitters.], and any fixed input distribution P_X, there exists an (M, { (n_k, ϵ_k) }_k = 0^K ) code such that

    ϵ_0 ≤ h(Y_0^n_0) > γ_0  ,

and for all k≥ 1,
		rCl
         *
        ϵ_k    ≤    [_k(X_[k]^n_k; Y_k^n_k) ≤logγ_k]  

              +   h(Y_k^n_0) ≤γ_0    


              + k(k-1)/2M  

              +∑_t = 1^k - 1 kt [_t(X_[t]^n_t; Y_k^n_t) > logγ_t ]  

              +∑_t = 1^k ∑_s = 1^t-1 kt-s  ℙ[_t(X_[s+1:t]^n_t; Y_k^n_t) 

                > n_t 𝔼 [_t(X_[s+1:t]; Y_k) ] + λ_s, t^k ]  

              + ∑_t = 1^k∑_s = 1^t kt-s M-ks  ℙ [_t( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t) 

                > logγ_t - n_t 𝔼 [_t(X_[s+1:t]; Y_k) ] - λ_s, t^k ],   
		
where for any n, (X_[k]^n, X̅_[k]^n, Y_k^n) is a random sequence drawn i.i.d. ∼ P_X_[k]X̅_[k] Y_k(x_[k], x̅_[k], y_k) = ( ∏_i = 1^k P_X(x_i) P_X(x̅_i) ) P_Y_k|X_[k](y_k | x_[k]).
 

The operational regime of interest is when ϵ_0, …, ϵ_k are constant; that is, ϵ_k does not vanish as n_k grows. For k = 0, the error term in (<ref>) is the probability that the decoder does not correctly determine that the number of active transmitters is 0 at time n_0. For k > 0,  (<ref>) is the probability that the true codeword set produces a low information density. This is the dominating term in the regime of interest. All remaining terms are negligible, as shown in the refined asymptotic analysis of the bound in thm:nonasymp (see Section <ref>, below.)
The remaining terms bound the probability that the decoder incorrectly estimates the number of active transmitters as 0 (<ref>), the probability that two or more transmitters send the same message (<ref>),[Given the use of identical encoders, multiple encoders sending the same message can be beneficial or harmful, depending on the channel. To simplify the analysis, we treat this (exponentially rare) event as an error.] the probability that the decoder estimates the number of active transmitters as t for some 1 ≤ t<k and decodes those t messages correctly (<ref>), and the probability that the decoder estimates the number of active transmitters as t for some 1 ≤ t≤ k and decodes to s messages that were not transmitted and t-s messages that were transmitted (<ref>)–(<ref>). 

For k = 1, 2, the expression in (<ref>) particularizes to
 
    ϵ_1    ≤[_1(X_1^n_1; Y_1^n_1)≤logγ_1 ] +   h(Y_1^n_0 ) ≤γ_0  
          + (M-1) [ _1(X̅_1^n_1 ; Y_1^n_1) > logγ_1 - λ_1,1^1 ] 
    ϵ_2    ≤[_2(X_[2]^n_2; Y_2^n_2)≤logγ_2 ] +   h(Y_2^n_0 ) ≤γ_0  
          + 1/M + 2 [_1(X_1^n_1 ; Y_2^n_1) > logγ_1 ] 
          + 2 [ _2(X_2^n_2; Y_2^n_2) ≥ n_2 I_2(X_2; Y_2) + λ_1,2^2 ] 
          + (M-1)[ _1(X̅_1^n_1; Y_2^n_1) > logγ_1 - λ_1,1^2 ]  
          + 2 (M-2) [ _2(X̅_1^n_2; Y_2^n_2 | X_2^n_2 ) 
            > logγ_2 - n_2 I_2(X_2; Y_2) - λ_1, 2^2] 
           + (M-2)(M-3)/2[ _2(X̅_[2]^n_2; Y_2^n_2 ) > logγ_2 - λ_2,2^2].

    
For the MAC with K transmitters, i.e., the scenario where K transmitters are always active, the only decoding time is n_K. The error terms associated with incorrect decoding times are no longer needed in this case, and the error probability bound in (<ref>) becomes
rCl
         *
        ϵ_K    ≤    [_K(X_[K]^n_K; Y_K^n_K) ≤logγ_K] + K(K-1)/2M 

              + ∑_s = 1^K-1 KK-s  ℙ[_K(X_[s+1:K]^n_K; Y_K^n_K) 

                > n_K 𝔼 [_K(X_[s+1:K]; Y_K) ] + λ_s, K^K ]   

              + ∑_s = 1^K KK-s M-Ks  ℙ [_K( X̅_[s]^n_K ; Y_K^n_K | X_[s+1: K]^n_K) 

                > logγ_K - n_K 𝔼 [_K(X_[s+1:K]; Y_K) ] - λ_s, K^K 
        ]. 


A description of the proposed RAC code and the proofs of Theorems <ref> and <ref> 
appear in Section <ref>. 



§ THE RAC CODE AND ITS PERFORMANCE



 §.§ Code Design


We construct the RAC code used in the proofs of Theorems <ref> and <ref> 
as follows.

Encoder Design: The common randomness random variable U = (U(1), …, U(M)) has distribution

    P_U    ≜ P_U(1)×⋯×  P_U(M),

where P_U(w) = P_X^n_K, w = 1, …, M, and P_X is a fixed distribution on alphabet . Each realization of U defines a codebook with M i.i.d. vectors U(1), …, U(M) of dimension n_K (the codewords). Note that the cardinality of the alphabet U is ||^M n_K. In <cit.>, Polyanskiy et al. use Carathéodory's Theorem to show that the common randomness U can be replaced with common randomness U' with cardinality at most K + 2. We reduce this alphabet size to K + 1 in app:caratheodory. As described in Definition <ref>, 
an (M,{(n_k,ϵ_k)}_k = 0^K) RAC code with identical encoders employs the same encoder (·) at every transmitter. The encoder (U, ·) depends on U as

    (U, w) = U(w)    w = 1, …, M.

For brevity, we omit U in the encoding and decoding functions and write (U, w) = (w) for w = 1, …, M, and _k(U, y^n_k) = _k(y^n_k) for y^n_k∈𝒴_K^n_k, k ∈{0, …, K}. Recall that (w) is a n_K-dimensional vector. We use (w)^n_k to denote the first n_k coordinates of vector (w).
For any collection of messages w_[k]∈[M]^k, we use (w_[k]) ≜((w_1),…,(w_k)) 
to denote the collection of encoded descriptions produced by the encoders.

Decoder Design: 
Upon receiving the first n_0 samples of the channel output Y, the decoder runs the following composite hypothesis test

    _0(y^n_0)=
            {[               h(y^n_0) ≤γ_0;                             ].

to decide whether there are any active transmitters.
Decoder output  signifies that the decoder decides that all transmitters are silent, sending a feedback bit `1' to all transmitters to start a new coding epoch. Decoder output e indicates that the receiver believes that there are active transmitters; the decoder transmits feedback bit `0' to the transmitters, telling them that it is not ready to decode, and therefore that transmissions must continue. Statistic h 𝒴^n_0↦ℝ is used to decide whether any transmitters are active.

For each k ≥ 1, decoder 𝗀_k observes output y^n_k and employs a single threshold rule 

    _k(y^n_k)=
            
            w_[k]   _k((w_[k])^n_k;y^n_k)>logγ_k 
       if   w_i < w_j   ∀  i < j

 for some constant γ_k chosen before the transmission starts. 
Under permutation-invariance (<ref>) and identical encoding (<ref>), all permutations of the message vector w_[k] give the same information density. We use the ordered permutation specified in (<ref>) as a representative of the equivalence class with respect to the binary relation π=. The choice of a representative is immaterial since decoding is identity-blind.
When there is more than one ordered w_[k] that satisfies the threshold 
condition, decoder 𝗀_k chooses among these options arbitrarily.  
All such events are counted as errors in the analysis in sec:thmpe, below. If the decoder output is a message vector w_[k], then the decoder sends feedback bit `1', telling them to stop transmission. Otherwise, the decoder sends feedback bit `0', and the epoch continues. For k ≥ 1, the decoder _k(y^n_k) depends on U through its dependence on the encoding function (w_[k]); for k = 0, _0(y^n_0) does not depend on U. 

The proof of Theorem <ref>, below, bounds the error probability for the proposed code.



 §.§ Proof of Theorem <ref>



In the discussion that follows, we bound the error probability of the code (,{_k}_k = 0^K) 
defined above.  For k = 0, the only error event is that the received vector at time n_0, Y_0^n_0, fails to pass the test

    ϵ_0    ≤_0(Y_0^n_0) ≠ | W_0 = 0

given in (<ref>).
For k > 0, the analysis relies on the independence of codewords (W_i) and (W_j) 
from distinct transmitters i and j.
Given identical encoders and i.i.d. codeword design, this assumption is valid provided that W_i≠ W_j; 
we therefore count events of the form W_i=W_j as errors.






Let  denote the probability of such a repetition; the union bound gives




    ≤k(k-1)/2M.


The discussion that follows uses
_[k]=(1, 2, …,k) as an example instance of a message vector w_[k] 
in which w_i≠ w_j for all i ≠ j. The set
_[s] describes all ordered message vectors that do not share any messages in common with _[k], i.e., 

    _[s]≜{_[s]∈[M]^s _1  > k, _i < _j    ∀ i < j}.


Let the components of the vectors (X_[k]^n_k, X̅_[k]^n_k, Y_k^n_k) be i.i.d. with joint distribution

    P_X_[k]X̅_[k] Y_k(x_[k], x̅_[k], y_k) 
          = P_X_[k](x_[k]) P_X_[k](x̅_[k]) 
        P_Y_k | X_[k](y_k | x_[k]).







Recall that the information density _t(x_[t]^n_t; y_t^n_t) in (<ref>) is defined with respect to (X_[t]^n_t, Y_t^n_t), not with respect to (X̅_[t]^n_t, Y_t^n_t). The resulting error bound proceeds as shown in (<ref>)–(<ref>); 
here X_[k] is the vector of transmitted codewords, 
and X̅_[s](_[s]) is an i.i.d. copy of X̅_[s], which represents the codeword for a collection of messages _[s]∈_[s] 
that was not transmitted.
Line (<ref>) separates the case where at least one message is repeated
from the case where there are no repetitions.
Lines (<ref>)–(<ref>) enumerate the error events in the no-repetition case; 
these include 
        all cases where the transmitted codeword passes the binary hypothesis test (<ref>) for “no active transmitters" (<ref>), 
        all cases where a subset of the transmitted codewords meets the threshold for some t<k (<ref>), 
        all cases where a codeword that is incorrect in s dimensions and correct in t-s dimensions meets the threshold for t≤ k (<ref>), and all cases where the transmitted codeword fails to meet the threshold (<ref>). 
        We apply the union bound and the symmetry of the code design 
        to represent the probability of each case by the probability of an example instance times the number of instances. Equations (<ref>)-(<ref>) apply the bound in (<ref>) and replace decoders by the threshold rules in their definitions. 
    
The delay in applying the union bound to the first probability in (<ref>) is deliberate. It allows us to exploit the symmetry assumptions on the channel and to use a single threshold rule instead of 2^k-1 threshold rules as in <cit.>. 
Applying the bound
rCl
[⋃__[s]∈_[s]{_t(X̅_[s]^n_t(_[s]),X_[s+1:t]^n_t;Y_k^n_t)>logγ_t }]  

    =     [⋃__[s]∈_[s]{_t(X̅_[s]^n_t(_[s]),X_[s+1:t]^n_t;Y_k^n_t)>logγ_t } 

        ⋂{_t(X_[s+1:t]^n_t;Y_k^n_t)>n_t[_t(X_[s+1:t];Y_k)]+λ_s,t^k}] 

        +[⋃__[s]∈_[s]{_t(X̅_[s]^n_t(_[s]),X_[s+1:t]^n_t;Y_k^n_t)>logγ_t } 

            ⋂{_t(X_[s+1:t]^n_t;Y_k^n_t)≤n_t[_t(X_[s+1:t];Y_k)]+λ_s,t^k}] 

   ≤    [_t(X_[s+1:t]^n_t;Y_k^n_t)>n_t[_t(X_[s+1:t];Y_k)]+λ_s,t^k] 

        +[⋃__[s]∈_[s]{_t(X̅_[s]^n_t(_[s]);Y_k^n_t|X_[s+1:t]^n_t)>  

         logγ_t -n_t[_t(X_[s+1:t];Y_k)]-λ_s,t^k}] 














before applying the union bound to the first probability in (<ref>) yields a tighter bound. Combining (<ref>) and (<ref>) and applying the union bound to the second probability in (<ref>) completes the proof. 

















 §.§ Proof of Theorem <ref>


We fix P_X, M, {ϵ_k}_k = 0^K, and we set the blocklengths {n_k}_k = 1^K as

    n_k     = γ_k^2 (e/k(M-k))^-2k,

where

    logγ_k    =  n_k I_k - τ_k √(n_k V_k)
    τ_k    ≜ Q^-1(ϵ_k-B_k+C_k/√(n_k)),

C_k is a constant to be chosen in (<ref>),

    B_k    ≜6 T_k/V_k^3/2

is the Berry-Esseen constant <cit.> 
(which is finite by the moment assumptions (<ref>)
and (<ref>)), and

    T_k    ≜|_k(X_[k] ; Y_k) - I_k |^3.


The choice of the threshold γ_k (<ref>)
follows the approach established 
for the point-to-point channel in <cit.>. Solving (<ref>) for M and applying the Taylor series expansion to Q^-1(·), we see that the size of the codebook admits the following expansion 

    k log M    =  n_k I_k - √(n_k V_k) Q^-1( ϵ_k  ) - 1/2log n_k + O(1)

simultaneously for all k ∈ [K]. 
Note that the expansion in (<ref>) is the best-known performance up to the second-order term for MACs without random access <cit.>, and we have chosen our parameters with the goal of matching that best prior performance. By lem:mutualinfofriendly, the resulting blocklengths satisfy n_1 < n_2 < ⋯ < n_K for M large enough. 

We proceed to apply thm:nonasymp to show that under the given parameter choices, the probability of decoding error at time n_k is bounded above by ϵ_k.
The constants {λ_s,t^k} used in the error probability bound (<ref>)–(<ref>) are set as

    λ_s,t^k     =  n_t/2(I_t(X_[s]; Y_t | X_[s+1:t]) 
    	- s/t I_t )

to ensure that
λ_s,t^k> 0 when s < t (see Lemma <ref>) 
and that λ_s,t^k=0 when s = t. Next, we sequentially bound
the terms in Theorem <ref> using the parameters chosen in (<ref>), (<ref>), and (<ref>).


  * (<ref>):
As noted previously, this is the dominant term. Since _k(X_[k]^n_k;Y_k^n_k)
is a sum of n_k independent random variables, by the Berry-Esseen theorem <cit.> and (<ref>)–(<ref>),  

    ℙ[ _k(X_[k]^n_k ; Y_k^n_k) ≤logγ_k ] ≤ϵ_k - C_k/√(n_k).


  * (<ref>): The test statistic h(·) and the threshold γ_0 given in (<ref>) are chosen in Section <ref> to satisfy

    h(Y_k^n_0) ≤γ_0   ≤E_k/√(n_k)
    h(Y_0^n_0) > γ_0   ≤ϵ_0

for some constant E_k > 0. lem:test, below, bounds the type-II error in (<ref>) in terms of n_0 when the type-I error in (<ref>) is bounded by ϵ_0.

Fix ϵ_0 ∈ (0, 1). Assume that (<ref>) holds. Then there exists a test function h(·) such that (<ref>) is satisfied and

    h(Y_k^n_0) ≤γ_0≤exp{-n_0 C' + o(n_0)}

for some C' > 0 depending on the output distributions P_Y_i for i = 0, …, K.


See Section <ref>.

From (<ref>), n_k = n_1 for k ≥ 1. To make (<ref>) behave as O( 1/√(n_k)) in lem:test, we pick n_0 as in (<ref>) with c_0 = 1/2C'.





  * (<ref>): According to (<ref>), the upper bound k(k-1)/2M on  in (<ref>) decays exponentially with n_k.


  * (<ref>): 
Define p as

    p ≜[_t (X_[t] ; Y_k) > - ∞].

We next analyze (<ref>) for the cases p = 1 and p < 1.

Case 1: p = 1. 
By Lemma <ref> and moment assumption (<ref>), 

    I_t - 𝔼[ _t (X_[t] ; Y_k)] -τ_t √(V_t/n_t) > 0
 
for sufficiently large n_t. Chebyshev's inequality gives

    ℙ[_t (X_[t]^n_t ; Y_k^n_t) > logγ_t ] 
         ≤Var[_t (X_[t] ; Y_k)]/n_t (I_t - 𝔼[ _t (X_[t] ; Y_k)] -τ_t √(V_t/n_t))^2.

The right side of (<ref>) 
behaves as O(1/n_t).

Case 2: p < 1.
Here

    ℙ[_t (X_[t]^n_t ; Y_k^n_t) > logγ_t ]  
         ≤ℙ[_t (X_[t]^n_t ; Y_k^n_t) > -∞ ] 
          = p^n_t,

where (<ref>) holds because _t (X_[t]^n_t ; Y_k^n_t) is the sum of n_t i.i.d. random variables, and that sum is greater than -∞ if and only if all the summands satisfy the same inequality.
From (<ref>) and (<ref>), (<ref>) contributes O(1/n_k) to our error bound. 


  * (<ref>): 
As in the analysis of (<ref>), we define

    q ≜[_t (X_[s+1: t] ; Y_k) > - ∞],

and treat the cases q = 1 and q < 1 separately. Observe that for q = 1,  Chebyshev's inequality implies

    [_t(X_[s+1:t]^n_t;Y_k^n_t)>n_t [_t(X_[s+1:t];Y_k) ]
    		+λ_t,s^k  ] 
         ≤Var[ _t(X_[s+1:t];Y_k) ] /n_t (1/2(I_t(X_[s];Y_t|X_[s+1:t])
    			-s/t I_t))^2 ,

	which is of order O (1/n_t) by the moment assumption (<ref>) and Lemma <ref>.

For q < 1, 

    [_t(X_[s+1:t]^n_t;Y_k^n_t)>n_t [_t(X_[s+1:t];Y_k) ]+λ_t,s^k  ] ≤ q^n_t.

Therefore (<ref>) contributes 1/n_k to 
our error bound.
 
 
  * (<ref>):
First, consider the case where s < t ≤ k.  By lemma:expectation and Chernoff's bound,  

    ℙ [_t( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t) 
          > logγ_t - n_t  [_t(X_[s+1:t] ; Y_k)] - λ_s, t^k ] 
       ≤ℙ [_t( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t) 
          > logγ_t - n_t I_t(X_[s+1:t]; Y_t) - λ_s, t^k ] 
       ≤exp{_t ( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t) }
         ·exp{ -(logγ_t - n_t I_t(X_[s+1:t]; Y_t) - λ_s, t^k )}
       = exp{ - (logγ_t - n_t I_t(X_[s+1:t]; Y_t) - λ_s, t^k )}.

Using Stirling's bound

    nk≤( e n/k)^k,

we find that for all s ≤ t ≤ k

    logM-ks   ≤ s log( e (M-k)/s) 
       ≤ s log( e (M-t)/t) + s log( t/s) 
       = s/t( logγ_t - 1/2log n_t ) + s log( t/s),

where (<ref>) follows from (<ref>). From (<ref>), (<ref>), (<ref>), and (<ref>), we have

    M-ksℙ [_t( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t) 
            > logγ_t - n_t I_t(X_[s+1:t]; Y_t) - λ_s, t^k ] 
         ≤exp{ - n_t 1/2(I_t(X_[s]; Y_t | X_[s+1: t]) - s/t I_t ) 
            + ( 1 - s/t) τ_t √(n_t V_t) - s/2tlog n_t + s log(t/s) }.

lem:mutualinfo ensures that the exponent in (<ref>) is negative for n_t large enough. 

For s = t < k, from (<ref>) and (<ref>) with s = t, we get

    M-ktℙ [_t( X̅_[t]^n_t ; Y_k^n_t) > logγ_t]    ≤M-kt/γ_t≤1/√(n_t).



For s = t = k, following the change of measure technique  (e.g., <cit.>), one can rewrite an expectation with respect to measure Q as an expectation with respect to measure P, giving 

    Q [ Z ∈𝒜]  = 𝔼_P[ ( P[Z]/Q[Z])^-1 1 { Z ∈𝒜}].

Switching to the measure P_X_[k] P_Y_k | X_[k] in this way, by (<ref>) and the parameter choice (<ref>), we write
	rCl
	 M-kk [_k( X̅_[k]^n_k ; Y_k^n_k )  > logγ_k  ] 

	    ≤    (e/k(M-k))^k  [ exp{-_k( X_[k]^n_k;Y_k^n_k)} . 

	         ·.1{_k(X_[k]^n_k;Y_k^n_k)  >  logγ_k } ] 

	     ≤    D_k/n_k ,
	
	where

    D_k≜ 2 ( log 2 /√(2 π V_k ) + 2 B_k )

and B_k is defined in (<ref>).
To justify (<ref>), notice that _k(X_[k]^n_k;Y_k^n_k) is a sum of i.i.d. random variables; in <cit.>, Polyanskiy et al. derive a sharp bound on the expectation

    exp( -∑_i = 1^n Z_i) 1{∑_i = 1^n Z_i  > γ}
 
when the Z_i's are independent. Applying that bound with Z_i = _k(X_[k],i; Y_k, i) yields (<ref>). Note that D_k is finite by the moment assumptions (<ref>) and (<ref>). 
Combining the bounds for the three cases in (<ref>), (<ref>), and (<ref>), we conclude that (<ref>) contributes 1/√(n)_k to the total error.

Finally, we set the constant C_k in (<ref>) to ensure

    (<ref>) + (<ref>) + (<ref>)+(<ref>)+(<ref>)≤C_k/√(n_k).

The existence of such a constant is guaranteed by our analysis above demonstrating that the terms (<ref>)–(<ref>) do not contribute more than 1/√(n)_k to the total.[Our bounds on (<ref>)–(<ref>) technically depend on γ_k and therefore on C_k. However, it is easy to see that their dependence on C_k is weak, and for large enough n_k, it can be eliminated entirely.   Thus the choice of C_k satisfying (<ref>) is possible.]


Due to (<ref>) and (<ref>), the total probability of making an error at time n_k is bounded by ϵ_k, and the proof of Theorem <ref> is complete. 




§ DISCUSSION OF THE MAIN RESULT
 



 §.§ Refining the Third-Order Term Using a Maximum Likelihood Decoder
 














For a RAC that satisfies the conditions in thm:ach and the conditional variance condition

    _k(X_[k]; Y_k)| Y_k > 0   ∀ s ∈ [k],

we can improve the achievable third-order performance in (<ref>) from -1/2log n_k to +1/2log n_k. Prior work showing the achievability of the + 1/2log n third-order term includes <cit.> for point-to-point channels satisfying (<ref>) with k = 1, <cit.> for the Gaussian point-to-point channel, <cit.>, <cit.> for discrete memoryless MACs satisfying (<ref>), and <cit.>, <cit.> for the Gaussian MAC and RAC. We can achieve the result here by replacing the threshold rule in (<ref>) with a combination of a hypothesis test and a maximum likelihood decoder, giving

    _k(U, y^n_k)    =
            max_w_[k] _k((w_[k])^n_k;y^n_k)    if  h_k(y^n_k) ≤γ_k 
       otherwise,

where the maximum is over the ordered message vectors w_[k], and h_k(·) is a suitable test function that allows us to distinguish P_Y_k from any P_Y_t with t ≠ k. As in prior work, the analysis applies the random coding union bound from <cit.>. 
As discussed in sec:analysis_0test, suitable test functions h_k(·) can be found provided that P_Y_k≠ P_Y_t for all t ≠ k. For instance, in <cit.>, we use h_k(y^n_k) = |1/n_k y^n_k^2 - (1 + kP) | for the Gaussian RAC, where P is the maximal power constraint. The result does not apply to channels such as the adder-erasure RAC (<ref>), which does not satisfy the condition in (<ref>).



 §.§ Choosing the Input Distribution P_X
 
Although there are RACs for which a single input distribution P_X achieves the capacity for all k-MACs, k ∈ [K], (e.g., the adder-erasure channel), the permutation-invariance (<ref>) and reducibility (<ref>) assumptions do not imply that such a distribution exists for all RACs. In the following, we discuss how to choose the input distribution when the optimal input distribution varies with k.

Given a permutation-invariant (<ref>) and reducible (<ref>) RAC, M, ϵ = (ϵ_0, …, ϵ_K), and any P_X such that (<ref>)–(<ref>) are satisfied for the given RAC under input distribution P_X, let  

    ℛ(M, ϵ, P_X) = {(R_0, …, R_K) (<ref>) and (<ref>) hold}

denote the achievable rate region under input distribution P_X.
Here

    R_k = log M/n_k for all  k ∈{0, …, K}.

Let

    ℛ(M, ϵ) = ⋃_P_X: (<ref>)–(<ref>) holdℛ(M, ϵ, P_X)

denote the achievable rate region over all i.i.d. input distributions. A point in this set is called dominant if no other points in the set are element-wise greater than or equal to that point. To optimize the achievable rate vector over the allowed input distributions, we must choose a distribution P_X^* that achieves a dominant point for the set ℛ(M, ϵ). 
Note that for the dominant points of ℛ(M, ϵ) corresponding to different values of P_X^*, there is an O(1) difference between the left and right sides of the inequalities in (<ref>). If the achievable rate region ℛ(M, ϵ) is not convex, it can be improved to its convex hull using time sharing. For the modifications to the coding strategy that enable us to incorporate time sharing, see <cit.>. 



To illustrate what happens when different P_X^* values achieve different dominant points of ℛ(M, ϵ), we consider the following example.

 
Consider a RAC with K = 2, 𝒳 = 𝒴_2 = {0, 1}, and transition probability matrix P_Y_2|X_1, X_2

    Y_2\X_1 X_2   00   01   10   11
    0   1-b   b   b   1-a
    1   b   1-b   1-b   a

where a, b ∈ [0, 1]. This RAC is permutation-invariant since the “01" and the “10" columns are identical. When k = 1, the channel reduces to the binary symmetric channel with crossover probability b.
fig:rateTot illustrates the set of achievable rate vectors ℛ(M, ϵ) (neglecting the O(1) term in (<ref>)) with log M = 1000 and ϵ = 10^-31 for two choices of parameters in the channel in (<ref>). In fig:rate1, a = 0.7, b = 0.11, and in fig:rate2, a = b = 0.11; for each, the finite blocklength and capacity boundaries are demonstrated. In fig:rate1, the dominant points are highlighted. The input distribution P_X^* = (0.65, 0.35) (i.e., the Bernoulli(0.35) distribution) achieves the dominant point (R_1, R_2) = (0.400, 0.204); the corresponding region ℛ(M, ϵ, P_X^*) is shown as the region bounded by the dashed lines. In fig:rate2, the only dominant point (0.437, 0.227) is achieved by the input distribution P_X^* = (0.5, 0.5) (i.e., the Bernoulli(0.5) distribution.) Therefore, for the channel in fig:rate2, the achievable rate region ℛ(M, ϵ) coincides with ℛ(M, ϵ, P_X^*), and we must choose P_X^* as our input distribution. For this channel, P_X^* = (0.5, 0.5) simultaneously maximizes the mutual informations I_1 and I_2, and the maxima are I_1 = I_2 = 0.5.


 



 §.§ Discussion of the Converse
 
Even for MACs with only 2 transmitters, the capacity region for the MAC remains incompletely understood. A brief summary of related results follows. For any blocklength n and average error probability ϵ∈ (0, 1), let 

    ℛ(n, ϵ) = {(log M_1/n, log M_2/n) ∃ an  (n, M_1, M_2, ϵ)  code}

denote the set of achievable rate pairs, where M_i is the message size for transmitter i ∈{1, 2}. The capacity region of the MAC <cit.> is 

    𝒞 = ⋃_P_Q P_X_1|Q P_X_2|Q{ (R_1, R_2)    
    
        R_1    ≤ I_2(X_1; Y_2|X_2, Q) 
    
        R_2    ≤ I_2(X_2; Y_2|X_1, Q)  
    
        R_1 + R_2    ≤ I_2(X_1, X_2; Y_2|Q)},

where Q is the time sharing random variable. In <cit.>, Dueck uses the blowing-up lemma to derive the first strong converse for discrete memoryless MACs. In <cit.>, for discrete memoryless MACs, Ahlswede uses a wringing technique to show 

    ℛ(n, ϵ) ⊆𝒞 + log n/√(n)1,

which improves Dueck's result. The coefficients of the term log n/√(n)1 in (<ref>) are bounded by a multiple of the product of input and output alphabet sizes |𝒳_1| |𝒳_2||𝒴_2|. 









In <cit.>, Fong and Tan improve Ahlswede's second-order term log n/√(n)1 to √(log n/n)1 for the Gaussian MAC. They derive this result by applying Ahlswede's wringing technique <cit.> to quantized channel inputs. 
In <cit.>, Kosut further improves the second-order term to 1/√(n)1. The second-order term in <cit.> has the same order and, for some channels, the same sign as the best-known second-order achievable term in <cit.>. Kosut's result




applies to all discrete memoryless MACs and to the Gaussian MAC. To prove this converse, Kosut introduces a new measure of dependence between two random variables called “wringing dependence." A key aspect of the approach is to restrict the channel inputs so that the wringing dependence between them is small. 






In <cit.>, Moulin proposes a new converse technique for maximum-error capacity. His approach relies on strong large deviations for binary hypothesis tests and leads to a second-order term as in (<ref>) when no time sharing is needed. Since the capacity regions for the maximum and average error probability can differ <cit.>, Moulin's result does not give a converse for the average-error capacity. 





Whether it is possible to derive a converse for the average-error capacity with a second-order term matching the ones in <cit.> remains an open problem.

In the sparse recovery literature, where achievability proofs typically consider the expected error probability evaluated under i.i.d. codebook design (see, e.g.,  <cit.>), converses derive lower bounds on the expected error probability assuming i.i.d. code design. Although a lower bound on the expected error probability for our problem could be derived using tools from <cit.>, such a bound would yield a bound for the best i.i.d. random code rather than a bound for all possible codes.



 §.§ A RAC Code That Decodes Transmitter Identity
  

While the use of identical encoding at all transmitters has a number of practical advantages, the techniques employed in this work are not limited to that case. 

We next briefly explore the use of distinct encoders at each transmitter of a RAC. Under permutation-invariance (<ref>) and identical encoding, the decoder cannot distinguish which transmitter sent each of the decoded messages. Maintaining permutation-invariance but replacing identical encoders with a different instance of the same random codebook for each encoder, we get a code that achieves the same first- and second-order terms as in thm:ach, with a decoder that can also associate the corresponding transmitter identity to each decoded message. The following definition formalizes the resulting RAC codes.



 
An (M, { (n_k, ϵ_k) }_k = 0^K ) identity-preserving code comprises a collection of encoding functions

    𝖿_k 𝒰× [M] →𝒳^n_K,    k = 1, …, K,

and a collection of decoding functions

    𝗀_k  𝒰×𝒴_k^n_k→{ [M]^k  ×[K]k}∪{𝖾},   k = 0, 1, …, K,

where erasure symbol 𝖾 is the decoder's output when the decoder is not ready to decode.
At the start of each epoch, a random variable U ∈𝒰, with U ∼ P_U, is generated independently of the transmitter activity, and revealed to the transmitters and the receiver for use in initializing the encoders and the decoder. If the set of active transmitters 𝒜⊆ [K] satisfies |𝒜| = k > 0, i.e., k transmitters are active, then the messages of 𝒜 and their corresponding transmitter identities are decoded correctly at time n_k, with probability at least 1-ϵ_k, i.e.,

    1/M^k   ∑_w_𝒜∈ [M]^kℙ[𝗀_k(U, Y_k^n_k)≠ (w_𝒜, 𝒜)⋃
       .⋃_t = 0^k-1𝗀_t(U, Y_k^n_t) ≠ | . W_𝒜 = w_𝒜] ≤ϵ_k,

where W_𝒜 are the independent and equiprobable messages of the transmitters in 𝒜, and the given probability is calculated using the conditional distribution P_Y_k^n_k | X_𝒜^n_k = P_Y_k | X_𝒜^n_k where X_i^n_k = 𝖿_i(U, W_i)^n_k, i ∈𝒜. If 𝒜 = ∅, then the probability that at time n_0 the receiver decodes to the unique message in set [M]^0 = {0} is no smaller than 1-ϵ_0. That is,

    𝗀_0(U, Y_0^n_0) ≠ | W_[0] = ≤ϵ_0.

 



If we continue to assume 
permutation-invariance (<ref>) and to employ
the same input distribution P_X at all encoders, then
the channel output statistics again depend on
the dimension of the channel input
but not on the identity of the active transmitters. In this case, we can apply the proof from the identical-encoding single-threshold-decoding argument in sec:codedesign to derive an achievability result for the general case.[This simple argument was suggested by Dr. Jonathan Scarlett.] In particular, consider a code with K M (rather than M) messages. Replacing M by KM in thm:ach implies that our RAC code with identical encoders gives a penalty of -k log K on the right-hand side of the rate bound (<ref>). Suppose that we use this identical-encoding code to design a general code in which codewords indexed from (t-1)M + 1 to t M are used exclusively by transmitter t for t = 1, …, K. Since each message belongs to a single transmitter, the list of decoded messages reveals the identities of the active transmitters. Under this allocation of codewords, the repetition error ℙ_rep in (<ref>) disappears since transmitters send messages from distinct sets. The error probability from decoding the wrong codeword values decreases since there are fewer legitimate codeword combinations to consider. Therefore, in the case where K is a finite constant and the receiver decodes both messages and transmitter identities, the first three terms in (<ref>) are preserved, and the penalty -k log K only affects the constant term O(1) in (<ref>).

When applied to a scenario with M = 1 and identity decoding, the bound in thm:nonasymp, modified as described in the preceding paragraph, extends the non-asymptotic achievability bound in the group testing problem <cit.> to the scenario where an unknown number k out of a total of K items are defective. 

In the scenario considered in <cit.>, the number of defective items k is known, and our MAC bound 

(<ref>) with K replaced by k, M replaced by KM = K, and the term K(K-1)/2M removed applies.





The resulting bound is similar to <cit.>. The difference is that the bound in (<ref>) uses a single information density threshold rule, while <cit.> uses 2^k-1 simultaneous information density threshold rules.




 §.§ Per-user Probability of Error
 
We extend the definition of the PUPE from <cit.> to the RAC with k ∈ [K] active transmitters as

    e_k ≜1/M^k∑_w_[k]∈ [M]^k∑_i = 1^k 1/kw_i ∉𝗀_T(U, Y_k^n_T) | W_[k] = w_[k],

where Y_k^n_T is the received output at time n_T, and

    T ≜min{t ∈{0}∪ [K] 𝗀_t(U, Y_k^n_t) ≠𝖾}

is the random variable describing the decoder's estimate of the number of active transmitters.[Note that the joint error probability in (<ref>) can likewise be written as

    1/M^k∑_w_[k]∈ [M]^k𝗀_T(U, Y_k^n_T) π≠ w_[k] | W_[k] = w_[k].
]
We set T = K if 𝗀_t(U, Y_k^n_t) = 𝖾 for all t ∈{0}∪ [K]. For k = 0, we define e_0 ≜𝗀_0(U, Y_0^n_0) ≠ | W_[0] = as in (<ref>).

For a RAC with a total of K transmitters and a MAC with K transmitters, the following corollary to thm:nonasymp gives non-asymptotic achievability bounds under the PUPE criterion (<ref>). 

Fix constants γ_0, λ_s, t^k ≥ 0, and γ_t > 0 for all 1 ≤ s ≤ t ≤ k. For any k and n, let (X_[k]^n, X̅_[k]^n, Y_k^n) be a random sequence drawn i.i.d. ∼ P_X_[k]X̅_[k] Y_k(x_[k], x̅_[k], y_k) = ( ∏_i = 1^k P_X(x_i) P_X(x̅_i) ) P_Y_k|X_[k](y_k | x_[k]).


  * For any RAC {(^k, P_Y_k | X_[k](y_k|x_[k]), _k)}_k=0^K satisfying (<ref>) and (<ref>), any K ≤∞, and any fixed input distribution P_X, there exists an (M, { (n_k, e_k) }_k = 0^K ) RAC code under the PUPE criterion (<ref>) such that

    e_0 ≤ h(Y_0^n_0) > γ_0  ,

and for all k≥ 1,
		rCl
        
        *
        e_k    ≤    [_k(X_[k]^n_k; Y_k^n_k) ≤logγ_k]  

              +    h(Y_k^n_0) ≤γ_0    + k(k-1)/2M 

              +∑_t = 1^k - 1 k-1t [_t(X_[t]^n_t; Y_k^n_t) > logγ_t ]   

              +∑_t = 1^k ∑_s = 1^t-1 k-1t-s  ℙ[_t(X_[s+1:t]^n_t; Y_k^n_t) 

                > n_t 𝔼 [_t(X_[s+1:t]; Y_k) ] + λ_s, t^k ]  

              + ∑_t = 1^k∑_s = 1^t k-1t-s M-ks  

                 ℙ [_t( X̅_[s]^n_t ; Y_k^n_t | X_[s+1: t]^n_t)  

                > logγ_t - n_t 𝔼 [_t(X_[s+1:t]; Y_k)]  - λ_s, t^k ].  

  * For a MAC with K transmitters satisfying (<ref>), there exists a MAC code for M messages and decoding blocklength n_K such that
rCl
    e_K    ≤    [_K(X_[K]^n_K; Y_K^n_K) ≤logγ_K] + K(K-1)/2M 

                + ∑_s = 1^K-1 K-1K-s ℙ[_K(X_[s+1:K]^n_K; Y_K^n_K) 

                  > n_K 𝔼 [_K(X_[s+1:K]; Y_K) ] + λ_s, K^K ]  

                + ∑_s = 1^K K-1K-s M-Ks  

                ℙ [_K( X̅_[s]^n_K ; Y_K^n_K | X_[s+1: K]^n_K) > logγ_K 

                  - n_K 𝔼 [_K(X_[s+1:K]; Y_K) ] - λ_s, K^K ]. 



 
Notice that in (<ref>), the only modification from thm:nonasymp is the replacement of the coefficients kt in (<ref>) and kt-s in (<ref>)–(<ref>) by the coefficients k-1t and k-1t-s, respectively. To see how cor:pupe is derived from thm:nonasymp, observe that the PUPE (<ref>) measures the fraction of transmitted messages missing from the list of decoded messages. Therefore, to bound the PUPE for the RAC, we can multiply the error probability bounds in (<ref>) that correspond to the case where t out of k messages are decoded by k-(t-s)/k, where s is the number of messages decoded incorrectly. 

Similarly, under the PUPE, the coefficient KK-s in the K-transmitter MAC bound (<ref>) is replaced by K-1K-s in (<ref>) since we can multiply the error probability bounds in (<ref>)–(<ref>), corresponding to the case where s out of K messages are decoded incorrectly, by s/K.



From the proof of thm:ach, the error probability bounds in (<ref>)–(<ref>) behave as O(1/√(n_k)). This implies that under the PUPE criterion (<ref>), our encoding and decoding scheme described in sec:codedesign achieves the same first three order terms as thm:ach. Only the constant O(1) term in (<ref>) is affected by the change from the joint error probability to the PUPE.












The PUPE criterion becomes critical in applications of the Gaussian RAC with K →∞, where the energy per bit (nP/2 log_2 M) and the number of bits sent by each transmitter (log_2 M) are fixed as the blocklength n grows, and all K transmitters are active. In <cit.>, Polyanskiy shows that in this regime, the joint error probability goes to 1 as K →∞. As we saw in (<ref>), the
PUPE introduces scaling factors s/K in front of the error terms corresponding to s out of K messages decoded incorrectly, for s = 1, …, K. In the regime K →∞, the number of these terms is infinite, and the PUPE can be strictly less than 1 even as the joint error probability approaches 1. In <cit.>, Polyanskiy shows that the PUPE behaves nontrivially in this regime.




















§ TESTS FOR NO ACTIVE TRANSMITTERS
 
In this section, we give an analysis of the error probabilities of the composite binary hypothesis test that we use to decide between H_0: “no active transmitters," and H_1: “k ∈ [K] active transmitters;" that is 

    H_0: Y^n_0∼ P_Y_0^n_0
       H_1: Y^n_0∼ P_Y_k^n_0 1 ≤ k ≤ K.

In the context of thm:nonasymp, the maximal number of transmitters, K, can be infinite. In that case, enumerating all alternative possibilities as in (<ref>) becomes infeasible, and a universal (goodness-of-fit) test

    H_0 Y^n∼ P_Y_0^n
       H_1 Y^n P_Y_0^n

is appropriate.

 Following <cit.>, a test statistic h_n 𝒴^n ↦ℝ is a function that maps the observed sequence y^n to a real number used to measure the correspondence between that sequence and the null hypothesis. A (randomized) test corresponding to the test statistic h_n is a binary random variable that depends only on h_n(Y^n). The test is deterministic if it outputs H_0 if h_n(y^n) ≤γ_0 for some constant γ_0, and H_1 otherwise.
 
Type-I and type-II errors corresponding to a deterministic test with the statistic h_n are defined as

    α(h_n)    ≜ P_Y_0[h_n(Y^n) > γ_0] 
    β(h_n)    ≜ Q[h_n(Y^n) ≤γ_0],

where Q is the unknown alternative distribution of Y, and γ_0 is a constant determined by the desired error criterion. Throughout the following discussion and in our application of these results in lem:test, we employ deterministic tests. For these deterministic tests, we choose γ_0 to ensure that we meet the zero-transmitter error bound α(h_n) ≤ϵ_0, and then we show that β(h_n) decays exponentially with n for each Q in {P_Y_1, …, P_Y_K} to ensure (<ref>) in thm:ach. 

In Sections A and B, below, we consider Hoeffding's test and the Kolmogorov-Smirnov test as possible hypothesis tests for recognizing the zero-transmitter scenario. Both tests are universal in the sense that the test statistic does not vary with the alternative output distributions P_Y_1, …, P_Y_K. They both give an exponentially decaying type-II error for a fixed type-I error ϵ_0 ∈ (0, 1). The disadvantage of Hoeffding's test is that its traditional form requires the channel output alphabet to be finite for every k (as in the adder-erasure RAC in (<ref>)); the advantage of Hoeffding's test is that it achieves the same exponent as the Neyman-Pearson Lemma, which is optimal for a given collection of output distributions P_Y_1, …, P_Y_K, but is not universal, meaning that a different test statistic is necessary for each collection {P_Y_k k ∈ [K]}. In contrast to Hoeffding's test, the Kolmogorov-Smirnov test does not require 𝒴 to be finite; however, when applied to a setting with finite 𝒴, it achieves a type-II error exponent that is inferior to that achieved by Hoeffding's test.

In Section <ref>, we compare the performances of these universal test statistics to that of the log-likelihood ratio (LLR) threshold test, which is third-order optimal in terms of the type-II error exponent for composite hypothesis testing <cit.> and relies explicitly on alternative output distributions P_Y_1, …, P_Y_K.




 §.§ Hoeffding's Test

Denote the empirical distribution of an observed sequence y_1, …, y_n by

    P̂_y^n(a) ≜1/n∑_i = 1^n 1{y_i = a}  ∀  a ∈𝒴.


Hoeffding's test is based on the relative entropy, denoted by D(··), between P̂_y^n and P_Y_0, giving the test statistic

    h_n^H(y^n) = D(P̂_y^n P_Y_0).

Note that if P_Y_0 is a continuous distribution, h_n^H(y^n) = +∞.


	Let 𝒴 be a finite set, and let Q be an unknown alternative distribution for Y_0. If P_Y_0 is absolutely continuous with respect to Q, and P_Y_0≠ Q, then the type-I and type-II errors of Hoeffding's test satisfy
	
    α(h_n^H)    ≤exp{ -n γ_0 + O(log n)}
    β(h_n^H)    ≤exp{ - n inf_P: D(P  P_Y_0) < γ_0 D(P  Q) + O(log n) }.


In <cit.>, a more restrictive assumption (P_Y_0(y) > 0 and Q(y) > 0 for all y ∈𝒴) is used. Absolute continuity is sufficient according to the proofs given in <cit.> and <cit.>, which both rely on Sanov's theorem.
The error exponents of Hoeffding's test coincide with the exponents of the optimal (Neyman-Pearson Lemma) binary hypothesis test. Therefore, Hoeffding's test is asymptotically universally most powerful.

Setting γ_0 = |𝒴| log n/n achieves type-I error ϵ_0 → 0 as n →∞; therefore, the type-I error condition is satisfied for any ϵ_0 > 0 and sufficiently large n. Under this choice, type-II error exp{ -n D(P_Y_0 Q) + o(n) } is achieved (see <cit.>). Therefore, in (<ref>), the maximum type-II error decays with exponent 

    C'    = inf_k ∈ [K] D(P_Y_0 P_Y_k) 
       ≥ 2 inf_k ∈ [K]{( sup_x ∈ℝ  | F_k(x) - F_0(x) | )^2 
          + 4/9( sup_x ∈ℝ  | F_k(x) - F_0(x) | )^4 }
       ≥ 2 δ_0^2 + 4/9δ_0^4.

 The inequality in (<ref>) is due to <cit.> and Pinsker's inequality <cit.>. The inequality in (<ref>) follows from (<ref>).

In <cit.>, Zeitouni and Gutman extend Hoeffding's test to continuous distributions. Their test, which also uses the empirical distribution, employs “δ-smoothing" of the decision regions obtained by a relative entropy comparison. The Zeitouni-Gutman test is optimal under a slightly weaker optimality criterion than the standard first-order type-II error exponent criterion. Using <cit.>, it can be shown that the Zeitouni-Gutman test also yields the desired exponentially decaying maximum type-II error.



 §.§ Kolmogorov-Smirnov Test


The Kolmogorov-Smirnov test <cit.> relies on the empirical CDF 

    F̂^(n)(x|y^n) ≜1/n∑_i = 1^n 1{y_i ≤ x}  ∀  x∈ℝ

of the observed sequence y_1, …, y_n ∈ℝ. The Kolmogorov-Smirnov test uses a deterministic test

    h^KS_n(y^n) =  sup_x ∈ℝ | F̂^(n)(x|y^n) - F_0(x) |

to test whether the observed sequence y^n is well-explained by P_Y_0 with the CDF F_0.

The following theorem bounds the probability that the Kolmogorov-Smirnov statistic exceeds a threshold γ_0.
 
Let Y_1, …, Y_n be drawn i.i.d. according to an arbitrary distribution P_Y_0 with the CDF F_0 on ℝ. For any n ∈ℕ and γ_0 > 0, it holds that

    α(h^KS_n) ≤ 2 exp{-2 n γ_0^2}.


In <cit.>, Dvoretzky et al. prove thm:DKW with an unspecified multiplicative constant C in front of the exponential on the right side of (<ref>). In <cit.>, Massart establishes that C = 2. 




In our operational regime of interest, we set the type-I error to a given constant ϵ_0, which by thm:DKW corresponds to setting the threshold γ_0 to

    γ_0 = √(log2/ϵ_0/2 n) = O(1/√(n)).

We next bound the type-II errors for every k ∈ [K]. For each k ∈{0, …, K}, let F_k denote the CDF of P_Y_k. 
The type-II error when k ≥ 1 transmitters are active is bounded as

    β_k(h_n^KS)    = sup_x ∈ℝ | F̂^(n)(x|Y_k^n) - F_0(x) | ≤γ_0
       ≤ℙ[ sup_x ∈ℝ(| F_k(x) - F_0(x) | 
          - | F̂^(n)(x|Y_k^n) - F_k(x) | ) ≤γ_0 ] 
       ≤ℙ[ sup_x ∈ℝ | F̂^(n)(x|Y_k^n) - F_k(x) | 
         ≥sup_x ∈ℝ  | F_k(x) - F_0(x) |  - γ_0 ]
       ≤ 2 exp{-2 n  (sup_x ∈ℝ  | F_k(x) - F_0(x) | )^2 
          + O(√(n))},

where (<ref>) follows from triangle inequality |x + y| ≥ |x| - |y|, and (<ref>) follows from thm:DKW and (<ref>). Applying (<ref>) to (<ref>), we conclude that the maximum type-II error in (<ref>) decays exponentially with n, with exponent 

    C'    = 2 inf_k ∈ [K]( sup_x ∈ℝ  | F_k(x) - F_0(x) | )^2 
       ≥ 2 δ_0^2.

Comparing (<ref>) and (<ref>), from (<ref>), we see that the type-II error exponent achieved by the Kolmogorov-Smirnov test is always inferior to that achieved by Hoeffding's test.
































































 





 §.§ The Optimal Composite Hypothesis Test
 

From (<ref>) and (<ref>), we know that there exists a positive constant c_0 such that 

    n_0 ≥ c_0 log n_1 + o(log n_1)

suffices to meet the error requirements of the composite hypothesis test given in (<ref>) and (<ref>). Since the proposed tests are universal, thm:nonasymp allows us to decode any message set of k ≤ K active transmitters without knowing the total number of transmitters, K. In this section, we find the smallest first three terms on the right side of (<ref>) that we can achieve when K is finite and we allow the composite hypothesis test to depend on the distributions P_Y_1, …, P_Y_K. 

Let β_ϵ_0(P_Y_0, {P_Y_k}_k = 1^K) denote the minimax type-II error among the alternative distributions P_Y_1, …, P_Y_K such that type-I error (under P_Y_0) does not exceed ϵ_0; that is,

    β_ϵ_0(P_Y_0, {P_Y_k}_k = 1^K) ≜min_h_n: α(h_n) ≤ϵ_0max_ k ∈ [K] β_k(h_n),

where the minimum is over all tests including deterministic and randomized tests.

The LLR test statistic h_n^LLR 𝒴^n ↦ℝ^K is given by

    h_n^LLR(y^n) = ∑_i = 1^n h_1^LLR(y_i),

where

    h_1^LLR(y) ≜[ logP_Y_0(y)/P_Y_1(y); logP_Y_0(y)/P_Y_2(y);                    ⋮; logP_Y_0(y)/P_Y_K(y) ].

Given a threshold vector τ∈ℝ^K, the corresponding LLR test outputs H_0 if h_n^LLR(y^n) ≥τ, and H_1 otherwise. 











The gap in the type-II error exponent (C' in (<ref>)) between the general optimal tests and the LLR tests with the optimal threshold vector τ is O(1/n) <cit.>; therefore, we only consider minimizing over the LLR tests in (<ref>) for asymptotic optimality.

Denote by 𝐃 and 𝖵 the mean and covariance matrix of the random vector h_1^LLR(Y_0), respectively. Define 

    D_min   ≜min_k ∈ [K] D(P_Y_0 P_Y_k) 
    ℐ_min   ≜{k ∈ [K]  D(P_Y_0 P_Y_k) = D_min}
    𝖵_min   ≜Cov[(h_1^LLR(Y_0))_ℐ_min] ∈ℝ^ |ℐ_min| ×  |ℐ_min|.

The following theorem gives the asymptotics of the minimax type-II error defined in (<ref>). 
 
Assume that P_Y_0 is absolutely continuous with respect to P_Y_k, 0  < D(P_Y_0P_Y_k) < ∞ for k = 1, …, K, 𝖵 is positive definite,  and T =  𝔼[ ‖ h_1^LLR(Y_0) - 𝐃‖_2^3 ] < ∞. Then for any ϵ_0 ∈ (0, 1), the asymptotic minimax type-II error satisfies

    β_ϵ_0(P_Y_0, {P_Y_k}_k = 1^K) 
       = exp{-nD_min + √(n) b 
          -1/2log n + O(1) },

where b is the solution to

    𝐙≤ b1 = 1 - ϵ_0,

for 𝐙∼𝒩(0, 𝖵_min) ∈ℝ^| ℐ_min |. Moreover, the minimax error in (<ref>) is achieved by a LLR test with some threshold vector τ.


See app:hypothesis.







Rewriting (<ref>), defining b as given in (<ref>), and using the condition in (<ref>) with any fixed E_k, we see that a decision about whether any of the transmitters are active can be made at time 

    n_0    = 1/2 D_minlog n_1 + b/√(2D_min^3)√(log n_1)
          - 1/2 D_minloglog n_1 + O(1)

while guaranteeing both that the probability that we do not decode at time n_0 when no transmitters are active does not exceed ϵ_0 and that the probability that we decode at time n_0 when k > 0 transmitters are active does not exceed E_k/√(n_k). Note that E_k only affects the constant term O(1) in (<ref>).
thm:huangmoulin implies that the coefficients in front of log n_1, √(log n_1), and loglog n_1 in (<ref>) are optimal. Juxtaposing (<ref>) and (<ref>), we see that Hoeffding's test achieves the optimal first-order error exponent (that is, the optimal coefficient in front of log n_1).



§ CONCLUSION
 
We study the agnostic random access model, in which each transmitter knows nothing about the set of active transmitters beyond what it learns from limited scheduled feedback from the receiver, and the receiver knows nothing about the set of active transmitters beyond what it learns from the channel output. In our proposed rateless coding strategy, the decoder attempts to decode only at a fixed, finite collection of decoding times. At each decoding time n_t, it sends a single bit of feedback to all transmitters indicating whether or not its estimate for the number of active transmitters is t. We prove non-asymptotic and second-order achievability results for the equal rate point (R, …, R) under our assumptions on the channel (permutation-invariance (<ref>), reducibility (<ref>), friendliness (<ref>), and interference (<ref>)). For a nontrivial class of discrete, memoryless RACs, our proposed RAC code performs as well in its capacity and dispersion terms as the best-known code for the discrete memoryless MAC in operation; that is, it performs as well as if the transmitter set were known a priori. The assumptions of permutation-invariance (<ref>), reducibility (<ref>), and interference (<ref>) together with our use of identical encoding guarantee (by lem:mutualinfo) that the equal rate point always lies on the sum-rate boundary rather than on one of the corner points. For example, for two users, the capacity region is a symmetric pentagon. This ensures that our simplified, single-threshold decoding rule results in no loss in the first- or second-order achievable rate terms, making the codes far more practical than prior schemes <cit.> in which decoders employ 2^k -1 simultaneous threshold-rules. In sec:transiden, we show that as long as K < ∞, there is no loss in the first two terms even if the decoder is tasked with decoding transmitter identity.

We also provide a tight approximation for the capacity and dispersion of the adder-erasure RAC (<ref>), which is an example channel satisfying our symmetry conditions. 

In order to decide whether there are any active transmitters without enumerating all K alternative hypotheses, we analyze universal hypothesis tests. Results are given both for the case where the channel output alphabet is finite and the case where the channel output alphabet is countably or uncountably infinite. Using existing literature, it is possible in both cases to obtain exponentially decaying maximum type-II error under the condition that sup_x ∈ℝ |F_k(x) - F_0(x)| ≥δ_0 > 0   for all  k ∈ [K]. We also derive the best third-order asymptotics of the minimax type-II error (thm:huangmoulin).



We conclude the paper by giving some directions for generalizations and future work.


    
  * Achievability of unequal rate points: While identical encoding is appealing from a practical perspective, it is also possible to design codes with different transmitters operating at different rates. Such codes would employ non-identical encoding at the transmitters, and they could also employ a decoding rule with multiple, simultaneous threshold rules. In <cit.>, Chen et al. use a similar strategy to derive third-order achievability and converse results for the random access source coding problem where operation at both identical and distinct rates is allowed.
    
  * Unordered decoding times:
    Example scenarios where unordered decoding times can arise include channels that do not satisfy the assumptions (<ref>) or (<ref>), applications characterized by small message sizes (e.g., in the internet of things), and scenarios where the system designer chooses unordered decoding times (e.g., when a quick error is preferable to a long period of low individual data rates caused by unusually high traffic in the network). It is easy to modify our nonasymptotic bound (thm:nonasymp) to capture the case where n_0, …, n_K are unordered.
    
  * Non-i.i.d. input distributions at the random encoders: Our random coding design generalizes to scenarios where an arbitrary input distribution P_X^n_K is employed instead of P_X×⋯× P_X. For example, in <cit.>, we improve the achievable second- and third-order term for the Gaussian RAC by employing uniform distributions over spheres instead of i.i.d. distributions. To prove <cit.>, random codewords are formed by concatenating K independent sub-codewords,
    drawn from uniform distributions over the power spheres with dimensions n_1, n_2-n_1, …, n_K-n_K-1. This non-product input distribution satisfies the maximal power constraints for all decoding times n_1, n_2, …, n_K. 
    More broadly, non-stationary input distributions can arise in communication over RACs where no single P_X simultaneously maximizes all mutual informations I_k. While we explore in sec:choosinginput how to choose the “best" single-letter input distribution P_X for this scenario, it is possible to employ different input distributions for each of the sub-codewords n_1, n_2-n_1, …, n_K - n_K-1 to achieve higher rates. 

    
  * Fading channels:  A rateless code design for quasi-static fading RACs where the channel fading coefficients are unavailable either at the transmitters or at the receiver would constitute one of the most practically relevant extensions of this work. In the quasi-static fading channel model with a fixed blocklength, the achievable rate is dictated by a quantity called the outage probability<cit.>. If the fading coefficient is small in a communication epoch, then the channel is declared to be in outage and reliable communication is not achieved. However, using rateless codes, it is possible to maintain reliable communication at the expense of reduced rates (i.e., larger decoding times) when the fading coefficient is small while achieving larger rates when the fading coefficient is large. While Kowshik et al. <cit.> derive achievability results for the quasi-static fading RAC in the fixed blocklength regime under the PUPE (<ref>) criterion, rateless coding over fading RACs is yet to be fully explored.







§ PROOFS OF LEMMAS <REF>–<REF>
 


We first state and prove Lemma <ref>, which we then use to prove Lemmas <ref>, <ref>, and <ref> (in that order).
 
Let X_1, X_2, …, X_k be i.i.d., and let the interference (<ref>), permutation-invariance (<ref>), and reducibility (<ref>) assumptions hold. Then I_k(X_i ; Y_k | X_[i-1]) is strictly increasing in i, i.e., for all i < j ≤ k,

    I_k(X_i ; Y_k | X_[i-1]) < I_k(X_j ; Y_k | X_[j - 1]) .


[Proof of lemma:mutualincrease]
By permutation-invariance (<ref>) and the i.i.d. distribution of X_1, …, X_k, we have

    I_k(X_i ; Y_k | X_[i-1]) = I_k(X_j ; Y_k | X_[i - 1]).

Let (U, V, T) be mutually independent random variables. Then I(U; V) = I(U; T, V) = 0. Since I(U; T, Y ) ≤ I(U; T, V, Y), the chain rule
implies that

    I(U; Y | T) ≤ I(U; Y | T, V).

Setting U to X_j, Y to Y_k, T to X_[i-1], and  V to X_[i: j-1] in (<ref>) and then applying (<ref>) gives (<ref>) with < replaced by ≤. Equality in  (<ref>) is attained if and only if U and V are conditionally independent given (Y, T). As a result, equality in our modified form of (<ref>) occurs if and only if X_j and X_[i:j-1] are conditionally independent given (Y_k, X_[i-1]). We proceed to show that this is not possible using a proof by contradiction.

Assume that X_j and X_[i:j-1] are conditionally independent given (Y_k,  X_[i -1]), i.e.,

    P_X_[i:j] | Y_k, X_[i-1] = P_X_[i:j-1] | Y_k, X_[i - 1]  P_X_j | Y_k, X_[i - 1].

Set X_[i-1] = 0^i-1 and use Bayes' rule to show 

    P_X_[i:j] | Y_k, X_[i-1] = 0^i-1   = P_X_[j - (i-1)] | Y_k - (i-1)
    
    P_X_[i:j-1] | Y_k, X_[i-1] = 0^i-1   = P_X_[2:j-(i-1)] | Y_k - (i-1)
    
    P_X_j | Y_k, X_[i-1] = 0^i-1   = P_X_1 | Y_k - (i-1)

due to reducibility (<ref>), permutation-invariance (<ref>), and the i.i.d. distribution of X_1, …, X_k. 
Therefore, (<ref>) implies that X_1 and X_[2:j-(i-1)] are conditionally independent given Y_k-(i-1), which is not possible by interference assumption (<ref>). 



















[Proof of lem:mutualinfo]
We wish to show that

    1/kI_k(X_[k];Y_k)<1/s I_k(X_[s];Y_k|X_[s+1:k]) .

 By the chain rule for mutual information, the left-hand side of (<ref>) equals the average of k terms

    1/kI_k(X_[k];Y_k)=1/k∑_i=1^kI_k(X_i;Y_k|X_[i-1]).

By permutation-invariance (<ref>) and the chain rule, the right-hand side of (<ref>) equals the average of the last s of those k terms

    1/s I_k(X_[s];Y_k|X_[s+1:k])
       = 1/s I_k(X_[k-s+1:k];Y_k|X_[k-s]) 
       = 1/s∑_i=k-s+1^k I_k(X_i;Y_k|X_[i-1]).

Since the terms in these averages are strictly increasing in i by lemma:mutualincrease, we have the desired result.


[Proof of lem:mutualinfofriendly]
We wish to show that 1/s I_s > 1/k I_k. We proceed by representing I_s in terms of I_k as

    1/s I_s    = 1/s I_k(X_[s]; Y_k | X_[s+1:k] = 0^k-s) 
       ≥1/s I_k(X_[s]; Y_k | X_[s+1:k]) 
       > 1/k I_k,

where (<ref>) follows from reducibility (<ref>), (<ref>) follows from friendliness (<ref>), and (<ref>) follows from lem:mutualinfo.


[Proof of lemma:expectation]
To derive the bound 𝔼[_t(X_[s]; Y_k)] ≤ I_k(X_[s]; Y_k) < I_t(X_[s]; Y_t), we write
rCl
𝔼[_t(X_[s]; Y_k)] 
   =    [logP_Y_t | X_[s] (Y_k | X_[s]) /P_Y_t(Y_k) ]

   =    -D(P_X_[s] P_Y_k|X_[s]   P_X_[s] P_Y_t|X_[s])  

       + D(P_Y_k  P_Y_t)  

       + D(P_X_[s] P_Y_k|X_[s]   P_X_[s] P_Y_k ) 

   =    -D( P_X_[s] P_Y_k|X_[s]   P_X_[s] P_Y_t|X_[s] )  

      + D(P_Y_k  P_Y_t)  + I_k(X_[s]; Y_k)  

   ≤    I_k(X_[s]; Y_k) 

   =    ∑_i = 1^s I_k(X_i; Y_k | X_[i-1])  

   <    ∑_i = 1^s I_k(X_i; Y_k | X_[i-1], X_[s+1:s+k-t])  

   =    I_k(X_[s]; Y_k | X_[t+1:k]) 

   ≤    I_k(X_[s]; Y_k | X_[t+1:k] = 0^k-t) 

   =    I_t(X_[s]; Y_t),   

where (<ref>) follows from data processing inequality of relative entropy (e.g., <cit.>), (<ref>) follows from the chain rule, (<ref>) follows from permutation-invariance (<ref>) and  lemma:mutualincrease, (<ref>) follows from permutation-invariance (<ref>) and the chain rule, and (<ref>) and (<ref>) follow from friendliness (<ref>) and reducibility (<ref>), respectively.

































§ ACHIEVABLE RATES ON THE SUM-RATE BOUNDARY OF A MAC

[Proof of (<ref>)]
	For the 2-transmitter MAC, the second-order achievability region is expressed in terms of dispersion matrix, 𝖵_2, defined as the covariance matrix of the random vector
	
    _2 ≜[ _2(X_1; Y| X_2); _2(X_2; Y| X_1); _2(X_1, X_2; Y) ].

	
	Let 𝐙 be a k-dimensional Gaussian vector with mean 0 and covariance matrix 𝖵. For ϵ∈ (0, 1), define the multidimensional counterpart of the Q^-1(·) function
	
    𝒬_inv(𝖵, ϵ) ≜{τ∈ℝ^k : 𝐙≤τ≥ 1 - ϵ}.

	It is shown in <cit.> that the achievable rate region satisfies
	
    (R_1, R_2): [       R_1;       R_2; R_1 + R_2 ]   ⊇⋃_P_X_1, P_X_2{_2 - 1/√(n) Q_inv(𝖵_2, ϵ) 
       + O( log n/n) 1}.

	Let (R_1, R_2) converge to a point on the sum-rate boundary, i.e., R_1 = D_1 + 1/√(n) L_1 + O ( log n/n) and R_2 = D_2 + 1/√(n) L_2 + O ( log n/n), where
	
    D_1    = λ I_2(X_1; Y) + λ̅ I_2(X_1; Y | X_2) 
    
    	D_2    = λ̅ I_2(X_2; Y) +  λ I_2(X_2; Y | X_1),

	for some 0 < λ < 1, and λ̅ = 1- λ. We are going to prove that under this condition, (<ref>) and (<ref>) are equivalent. The proof is similar to <cit.>, which proves the reduction for Gaussian MACs on the sum-rate boundary. 
	
	For any nontrivial MAC, we have
	
    Δ_1    = I_2(X_1; Y | X_2) - I_2(X_1; Y) > 0 
    Δ_2    = I_2(X_1; Y | X_2) - I_2(X_1; Y) > 0.

	
	We consider a Gaussian random vector 𝐙 = (Z_1, Z_2, Z_3) ∼𝒩(0, 𝖵_2) ∈ℝ^3. Due to the definition of Q_inv(𝖵, ϵ) in (<ref>) and (<ref>), 𝐙 satisfies
	
    1-ϵ
       ≤ℙ[ 𝐙≤√(n)[         I_2(X_1; Y| X_2) - R_1;        I_2(X_2; Y | X_1) - R_2; I_2(X_1, X_2; Y) - (R_1 + R_2) ]. 
          +  O ( log n/√(n)) 1] 
       = ℙ[ 𝐙≤[  √(n)λΔ_1 - L_1; √(n)λ̅Δ_2 - L_2;    -(L_1 + L_2) ]] +  O ( log n/√(n)),

	where (<ref>) follows from (<ref>) and Taylor expansion of Q_inv(𝖵, ·). 	Denote
	
    p_diff≜Z_3 ≤ -(L_1 + L_2) - 
    	ℙ[ 𝐙≤[  √(n)λΔ_1 - L_1; √(n)λ̅Δ_2 - L_2;    -(L_1 + L_2) ]] 
       = ℙ[Z_1 > √(n)λΔ_1 - L_1∪Z_2 > √(n)λΔ_2 - L_2
         ∩{Z_3 ≤ -(L_1 + L_2)}] 
       ≤exp-cn
       = O ( log n/√(n)),

	for some c > 0 constant, where (<ref>) follows from Chernoff bound on Gaussian random variables and union bound. This implies that (<ref>) is equivalent to
	
    1 - ϵ≤Z_3 ≤ -(L_1 + L_2) + O ( log n/√(n)),

	where Z_3 ∼𝒩(0, V_2), which proves the claim in (<ref>). In thm:ach, notice that I_2(X_1; Y| X_2) > I_2(X_1; Y) follows from lem:mutualinfo and that we pick the symmetrical rate point R_1 = R_2.
 




§ PROOF OF LEM:SCARLETT


To prove lem:scarlett, we first derive the saddle point condition for the MAC.

    Let 𝒫_1 and 𝒫_2 be convex set of distributions on alphabets 𝒳_1 and 𝒳_2, respectively. Suppose that there exists a product distribution P_X_1^* P_X_2^* such that
    
    sup_P_X_1 P_X_2
     P_X_1∈𝒫_1, P_X_2∈𝒫_2 I_2(X_1, X_2; Y_2) = I_2(X_1^*, X_2^*; Y_2^*) = I_2^*,

    where P_Y_2^*|X_1^*, X_2^* = P_Y_2|X_1, X_2. Then, for all P_X_1∈𝒫_1 and for all Q_Y_2, it holds that
    
    D(P_X_1P_X_2^* P_Y_2|X_1, X_2 P_X_1P_X_2^* P_Y_2^*) 
    ≤   I_2^*
    ≤    D(P_X_1^* P_X_2^* P_Y_2|X_1, X_2 P_X_1^* P_X_2^* Q_Y_2).



[Proof of lem:scarlett]
lem:scarlett follows by an application of thm:saddlepoint to the setting where 
𝒫_1 includes the set of all distributions with a singleton on 𝒳_1 having probability 1, i.e., {δ_x_1 x_1 ∈𝒳_1}⊆𝒫_1, and I_2^* < ∞. Particularizing P_X_1 in (<ref>) to any P_X_1 = δ_x_1 with x_1 ∈𝒳_1 yields

    D( P_X_2^* P_Y_2|X_1 = x_1, X_2  P_X_2^* P_Y_2^*) ≤ I_2^*

for all x_1 ∈𝒳_1. Since the left-hand side of (<ref>) is equal to the conditional expectation of _2(X_1^*, X_2^*; Y_2^*) given X_1^* = x_1,
(<ref>) follows with less than or equal to. The equality in (<ref>) follows since otherwise (<ref>) would give the contradiction I_2(X_1^*, X_2^*; Y_2^*) < I_2^*. 


[Proof of thm:saddlepoint]
    The proof of thm:saddlepoint is similar to the proof of the saddle point condition for point-to-point channels in <cit.> and extends <cit.> to the MAC. Although the optimization in (<ref>) is not convex in general <cit.>, the optimization

    sup_P_X_1∈𝒫_1 I_2(X_1, X_2^*; Y_2),

where P_X_1 X_2^* Y_2 = P_X_1 P_X_2^* P_Y_2|X_1, X_2 is convex.

Inequality (<ref>) follows from the golden formula (e.g., <cit.>)

    I_2^*    = D(P_X_1^* P_X_2^* P_Y_2|X_1, X_2 P_X_1^* P_X_2^* P_Y_2^*) 
       = D(P_X_1^* P_X_2^* P_Y_2|X_1, X_2 P_X_1^* P_X_2^* Q_Y_2) - D( P_Y_2^* Q_Y_2)

and the nonnegativity of the relative entropy. Notice that for I_2^* = ∞, (<ref>) is trivial. Assume that I_2^* < ∞. Fix any P_X_1∈𝒫_1. Let λ∈ (0, 1). Set

    P_X_1λ = λ P_X_1 + (1-λ) P_X_1^*∈𝒫_1.
 
Let θ∼Bernoulli(λ), so that P_X_1λ | θ = 0 = P_X_1^* and P_X_1λ| θ = 1 = P_X_1, and let 

    P_X_1λ X_2^* Y_2λ = P_X_1λ P_X_2^* P_Y_2|X_1, X_2.

Then
rCl
    I_2^*    ≥    I_2(X_1λ, X_2^*; Y_2λ)  

       =    D(P_X_1λ P_X_2^* P_Y_2|X_1, X_2  P_X_1λ P_X_2^* P_Y_2λ) 

       =    λD( P_X_1 P_X_2^* P_Y_2|X_1, X_2   P_X_1 P_X_2^* P_Y_2λ) 

           + (1-λ) D(P_X_1^* P_X_2^* P_Y_2|X_1, X_2  P_X_1^* P_X_2^* P_Y_2λ) 

       ≥    λD(P_X_1 P_X_2^*  P_Y_2|X_1, X_2  P_X_1 P_X_2^* P_Y_2λ) 

          + (1-λ) I_2^*, 

where (<ref>) follows from (<ref>). By subtracting (1-λ) I_2^* from both sides of (<ref>) and dividing by λ, we get

    I_2^* ≥ D(P_X_1 P_X_2^* P_Y_2|X_1, X_2 P_X_1 P_X_2^* P_Y_2λ).

By taking lim inf_λ→ 0 in (<ref>) and applying the lower semicontinuity of the relative entropy (e.g., <cit.>), (<ref>) is proved.

Note that (P_X_1^*, P_X_2^*) does not have to be unique for thm:saddlepoint and lem:scarlett to hold.































§ ADDER-ERASURE RAC

Here, we approximate the sum-capacity and dispersion of the adder-erasure RAC for a large number of transmitters (k). 

The optimal input distribution for the adder-erasure RAC defined in (<ref>) is the Bernoulli(1/2) distribution at all encoders. That input distribution achieves the sum-rate capacity, and

    I_k = (1 - δ) ( 1/2logπ e k/2 - log e/12 k^2 )+ O(k^-3)  
       V_k = (1 - δ) [ δ/4log^2 π e k/2 + log^2 e/2  - log^2 e/2 k
          - ( log e/2 + δlogπ e k/2/12) log e/k^2] + O( log k/k^3)  .
  


The calculation leading to thm:ikvk is presented in Lemmas <ref>–<ref>, which rely on Stirling's approximation and the Taylor series expansion.  

Consider a binomial random variable X∼(n, 1/2).
lem:demoivre, below, shows that the probability mass that this Binomial distribution puts at k is well approximated by

    P̃_X(k)    ≜1/√(π n/2) e^-(k - n/2)^2/n/2( 1 + f(k)/n + g(k)/n^2),

where

    f(x)    ≜ -1/12( 2x - n )^4/n^2 + 1/2( 2 x - n )^2/n - 1/4
    
    g(x)    ≜1/288(2 x - n )^8/n^4  - 3/40( 2 x - n )^6/n^3  + 19/48( 2 x - n )^4/n^2
          - 11/24(2 x - n )^2/n + 1/32.

Define the interval

    𝒦≜[n/2 - A/2√(n log n),   n/2 + A/2√(n log n)]

for some constant A > 0. 

 
Let X ∼Binom(n, 1/2). Then for any k ∈𝒦,

    P_X(k) = nk 2^-n = P̃_X(k) ( 1 + O ( log^6 n/n^3) ).


[Proof of lem:demoivre]
We apply Stirling's approximation <cit.> 

    n! = √(2 π) n^n + 1/2 e^-n( 1 + 1/12n + 1/288n^2  + O(n^-3) ),

and a Taylor series expansion of nk around x = 0, where 

    k = n/2 + x/2√(n log n),

to P_X(k) = nk 2^-n, to derive (<ref>).


    ϕ(j) ≜ 1 + 1/12 j + 1/288j^2.

By lem:stirling, we obtain

    nk 2^-n   = 1/√(2 π)2^-n n^n + 1/2/k^k + 1/2 (n-k)^n-k + 1/2
         ·ϕ(n)/ϕ(k) ϕ(n-k) + O(n^-3).

Using (<ref>), we expand the Taylor series around x = 0 of each factor in (<ref>) to get

    ( 2^-n n^n + 1/2/k^k + 1/2 (n-k)^n-k + 1/2) = 1/√(n/4)exp{ -  x^2 log n/2}
       ·( 1 -  x^4 log^2 n/12n +  x^2 log n/2n + x^8 log^4 n/288 n^2 - 3 x^6 log^3 n/40 n^2
        + 3 x^4 log^2 n/8 n^2 + O ( log^6 n/n^3) ) ,

and

    ϕ(n)/ϕ(k) ϕ(n-k) = 1 - 1/4n + 3 - 32x^2 log n/96n^2 + O ( log^2 n/n^3) .


Substituting the Taylor series expansions in (<ref>) and (<ref>) into (<ref>) completes the proof.



Let V(X) 

    V(X)    = Var[ log1/P_X(X)].

denote the varentropy of X.

 
For X ∼Binom(n, 1/2 ), 

    H(X)    = 1/2logπ e n/2 - log e/12n^2 + O(n^-3) 
    
    V(X)    = log^2 e/2  - log^2 e/2n -  log^2 e/2n^2 + O(n^-3).


[Proof of lem:binom]
We denote the centered version of X by 

    X̅≜ X - n/2,

and we calculate its moments as follows: 

    𝔼[X̅^2 ]    = n/4
    𝔼[X̅^4 ]    = n/16 (3n - 2) 
    𝔼[X̅^6 ]    = n/64  (15n^2 - 30 n + 16) 
    𝔼[X̅^8 ]    = n/256 (105n^3 - 420 n^2 + 588 n - 272).


Let T̃(k) denote the first 3 terms of the Taylor series expansion of log1/P̃_X(k) around n/2 evaluated at k, giving

    T̃(k)    ≜1/2 logπ n/2 +  log e ((k-n/2)^2/n/2
          -  f(k)/n + -g(k) + f^2(k)/2/n^2).

Recall the definition of interval 𝒦 from (<ref>). Then we can write the entropy H(X) as
rCl
H(X)    =     ∑_k = 0^n  nk/2^n log( 2^n/nk  )   

   =    T̃(X) 

       +  ( log1/P_X(X)  - T̃(X) ) 1{ X ∈𝒦 }  

       +  ( log1/P_X(X) - T̃(X) ) 1{ X ∉𝒦 } . 

Using the moments of Binom(n, 1/2 ) (e.g., <cit.>), the first term in (<ref>) is 

    T̃(X) =  1/2logπ e n/2 -log e/12n^2.

By lem:demoivre, the second term in (<ref>) is

    ( log1/P_X(X)  - T̃(X) ) 1{ X ∈𝒦} = O ( log^6 n/n^3).

By Hoeffding's inequality, 

    ℙ[X ∉𝒦] ≤ 2 n^-A^2 log e/2,

where A is the constant in (<ref>).
Since the minimum of P_X(k) over k is achieved at k = n, using (<ref>), we get 

    log1/P_X(X)  1{ X ∉𝒦}  = O ( log^6 n/n^3)
 
for A ≥3/√(log e). Similarly, by taking the derivative of T̃(k), one can show that T̃(k) ≤T̃(n) ≤ n for all k ∈ [0, n], which gives 

    T̃(X)  1{ X ∉𝒦}  = O ( log^6 n/n^3).

Combining (<ref>)–(<ref>), (<ref>)–(<ref>) gives 

    H(X) = 1/2logπ e n/2 -log e /12n^2 + O ( log^6 n/n^3) .


Via an argument similar to (<ref>) and (<ref>), we can show that for A ≥4/√(log e), the contribution of k ∉𝒦 to the varentropy is O ( log^6 n/n^3). Therefore, using the moments of Binom(n, 1/2) and lem:demoivre, we can approximate the varentropy V(X) as 

    V(X)    = log^2 1/P_X(X) - (H(X))^2 
        = (T̃(X))^2 - (H(X))^2 + O ( log^6 n/n^3) 
    
    
    
    
    
       =  log^2 e (1/2 - 1/2n - 1/2n^2) + O ( log^6 n/n^3).


The above analyses use the first 3 terms of the Stirling series (<ref>) to obtain the remainder O ( log^6 n/n^3). Applying the same analyses with 4 terms of the Stirling series improves the remainder to O(n^-3), as claimed in (<ref>) and (<ref>) in the statement of lem:binom.

We are now equipped to prove thm:ikvk.
[Proof of thm:ikvk]
Define

    E ≜ 1{Y = 𝖾}.
 
By the chain rule for entropy, we have for the adder-erasure RAC

    I_k(X_[k]; Y_k)    = H(Y_k) - H(Y_k | X_[k]) 
       = H(Y_k, E) - H(E) 
       = H(Y_k | E) 
       = (1-δ) H(Y_k | E = 0).

Given the independent inputs X_i ∼(p_i) for i ∈ [k], H(Y_k | E = 0) is equal to the entropy of the sum of k independent Bernoulli random variables with parameters (p_1, …, p_k), which is maximized when p_i = 1/2 for all i <cit.>. Therefore, for any δ∈ [0, 1], the equiprobable input distribution at all encoders, X_i^* ∼Bernoulli(1/2), maximizes the mutual information I_k(X_[k]; Y_k) for all k. Let (X_[k]^* Y_k^*) ∼ P_X_[k]^* P_Y_k|X_[k]. Then

    I_k(X_[k]^*; Y_k^*) = (1-δ) H(Z),

where Z ∼(k, 1/2), and (<ref>) follows from lem:binom.
Furthermore,

    _k(X^*_[k]; Y_k^*) = 
    0    δ
    log2^k/ki    (1-δ) ki/2^k,     0 ≤ i ≤ k ,

which gives 

    V_k = _k(X^*_[k]; Y_k^*)   = (1-δ) [ V(Z) + δ (H(Z))^2 ],

and (<ref>) follows from lem:binom.




§ BOUND ON THE CARDINALITY |𝒰|


While the analysis in Section <ref> employs common randomness U with |𝒰| = ||^Mn_K, <cit.> shows that |𝒰| ≤ K + 2 suffices to achieve the optimal performance. thm:caratheodory, stated next, improves the cardinality bound on |𝒰| from K + 2 <cit.> to K + 1 by using the connectedness of the set of achievable error vectors defined in (<ref>).
 If an (M, { (n_k, ϵ_k) }_k = 0^K ) RAC code exists, then there exists an (M, { (n_k, ϵ_k) }_k = 0^K ) RAC code with |𝒰| ≤ K + 1. 

[Proof of thm:caratheodory]
	For fixed M, n_0, …, n_K, let G_u denote the set of achievable error vectors compatible with message size M, blocklengths n_0, …, n_K, and cardinality |𝒰| ≤ u; that is,
	
    G_u    = {(ϵ'_0, …, ϵ'_K): ∃ (M, { (n_k, ϵ'_k) }_k = 0^K ) 
          |𝒰| ≤ u }.

	Let G denote the set of achievable error vectors compatible with message size M and blocklengths n_0, …, n_K; that is,
	
    G    = {(ϵ'_0, …, ϵ'_K): ∃ (M, { (n_k, ϵ'_k) }_k = 0^K ) }.

	As observed in <cit.>, G = G_||^Mn_K is the convex hull of G_1. Indeed, every vector (ϵ_0', …, ϵ_K') in G is a convex combination of vectors in G_1, and the coefficients of the convex combination are determined by the distribution of the common randomness random variable U. 
	
	Furthermore, G_1 is a connected set. To see this, take any ϵ_1, ϵ_2 ∈ G_1. For any ϵ' ≥ϵ with ϵ∈ G_1, the line segments L_i = {λϵ_i + (1-λ) 1λ∈ [0, 1]}, i = 1, 2, also belong to G_1, and the path L_1 ∪ L_2 connects ϵ_1 and ϵ_2. Therefore, G_1 is a connected set.
	
	Since G = conv(G_1) ⊂ℝ^K + 1, and G_1 is a connected set, by Fenchel-Eggleston-Carathéodory's theorem <cit.>, G = G_K + 1 holds. Therefore, (ϵ_0, …, ϵ_K) ∈ G implies that (ϵ_0, …, ϵ_K) ∈ G_K + 1.




§ COMPOSITE HYPOTHESIS TESTING
 

We begin with a lemma that is used in the proof of thm:huangmoulin. See fig:qq for an illustration of lem:generalminmax.

Throughout this section,

    𝐙∼𝒩(0, 𝖵).

 
Let 𝐔_1, …, 𝐔_n be zero-mean i.i.d. random vectors in ℝ^d. Assume that the minimum eigenvalue of the covariance matrix 𝖵 = Cov[𝐔_1] satisfies λ_min(𝖵) > 0, and that T = ‖𝐔_1 ‖_2^3  < ∞. Then

    sup_𝒜∈ℭ_d|1/√(n)∑_i = 1^n 𝐔_i ∈𝒜 - ℙ[𝐙∈𝒜] |≤400 d^1/4 T/λ_min(𝖵)^3/2√(n),

where ℭ_d is the set of all convex, Borel measurable subsets of ℝ^d.


The following lemma is the reversed version of <cit.> for random vectors.
 
	Under the assumptions of th:mbe, for any constant vector 𝐂, there exists a constant vector 𝐞 such that

    exp{ -∑_j = 1^n 𝐔_j } 1 {∑_j = 1^n 𝐔_j≥√(n)𝐂}
       ≥exp{-√(n)𝐂- 1/2log n 1+  𝐞},

where vector inequalities are understood element-wise.  


Fix constants c > 0, and t ∈ [d].
By th:mbe, we have

    𝐂≤1/√(n)∑_j = 1^n 𝐔_j  ≤𝐂 + 𝐚_t, n
         ≥𝐂≤𝐙≤𝐂 + 𝐚_t, n - γ/√(n),

where 

    𝐚_t, n = (c, …, c, δ/√(n), c, …, c),

and δ in the t^th coordinate of 𝐚_t, n is a positive constant to be chosen later, and  

    γ =  400 k^1/4 T/λ_min(𝖵)^3/2

is the constant from (<ref>).
For each t, denote the minimum of the pdf of 𝐙 over the set {𝐳 : 𝐂≤𝐳≤𝐂 + 𝐚_t, n} by

    D_t, n≜min_𝐂≤𝐳≤𝐂 + 𝐚_t, nexp{ -1/2𝐳^T 𝖵^-1𝐳}/√((2π)^d |𝖵|).

Since δ/√(n) decreases with n, 

    inf_n D_t, n = D_t, 1 > 0,

and by (<ref>) and (<ref>), we get

    𝐂≤1/√(n)∑_j = 1^n 𝐔_j  ≤𝐂 + 𝐚_t, n≥δ/√(n) c^d-1 D_t, 1 - γ/√(n).
 
We conclude

    exp{ -∑_j = 1^n 𝐔_j }  1 {∑_j = 1^n 𝐔_j≥√(n)𝐂}
       ≥exp{-(√(n)𝐂 + δ1) - 1/2log n 1}(δ c^d-1min_t ∈ [d] D_t, 1 - γ).

To obtain (<ref>), we lower bounded the indicator in (<ref>) by 1{𝐂≤1/√(n)∑_j = 1^n 𝐔_j  ≤𝐂 + 𝐚_t, n}, and used (<ref>).
The proof is completed by picking δ = 1 + γ/c^d-1min_t ∈ [d] D_t, 1.




Let f ℝ^d →ℝ be a continuous function that satisfies coordinate-wise partial ordering, i.e., f(𝐱) ≤ f(𝐲) for any 𝐱, 𝐲∈ℝ^d with 𝐱≤𝐲. Then for any a in the image of f (denoted a ∈Im f), it holds that

    b^⋆ = min_𝐛∈ℝ^d: f(𝐛) ≥ amax_1≤ j ≤ d b_j = min_x ∈ℝ: f(x 1) ≥ a x.










Since a ∈Im f, there exists some 𝐛∈ℝ^d such that f(𝐛) = a. Denote by b_min and b_max the minimum and maximum components of 𝐛, respectively.
Since f is nondecreasing, 
    f(b_min1)≤  a = f(𝐛) ≤ f(b_max1).

Therefore, since the function mapping b to f(b 1) is continuous and nondecreasing, by the intermediate value theorem there exists some b ≤ b_max such that f(b 1) = a. Equation (<ref>) follows.



Let 𝐙∼𝒩(0, 𝖵). Define the multidimensional counterpart of the function Q^-1(·) as

    𝒬_inv(𝖵, ϵ) ≜{𝐳∈ℝ^K : 𝐙≤𝐳≥ 1 - ϵ}.




Under the assumptions of thm:huangmoulin, it holds that

    exp{ -n 𝐃 + √(n)𝒬_inv(𝖵, ϵ_0) - 1/2log n 1 + O(1) 1}
       ⊂ℰ_ϵ_0 (P_Y_0, {P_Y_k}_k = 1^K )  
       ⊂exp{ -n 𝐃 + √(n)𝒬_inv(𝖵, ϵ_0) + o(√(n)) 1}.



Huang and Moulin <cit.> presented thm:huangregion with o(√(n)) term replaced by -1/2log n + O(1) in (<ref>), indicating that the inner and outer bounds on the achievable error vectors match up to the third-order term in the exponent. However, according to the definition in (<ref>), there exists some τ∈ Q_inv(𝖵, ϵ_0) such that τ has an arbitrarily large coordinate. Therefore, the assumption in <cit.> that Q_inv(𝖵, ϵ_0) = O(1) 1 with respect to n, does not hold. We reprove the theorem considering this observation. The achievability part of (<ref>) is unaffected in the new proof. For the converse part of (<ref>), we show that the second-order term in the error exponent remains unchanged, while we cannot confirm that the third-order term is -1/2log n unless the threshold vector satisfies τ = n 𝐃 - O(√(n)) 1.

The proof of the achievability part of thm:huangregion follows an argument similar to <cit.>; the difference is that we use <cit.> due to Polyanskiy et al. instead of <cit.>.
[Proof of the achievability part in (<ref>)]
We prove the achievability using the LLR tests given in (<ref>). Pick any τ = (τ_1, …, τ_K) ∈ n 𝐃 - √(n)𝒬_inv(𝖵, ϵ_0 - γ/√(n)), where γ is defined in (<ref>).
Then by definition of 𝒬_inv(𝖵, ϵ_0) in (<ref>), we have 

    √(n)𝐙≥τ - n 𝐃≥ 1 - ϵ_0 + γ/√(n).

Recall h_n^LLR(y^n) from (<ref>), and let

    𝐒_k = (S_k1, …, S_kK) ≜ h_n^LLR(Y_k^n),

where Y_k^n ∼ P_Y_k^n for k = 0, …, K. By th:mbe, we have

    ℙ[ 𝐒_0 ≥τ ] ≥ 1 - ϵ_0.

Thus, the threshold vector τ satisfies the type-I error condition. Then β_k, the error probability in deciding H_0 when the true distribution is P_Y_k, is bounded as

    β_k    = ℙ[ 𝐒_k ≥τ] 
       = 𝔼[ e^-S_0k 1 {𝐒_0 ≥τ} ]  
       ≤𝔼[ e^-S_0k 1 { S_0k≥τ_k} ] 
       ≤ 2 ( log 2 /√(2 π)+ 12 T_k/σ_k^2) 1/σ_k √(n)exp{-τ_k}
       = exp{ -τ_k - 1/2log n + O(1) },

where (<ref>) follows from a  measure change from P_Y_k to P_Y_0, and (<ref>) follows from <cit.> and the definitions σ_k^2 = Var[ logP_Y_0(Y_0)/P_Y_k(Y_0)] > 0 and T_k = 𝔼[ |logP_Y_0(Y_0)/P_Y_k(Y_0) - D(P_Y_0 P_Y_k) |^3 ] ≤ T < ∞.
By the Taylor series expansion of Q_inv(𝖵, ·), we conclude

    ℰ_ϵ_0 (P_Y_0, {P_Y_k}_k = 1^K ) 
       ⊃exp{ -n 𝐃 + √(n)𝒬_inv(𝖵, ϵ_0) - 1/2log n 1 + O(1) 1}.



The following proof of the converse part of thm:huangregion corrects <cit.>  by taking into account the possibility that Q_inv(𝖵, ϵ_0) may have arbitrarily large coordinates.
[Proof of the converse part (<ref>)]
From <cit.>, the gap in the type-II error exponent between the LLR tests and the optimal tests is O(1/n). Therefore, we only consider the LLR tests in the converse proof. For any LLR test, by definition (<ref>), we have

    ℙ[ 𝐒_0 ≥τ ] ≥ 1 - ϵ_0.

Then, by th:mbe, we have

    √(n)𝐙≥τ - n𝐃≥ 1 - ϵ_0 - γ/√(n),

where γ is the constant defined in (<ref>). By (<ref>),

    τ   ∈ n 𝐃 - √(n)𝒬_inv(𝖵, ϵ_0 + γ/√(n)) 
       = n 𝐃 - √(n)𝒬_inv(𝖵, ϵ_0) + O(1) 1.

Observe that (<ref>) implies that τ≤ n 𝐃 - √(n)𝐂  + o(√(n))1 for some constant vector 𝐂. The type-II error β_k is lower bounded as

    β_k    = ℙ[ 𝐒_k ≥τ] 
       ≥ℙ[ 𝐒_k ≥ n 𝐃 -  √(n)𝐂 + o(√(n))1] 
       = 𝔼[ e^-S_0k 1 {𝐒_0 ≥ n 𝐃 -√(n)𝐂  + o(√(n))1} ]  
       ≥exp{-n D_k+ √(n) C_k + o(√(n)) },

for all k ∈ [K], where 𝐃 = (D_1, …, D_K), 𝐂 = (C_1, …, C_K), and (<ref>) follows from thm:rev47mult.

Define the set of indices

    ℬ≜{k ∈ [K]: τ_k = nD_k - √(n)E_k + o(√(n)) },

for some constants E_1, …, E_K. For all k ∉ℬ, we can express τ_k as

    τ_k = n D_k - g_k(n)√(n) + o(g_k(n)√(n)),

where g_k(n) is a function of n such that lim_n →∞ g_k(n) = ∞ (For any constant ϵ_0 ∈ (0, 1), lim_n →∞ g_k(n) = -∞ is not possible.)

For k ∈ℬ, we can bound the type-II errors as

    β_k    = ℙ[ 𝐒_k ≥τ] 
       ≥exp{-n D_k + √(n) E_k + o(√(n)) },

where (<ref>) follows from (<ref>). We have for k ∉ℬ that

    β_k    = ℙ[ 𝐒_k ≥τ] 
       = exp{-nD_k + h_k(n) √(n)  + o(h_k(n) √(n) ) },

where h_k(n) ≤ g_k(n) by the upper bound in (<ref>), and lim_n→∞ h_k(n) = ∞, since we can pick arbitrarily large C_k for k ∉ℬ in (<ref>).

Define λ = (λ_k: λ_k = E_k   ∀ k ∈ℬ,  λ_k = h_k(n)  ∀ k ∉ℬ). By union bound, (<ref>) and (<ref>),

    ⋃_k = 1^k {Z_k > λ_k}
       ≤⋃_k ∉ℬ{Z_k > h_k(n) }  + ⋃_k ∈ℬ{Z_k > E_k}
       ≤ o(1) + ϵ_0.

Therefore, by Taylor series expansion of Q_inv(𝖵, ·), we obtain that

    λ∈𝒬_inv(𝖵, ϵ_0 + o(1)) =   𝒬_inv(𝖵, ϵ_0) + o(1) 1,

which completes the proof.


Finally, we derive the minimax error in thm:huangmoulin by applying lem:generalminmax to (<ref>).

[Proof of thm:huangmoulin]
For any ϵ_0 ∈ (0, 1), consider all composite hypothesis tests in the form given in (<ref>) that achieve type-I error no greater than ϵ_0. Let

    ℰ_ϵ_0 (P_Y_0, {P_Y_k}_k = 1^K ) ≜{ (e_1, …, e_K) : ∃ a (randomized) test 
       such that
         Decide  H_1 | H_0 ≤ϵ_0, 
         Decide  H_0 | H_1   = e_k, 1 ≤ k ≤ K }

denote the set of type-II errors achievable by these tests.

Huang and Moulin <cit.>[In the converse part of the proof of <cit.>, Huang and Moulin show that for any LLR test (<ref>) with threshold vector τ such that the type-I error is bounded by ϵ_0, it holds that τ = n 𝐃 - √(n)𝐛 + O(1) 1
for some 𝐛∈ Q_inv(𝖵, ϵ_0). Then, it is assumed that 𝐛 = O(1) 1, and <cit.> is applied. However, according to the definition of Q_inv(𝖵, ϵ_0) in (<ref>), 𝐛 can have coordinates growing with n, which violates this assumption. In <cit.>, Chen et al. confirm that the asymptotic expansion in (<ref>) holds. They prove the converse part of the expansion (<ref>) by evaluating a converse bound that they derive in <cit.> for the composite hypothesis testing.


] show that the asymptotic form of the error region defined in (<ref>) is given by
rCl
3l
ℰ_ϵ_0 (P_Y_0, {P_Y_k}_k = 1^K ) 

    =    exp{ -n 𝐃 + √(n) 𝒬_inv(𝖵, ϵ_0) -1/2 logn 1 + O(1) 1}. 


By the definition of the minimax error (<ref>) and the characterization of the achievable error region asymptotics in (<ref>), we have

    β_ϵ_0(P_Y_0, {P_Y_k}_k = 1^K) 
       = min_𝐳∈exp{ -n 𝐃 + √(n)𝒬_inv(𝖵, ϵ_0) -1/2log n 1 + O(1) 1}max_ 1 ≤ k ≤ K  z_k.

Applying lem:generalminmax with f(𝐳) = - n 𝐃 + √(n)𝐙≤𝐳 and a = 1- ϵ_0, where 𝐙∼𝒩(0, 𝖵), we obtain

    β_ϵ_0(P_Y_0, {P_Y_k}_k = 1^K) 
          = min_z ∈ℝ: f(z 1) ≥ 1 - ϵ_0exp{ z - 1/2log n + O(1)  }.

Since f(z1) is nondecreasing and continuous in z, 

    f(z^⋆1) = 1- ϵ_0
 
holds, where z^⋆ is the argument that achieves the minimum on the right-hand side of (<ref>). Recall the definitions of D_min and ℐ_min from (<ref>)–(<ref>). By Chernoff's bound on f(𝐳), for any z = nE + o(n) with E > -D_min, we have f(z 1) = 1 - o(1). Similarly, for E < -D_min, we have f(z 1) = o(1), giving 

    z^⋆ = -n D_min + o(n).

We proceed to show that the minimum on the right-hand side of (<ref>) is achieved at

    z^⋆ = -n D_min + √(n) b + O(1 ) ,

where b is defined in (<ref>). Here
rCl
3l-n D_min 1 + √(n)𝐙_ℐ_min ≤z^⋆1 

   =    - n 𝐃 + √(n) 𝐙 ≤z^⋆1 

      + ℙ[ {-n D_min 1 + √(n) 𝐙_ℐ_min ≤z^⋆1} 

         ⋂{ -n 𝐃_ℐ_min^c + √(n) 𝐙_ℐ_min^c ≰z^⋆ 1 } ]

   =    1 - ϵ_0 + O( 1/n), 

where (<ref>) follows from (<ref>), (<ref>), and the union bound and Chebyshev's inequality on -n 𝐃_ℐ_min^c + 𝐙_ℐ_min^c≰ z^⋆1. By the Taylor series expansion of Q_inv(𝖵, ·), we conclude that

    𝐙_ℐ_min≤1/√(n)(z^⋆ + n D_min) 1+ O( 1/n) = 1 - ϵ_0,

which implies (<ref>). Combining (<ref>) and (<ref>) completes the proof.




§ ACKNOWLEDGMENT

We are grateful to the reviewers—Professor Jonathan Scarlett and two anonymous reviewers—for their thorough, careful, and insightful feedback, which is reflected in the paper. 

IEEEtran
 


Recep Can Yavas(S'19) is currently a Ph.D. candidate in electrical engineering at the California Institute of Technology (Caltech). He received the B.S. degree from Bilkent University in Ankara, Turkey, in 2016 and the M.S. degree from Caltech in 2017, both in electrical engineering. His research interests include information theory and probability theory. 


Victoria Kostina(S'12-M'14)
received the bachelor's degree from the Moscow institute of Physics and Technology in 2004, the master's degree from the University of Ottawa in 2006, and the Ph.D. degree from Princeton University in 2013. In 2014, she joined Caltech, where she is currently a Professor of electrical engineering. Her research spans information theory, coding, control, learning, and communications. She received the Natural Sciences and Engineering Research Council of Canada master's scholarship in 2009, the Princeton Electrical Engineering Best Dissertation Award in 2013, the Simons-Berkeley Research Fellowship in 2015, and the NSF CAREER Award in 2017.


Michelle Effros(S'93-M'95-SM'03-F'09) 
received the B.S. degree with distinction in 1989, the M.S. degree in 
1990, and the Ph.D. degree in 1994, all in electrical engineering from 
Stanford University. She joined the faculty at the California Institute of 
Technology in 1994, where she is currently the George Van Osdol Professor 
of Electrical Engineering. Her research interests include information 
theory, network coding, data compression, and communications.

Prof. Effros received Stanford's Frederick Emmons Terman Engineering 
Scholastic Award (for excellence in engineering) in 1989, the Hughes 
Masters Full-Study Fellowship in 1989, the National Science Foundation 
Graduate Fellowship in 1990, the AT&T Ph.D. Scholarship in 1993, the NSF 
CAREER Award in 1995, the Charles Lee Powell Foundation Award in 1997, the 
Richard Feynman-Hughes Fellowship in 1997, and an Okawa Research Grant in 
2000. She was cited by Technology Review as one of the world's top young 
innovators in 2002. She and her co-authors received the Communications 
Society and Information Theory Society Joint Paper Award in 2009. She 
became a fellow of the IEEE in 2009. She is a member of Tau Beta Pi, Phi 
Beta Kappa, and Sigma Xi. She served as the Editor of the IEEE Information 
Theory Society Newsletter from 1995 to 1998 and as a Member of the Board 
of Governors of the IEEE Information Theory Society from 1998 to 2003 and 
from 2008 to 2017, serving in the role of President of the Information 
Theory Society in 2015. She was a member of the Advisory Committee and the 
Committee of Visitors for the Computer and Information Science and 
Engineering (CISE) Directorate at the National Science Foundation from 
2009 to 2012 and in 2014, respectively. She served on the IEEE Signal 
Processing Society Image and Multi-Dimensional Signal Processing (IMDSP) 
Technical Committee from 2001 to 2007 and on ISAT from 2006 to 2009. She 
served as Associate Editor for the 2006 joint special issue on Networking 
and Information Theory in the IEEE Transactions on Information 
Theory and the IEEE Transactions on Networking/ACM Transactions on 
Networking and as Associate Editor for Source Coding for the IEEE 
Transactions on Information Theory from 2004 to 2007. She has served on 
numerous technical program committees and review boards, including serving 
as general co-chair for the 2009 Network Coding Workshop and technical 
program committee co-chair for the 2012 IEEE International Symposium on 
Information Theory.


