## 4 DKI Capacity Region of the BSC
### Inner Bound (Achievability Proof)  
Before we provide the inner bound proof, we explain on our methodological approaches that are used here and expand on them. In particular, similar to other information theoretical problems, the derivation of the inner bound on the DKI capacity region, consists of the subsequent two main steps:  
Step 1 (rate analysis)First, we propose a greedy-wise method for codebook construction, which has a flavor similar to that observed in the classical approach of the Gilbert-Varshamov (GV) bound (the early introduction of such a bound in the literature is accomplished by [PERSON] in [63]) for covering of overlapping balls embedded in the input set. More specifically, we introduce a codebook of exponential size in the codeword length \(n\), which fulfills the input constraint and enjoys a Hamming distance property; namely, every pair of distinct codewords are separated by a certain distance. Moreover, we introduced a parameter \(\beta\) in order to account/adjust such a distance. This step is particularly relevant in the sort II error analysis, as well as the derivation for the final lower bound on the identification coding rate. Additionally, we identify the whole range across which the parameter \(\beta\) can change, which is needed to derive an analytical lower bound on the corresponding codebook size. Step 2 (error analysis)In the second part (error analysis), we show that the suggested codebook in the previous part is optimal, i.e., leads to an _attainable_ rate pairs \((R,\kappa)\). To this end, we begin with introducing a decision rule which is a distance decoder based on the Hamming metric, and would show that the associated errors of the sort I and the II probabilities vanish in the asymptotic codeword length, i.e., when \(n\to\infty\). Moreover, the error analysis for the sort II error probability determines the  
Figure 4: Range of codebook sizes for various K-identification configurations. The codebook scale for DKI problem over the BSC coincide the conventional exponential behavior. But, aside from the standard exponential and double exponential code sizes [26] (RKI over DMC), a different non-standard codebook size is also observed for Gaussian channel with slow fading (GSF); namely, it grows super-exponentially in the codeword length \(n\), i.e., \(2^{(n\log n)R}\). Figure 5: Spectrum of goal message set sizes for different K-identification setups. The goal message set scale for DKI problem over the BSC grows exponentially in the codeword length. Additionally, the GSF channel represent a sub-linear scale, which is lower than the conventional exponential behavior. The scale of goal message set for the BSC is identical to its codebook scale, i.e., exponentially in the codeword length. associated error exponent. As a result, the feasible region for the goal identification rate is obtained. Codebook Construction  
In the following, we confine ourselves to codewords that meet the subsequent condition: \(n^{-1}\sum_{t=1}^{n}c_{i,t}\leq A\), \(\forall\,i\in[\![M]\!]\). Furthermore, we divide them into two cases:  
\(\diamondsuit\)**Case 1--with Hamming weight constraint**: \(A\leq 1\), then the condition \(n^{-1}\sum_{t=1}^{n}c_{i,t}\leq 1,i\in[\![M]\! ]\) is non-trivial in the sense that it induces a strict subset of the entire input set \(\mathbf{H}^{n}\). We denote such subset by \(\mathcal{B}_{\mathbf{0}}(n,nA)\) and is equivalent to \(\left\|\mathbf{c}_{i}\right\|_{1}\leq A\). \(\diamondsuit\)**Case 2--without Hamming weight constraint**: \(A\geq 1\), then each codeword belonging to the \(n\)-dimensional Hamming cube \(\mathbf{H}^{n}\) fulfilled the Hamming weight constraint, since \(\frac{1}{n}\sum_{t=1}^{n}c_{i,t}\leq 1\leq A,i\in[\![M]\!]\). Therefore, we address the entire input set \(\mathbf{H}^{n}=\{0,1\}^{n}\) as the possible set of codewords and attempt to exhaust it in a brute-force manner in the asymptotic, i.e., as \(n\to\infty\). Analysis For Case 1  
Observe that, within this case, we again divide into two cases:  
\(0<A<1/2\).