I'm getting confused. Better terminology might be bit string (BS) 1 = plain text, BS 3 = cipher text. "The only case where they are not independent is if one is a part of the other" is absolutely not the only reason a cipher text might be compressible, for the following reasons that will appear shortly...

If you keep trying bitstrings until you find one that has a certain property, then it's not random any more, which means your assumptions about independence are false...

"111111111111 is less random than 01101001001101" In this case that's only because it's 2 bits shorter.

Newton's mechanics says yet. Quantum mechanics says no.

@TeroLahtinen that's a bit too simplistic. There is, in fact, of course no way to prove whether a bitstring is random. What those heuristics for estimating whether it is random do is: they investigate, statistically, correlations between adjacent bits. In a truely random bitstring, these correlations converge to zero, whereas, as you say, humans tend to choose the next bit with a slight negative correlation in order to avoid naturally ocurring constant runs. However, 11111111111 has a big positive correlation, so it would not pass those algorithms either. 111111011111 is more random.

@leftaroundabout so, by that logic 1010101010 is the most random bitstring possible. Remember that even though we might have seen a hundred sequential 1s, the chance of getting another 1 is still just 50:50.

@KenY-N, it is true that regardless of the past sequence, predicting the next bit from a random generator is still 50/50. I believe my confusion lies in the relationship between a random bitstring in a Kolmogorov sense, and a randomly generated bitstring.

@KenY-N a badly written fake-random detection heuristic might rate it this way, yes. The heuristics that are actually used of course don't just consider directly adjacent bits, but also bits a little further back. Mathematically, the correlation between all pairs of samples should be zero, but checking all of them gets you in trouble akin to the Birthday paradox (correlation in a sample is itself a random variable), to say nothing of the computational feasibility.

Imagine a 1 bit long P, encoded by a 1 bit K, send as a 1 bit C. C = 1, tell me what P could be without knowing K. Now if your message is 100 bits you have to do this 100 times, nothing about 1 bit in C influences any other bit in C.

I'm assuming a human is generating the keys. In that case, the randomness might not be as random as a computer generated key. I'm not trying to answer your question with a question, but that seems to suggest to me that there is a difference in security levels for a one time pad...this is just a late night rambling though...you've got an up-vote from me.

You are omitting a crucial piece of information: what have you been taught "perfect encryption" means? I hope it's not "the only way to recover the message is by knowing the key", because that makes no sense.

The fundamental confusion here seems to be about where the randomness is. Specifically, it's the OTP's data that's random, such that 1111111 is just as likely as 1010001. by definition. That said, it's true that a message of 1111111 might be more common than a message of 1010001 in some cases, but that's entirely moot because the message's entropy is completely irrelevant to OTP's guarantees. If your OTP is more likely to select 1111111 as its "random" sequence, then your implementation's messed up.

This question severely misunderstands what "randomness" is (and its relation to compression). It is not a state, nor a property that a singular entity can have in isolation. Rather it is either a property of a process, or else of a collective entity in the context of it's members (and possibly their order). You cannot speak of any single bitstring, even 11111111111 as being random or non-random in isolation. You can only talk about its randomness wrt to the process that created it, or else in the context of other bitstrings created for the same purpose/generation.

@RBarryYoung Obligatory XKCD.

@fkraiem I assume by "perfect encryption" they mean information-theoretically secure.

As to randomness, consider randomly sampling $x \in \{0, 1\}^n$. No $n$ bit string is any more likely to be sampled than another one, and in this sense it makes no sense to say any $n$ bit string is more random than any other $n$ bit string.