Map random string to another string of the same size on average

[slope]

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.

[slope]

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

[Jyrki Alakuijala]

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.

In the general case, no.

[Stefan Atev]

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).

[slope]

> 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)?

[Stefan Atev]

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...