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

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

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.

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

3. Originally Posted by 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.
In the general case, no.

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

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

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

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•