  This work is part of a project "Walsh Spectrum Analysis and the Cryptographic
Applications". The project initiates the study of finding the largest (and/or
significantly large) Walsh coefficients as well as the index positions of an
unknown distribution by random sampling. This proposed problem has great
significance in cryptography and communications.
  In early 2015, Yi JANET Lu first constructed novel imaginary channel
transition matrices and introduced Shannon's channel coding problem to
statistical cryptanalysis. For the first time, the channel capacity results of
well-chosen transition matrices, which might be impossible to calculate
traditionally, become of hottest research focus. For a few Discrete Memoryless
Channels (DMCs), it is known that the capacity can be computed analytically; in
general, there is no closed-form solution. This work is concerned with
analytical results of channel capacity in the new setting. We study both the
Blahut-Arimoto algorithm (which gave the first numerical solution historically)
and the most recent results [Sutter et al'2014] for the transition matrix of
$N\times M$. For an $\epsilon$-approximation (i.e., the desired absolute
accuracy of the approximate solution) of the capacity, the former has the
computational complexity $ O(MN^2 \log N/\epsilon) $, while the latter has the
complexity $ O(M^2N\sqrt{\log N}/\epsilon) $. We also study the relation of
Renyi's divergence of degree $1/2$ and the generalized channel capacity of
degree $1/2$.
