## 4 DKI Capacity Region of the BSC
### Inner Bound (Achievability Proof)
The argument for the need of such division is that the binary entropy function \(H(\cdot)\) is monotonic increasing in domain \(0<A<1/2\) and decreasing in domain \(A\geq 1/2\). In the latter case, we can introduce an alternative Bernoulli process, which results in a larger volume space, and at the same time, it guarantees the Hamming weight constraint. For the sub-case 1, i.e., where \(0<A<1/2\), we restrict our considerations to an \(n\)-dimensional Hamming hyper ball with edge length \(A\). We use a packing arrangement of overlapping hyper balls of radius \(r_{0}=\left\lfloor n\beta\right\rfloor\) in an \(n\)-dimensional Hamming hyper ball \(\mathcal{B}_{\mathbf{0}}(n,nA)\). **Lemma 1** ( Space exhaustion ). : _Let \(R<H(A)\) and let \(\beta\in(0,\beta_{\max})\) be an arbitrary positive constant referred to as the distinction property of the casebook._  
_Then, for sufficiently large codeword length \(n\), there exists a codebook \(\mathcal{C}=\{\mathbf{c}_{i}\}_{i\in[\![M]\! ]}\subseteq\mathbf{H}^{n}\), with \(\mathbf{c}_{i}=(c_{i,t})|_{t=1}^{n}\subseteq\mathbf{H}^{n}\), which consists of \(M\) sequences in the \(n\)-dimensional Hamming hyper ball \(\mathcal{B}_{\mathbf{0}}(n,nA)\), such that the subsequent holds:_  
\(\diamondsuit\)_Hamming distance property_: \(d_{\mathrm{H}}(\mathbf{c}_{i},\mathbf{c}_{j})\geq\left\lfloor n\beta\right\rfloor +1\qquad\forall i,j\in[\![M]\! ]\)_, where \(i\
eq j\). \(\diamondsuit\)_Codebook size: the codebook size is at least \(M\geq 2^{n(R-H(\beta))}\). Proof. : Recall that the minimum Hamming distance of a code \(\mathcal{C}\) is given by  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]  
We begin to obtain some codewords that fulfill the Hamming weight constraint, namely,  
\[\frac{1}{n}\sum_{t=1}^{n}c_{t}\leq A. \tag{29}\]  
First, we generate a codeword \(\mathbf{C}\stackrel{{ i.i.d. }}{{\sim}}\mathrm{Bern}(A)\) (such a random generation should not be confused with a similar procedure as is accomplished in the encoding stage of the RI problem. While therein, each message is mapped to a codeword through a random distribution, here for the DI problem, we first solely restrict ourselves to generation of codewords through the Bernoulli distribution to guarantee the Hamming weight constraint, and employ them in the next procedure called the greedy construction up to an exhaustion. Then, after the exhaustion, we establish a deterministic mapping between the message set and the codebook; that is, each message is associated with a codeword. Further, in the RI problem, it is in general possible that two different messages are mapped to a common codeword; however, considering the DKI problem in here, there exists a one-to-one mapping between the set of messages and the set of codewords). Since \(\mathbb{E}[C_{t}]=A\), by the _weak law of large numbers_, we obtain  
\[\lim_{n\to\infty}\Pr\left(\left|\frac{1}{n}\sum_{t=1}^{n}C_{t}-A\right|\leq \tau\right)=1, \tag{30}\]  
where \(\tau>0\) is an arbitrary small positive. Therefore, for sufficiently large codeword length \(n\), the event \(\left|n^{-1}\sum_{t=1}^{n}C_{t}-A\right|\leq\tau\) occurs with probability \(1\), which implies that, for sufficiently large \(n\), the subsequent event happens with probability one:  
\[\frac{1}{n}\sum_{t=1}^{n}C_{t}\leq A+\tau. \tag{31}\]  
Now, observe that since (31) holds for arbitrary values of \(\tau\), it implies that the subsequent condition for sufficiently large \(n\), is fulfilled  
\[\frac{1}{n}\sum_{t=1}^{n}C_{t}\leq A, \tag{32}\]  
which is the Hamming weight constraint, as required. Next, we begin with the greedy procedure as follows: Let us denote the first codeword determined by the Bernoulli distribution by \(\mathbf{c}_{1}\), and assign it to message with index \(1\). Then, we remove all the sequences that have a Hamming distance of less or equal than \(\left\lfloor n\beta\right\rfloor\) from \(\mathbf{c}_{1}\).