What is the computer science definition of entropy?

I’ve recently started a course on data compression at my university. However, I find the use of the term “entropy” as it applies to computer science rather ambiguous. As far as I can tell, it roughly translates to the “randomness” of a system or structure. What is the proper definition of computer science “entropy”? Answer … Read more

Optimal way to compute pairwise mutual information using numpy

For an m x n matrix, what’s the optimal (fastest) way to compute the mutual information for all pairs of columns (n x n)? By mutual information, I mean: I(X, Y) = H(X) + H(Y) – H(X,Y) where H(X) refers to the Shannon entropy of X. Currently I’m using np.histogram2d and np.histogram to calculate the … Read more

Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?

Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound? https://en.wikipedia.org/wiki/Bekenstein_bound Answer AttributionSource : Link , Question Author : Sue K Dccia , Answer Author : Community

Example of channel where capacity is achieved without a uniform distribution on the output alphabet

The capacity of a discrete memoryless channel is given by the maximum of the mutual information over all possible input probability distributions. That is C=max H(Y|X) is specified by the channel only and has nothing to do with p_X. Hence, it seems that maximizing the capacity is just equivalent to maximizing H(Y) i.e. we want … Read more

Can we think of information theory in terms of “a measure on set of information”?

In information theory, we deal with the quantities I(X;Y),H(X),H(Y),H(X|Y),H(Y|X). These are just numbers, but I intuitively think of them as the “measure” of a set of information. There is at least one special case where this interpretation is exact: suppose there are independent variables V1,…Vn, and the variables X,Y,Z are tuples of Vi. Then we … Read more

Decomposition of Mutual Information

I came across a book where the author uses the following property of mutual information: Let X,Y,Z be arbitrary discrete random variables and let W be an indicator random variable. (1)  I[X:Y∣Z]=Pr(W=0)I[X:Y∣Z,W=0]+Pr(W=1)I[X:Y∣Z,W=1]  I don’t understand why this property holds in general. To show this I was thinking to proceed as follows: I[X:Y∣Z]=Ez[I[X:Y∣Z=z]]=Ew[Ez[I[X:Y∣Z=z] | W=w]]=Pr(W=0)Ez[I[X:Y∣Z=z] | W=0]+Pr(W=1)Ez[I[X:Y∣Z=z] | W=1]. where the second line … Read more

Auxiliary random variables in the analysis of the private information of wiretap channels

I am following Section 13.2 of Mark Wilde’s book. I reproduce the question here for completeness. Consider a wiretap channel X→Y,Z defined by the conditional probabilities p(y,z|x) for inputs chosen according to some p(x). The goal of maximizing private information is to transmit information from X to Y without any information leaking to Z. Naively, … Read more

Complexity of maximization of entropy of Hamming distance of bitstrings

We have a set of possible “key”s S represented by bitstrings of length k. In other words, S contains an arbitrary subset of all bitstrings of length k. For example, when k=3, it can be S={001,010,011,000,111}. I would like to find a “guess”, which maximizes the Hamming distance of itself and the possible keys, assuming … Read more