Would it be possible to map (a reversible mapping) a random string of bits S1, to another random string of bits S2 which has a different length (length S1 != length S2) but that on average has the same length (avg length S2 = length S1)?
Thanks.
Would it be possible to map (a reversible mapping) a random string of bits S1, to another random string of bits S2 which has a different length (length S1 != length S2) but that on average has the same length (avg length S2 = length S1)?
Thanks.
Example:
- open a file
- read the first 1000 bits
- replace these bits with another string that is shorter or longer, but on average still 1000 bits
- save and close
Unless you have a way of knowing the lengths of S1 and S2 a priori, it's not possible (and if you do, it's triavial to map all S1 starting with 1 to a length(S1)-1 string and those starting with 0 to a length(S1)+1 string; inverting would simply compare length(S2) to length(S1); note that this also obviously would let you to compress, if only by a half-bit on average).
Without side information, it is indeed impossible. Only mappings where S2 have the same length as S1 can achieve the same average length (trivially).
> Unless you have a way of knowing the lengths of S1 and S2 a priori
Maybe if length(S1) is known a priori, but not length(S2)?
If you can't compute the length of S2, then it's still impossible. Basically if I hand you a stream of bits, you need to have a way of saying "S2 ends here". The thing is, that extra bit of information to know when S2 stops makes the task impossible - encoding that information in any way costs bits, and this pushes the average length higher. I am trying to think of a more intuitive counting argument for that but am drawing a blank...