Understanding entropy, information, and randomness In a statistical mechanics book, it is stated that "randomness and information are essentially the same thing," which results from the fact that a random process requires high information.
More specifically, if we are encoding the results of $N$ coin flips, where $0$ represents Tails and $1$ represents heads, then as $N \to \infty$, the Kolmogorov complexity will approach $N$. 
But, later it says that entropy and information are inversely related since disorder decreases with knowledge. But, this does not make sense to me. I always thought that entropy and randomness in a system were the same thing. 
What's wrong with my interpretation?
 A: I presume that there is hardly an xplicit definition of randomness or information in this book. Until one stays to the everyday life meaning, it is difficult to say something meaningful.
If one sticks to the informtion theory definition of information, that is a quantity which can be assigned to an event, on the basis of its probability. If we require it is a decreasing function of the probability (events with higher probability convey less information than events of lower probability) and we request that in the case of independent probabilities, the corresponding information are additive, information can be meaured by $log(1/p_i)$ if $p_i$ is the probability of event $i$. Starting with this definition of information, the average information  associated to the set of all the possible independent events is, whithin a multiplicative constant,  the information theory entropy (or Shannon entropy) $S_{Sh}$:
$$
S_{Sh} = - \sum_i p_i log(p_i).
$$
Randomness is a different concept, although with some possible connection to probabilities. But, in essence, randomness is always a property of an isolated  single configuration, while an event can correspond to a set of configurations. More important, information definition implies the possibility of assigning a probability, i.e. it can be translated in a statement about the frequency a single outcome appear in a repeated series of experiments, while randomness is something which is an attribute of the single outcome.
A quantitative measurement of randomness of a configuration is possible by measuring its algorithmic complexity, i.e. estimating the size of the minimum program able to reproduce that configuration. It turns out from Complexity Theory that the average of the complexity entropy is the Shannon entropy, linking together the two concepts (but it is clear that they do not coincide!).
An important side remark is that the definition of algorithmic complexity is non constructive, and even worse, it is a non-computable function! So, a straightforward calculation of Shannon entropy as average of the complexity is not possible in practice!. 
Finally, for some of the most obvious physical applications in equilibrium Statistical Mechanics, it is useful to notice that Shannon entropy coincides with Boltzmann-Gibbs definition of entropy in different ensembles, provided the probability of the microstates are the usual ones. In turn, for a general system, Boltzmann-Gibbs entropy per degree of freedom coincides with the thermodynamic entropy per degree of freedom only at the thermodynamic limit.
Applying all above to the example of a sequence of N coin flips: the randomness of a single sequence can be any number from 0 to N (we cannot exclude the sequence of N 1's or 0's). Moreover, larger is N and lower the relative number (and probability) of  ordered series of heads and tails. So, by increasing N, random sequences dominate.
However, it should be clear that this behavior is not universal, but based on the key assumption of statistical independence of each flip. In a random process where flips are correlated, non-random configurations could prevail. That's the case when a crystal is thermodynamically more stable than the fluid.
A: *

*Entropy
$$S = -\sum_i p_i \log p_i $$


*

*Information
$$ H = \sum_i p_i\log p_i $$
Therefore: 
$$
\boxed{\vphantom\int~~\text{(information)} = -\text{(entropy)}~~}
$$
or the less we know the higher the entropy, and vice versa.
