The $5000 Compression Challenge
patrickcraig.co.uk
patrickcraig.co.uk
On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims.
If you design an impossible game, the only possible thing for anyone to do is to break it. If you then complain that THAT is cheating, you're a pedantic idiot - one of those annoying kids in middle school who loses a bet and then tries every possible way to weasel himself out.
To add fuel to the fire, his obnoxious replies such as "I tried running the first two files and it didn't work", make my blood boil, as it's a clear attempt to try and belittle the contestant.
I feel the same way when casinos bust card counters. You use math to take money from suckers. When other people use your rules and better math to take money from you, that's suddenly deeply immoral.
That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising that this limitation isn't mentioned), and the subsequent alteration to the rules was initiated by Patrick, who intentionally tried to inject a loophole, but failed to specify the need to keep the files in order. His rules; he should have to live by them.
Also, I suspect that if Patrick had mentioned the need to leave the file names unaltered or in order, there's a good chance that Mike would have smelled a rat. After all, it is precisely in that side-channel where the information gain is to be had.
#!/bin/sh
i=0
f=`head -1 $1`
n=`tail -1 $1`
rm -f $f
while [ $i != $n ]; do
cat $1.$i >> $f
i=`expr $i + 1`
if [ $i != $n ]; then printf "5" >> $f; fi
done
Which is the Kobayashi Maru in a nutshell. In that fictional case, Kirk was disqualified but also received a commendation.
I don't know if the novel is canon, but it ought to be.
Kirk beat it by cheating, Scotty beat it legitimately, then proved that what he did only worked in the simulation.
The purpose for the impossible game was to provide a distraction to people going to Usenet comp.compression and announcing their brilliant new algorithm and claiming it could compress any file better than any other algorithm.
Obnoxiousness just means this challenge becomes interesting to code-golfers who will also try to obey the rules but produce a broken result.
However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed.
This means that the original formula for adding the size of the solution applies: just the file sizes added together.
Goldman should accept that he foolishly rushed into a careless amendment of his original challenge and pay the money.
That said, it obviously is cheating to have the archive format or file system hide the representation of where the removed bytes are! If a single file is produced, it has to include a table of where to insert the bytes that were taken out. If multiple files are produced, the archive format or file system stores that information for you at considerable expense.
If both people are wrong, the contest should be declared invalid and Goldman should return the $100.
If only Goldman is wrong, he should pay $5000.
Under no interpretation is Goldman strictly right and the contestant strictly wrong.
So he is wrong to keep the $100 in any case.
Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up.
It casts doubt on whether he would pay if somebody won by the original rules with some luck. Maybe he has an implicit allowance, that merely two files can't "encode" a big enough advantage, but again, then it's his fault for not addressing that in the new rules.
If you don't see the loophole before you agree, you pay. Actually there's a great little bit about this in the movie Guys And Dolls (1955), and what to do if someone bets you that he can make a jack of spades squirt cider in your ear.
Given the fact that Patrick made the rules concerning multiple files, and that they were intentionally tricky, I think it's fair to interpret them in that spirit - as a trick.
Notably, even without the ordering there is still some information leakage purely in terms of file sizes, but that's a little harder to exploit (likely still possible with a 3mb file). Of course, the rules don't explicitly state the directory must be otherwise empty...
Frankly, I think it's pretty reasonable that Patrick "lost" the bet, even if Mike reasoning wasn't sound. For Patrick to have won that bet would have required quite a list of requirements of how those "other" files were to be passed to the decompressor. Such requirements were not presented, and if they had been they would have been obviously fishy.
And yes there needs to be a way to know which file(s) are the compressed data, that loophole would disqualify any entry.
It's a good point about needing to know which files are compressed. On a philosophical level, I'm not sure whether that means there actually should be a way to know which file(s) are the compressed data, or that the rules are simply broken...
Unjustifiable objections could have been made but screw those, because they would cause legitimate compression to fail.
Unjustifiable objections will pretty much always exist if the rules are written in English. That doesn't mean the rules are broken, it means you use judgement and follow the purpose of the rules.
Mike's fate was sealed when he allowed multiple files without an overhead penalty. He could have removed all the metadata possible, simply having the files exist as separate entities was enough to ruin him.
Another scheme: chop it up into files of increasing length, the difference being 1..256, encoding a byte (ignore the last difference).
EDIT more efficient to increase in length by 1 or 2, encoding a bit.
Regardless of the results of the challenge, at the end of everything Goldman offered in good faith to return the $100 and Craig said he could keep it.
The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile.
Craig did not compress the data stored. He split the file up into multiple smaller files and using "5" as the boundary. However, by creating 218 files, he increased the amount of space required to store this data. Ergo, the combined size of the "compressed" files and the decompressor exceeded the size of the original file. It is only by excluding the space taken up by the meta data that the "compressed" files are smaller. Furtheremore, elsewhere it was noted that: "The FAQ clearly outlines that filesystem exploits are not true compression."
It's hardly a filesystem exploit if - again by Goldman's own statement - gunzip is allowable.
Replacing every "5" with EOF is apparently bad.
What if he replaced every "5z" with EOF? Fewer bytes there.
What if he had a variant of LZ77 doing dictionary encoding followed by a range encoder that outputs symbols in the range -1 through 255? Even counting the EOF as a character, this would give an output 2K characters smaller. Sounds like compression to me. It's finding common sequences and uncommon sequences and rescaling them based on probability to remove redundancy.
In any case, no compression algorithm makes all inputs smaller. So, just because a data encoding doesn't make a particular input case smaller doesn't imply that it's not a compression algorithm.
This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the multiple files would be considered purely based on their filesize. According to a straightforward reading of the challenge, only the filesize of the decompressor and compressed file would matter. But when Mike agreed to multiple compressed files, nowhere did anyone state that only the filesize of the additional compressed files would matter.
And it should be pretty obvious to anyone that you cannot simply accept just the filesize of the multiple compressed files. Because the only point in using multiple files is to try and hide extra data in either the number of files or their filenames. And that obviously violates the entire point of the challenge.
If you want to take Patrick's multiple files approach to its logical conclusion, you may as well submit a bunch of zero-sized files where all of the data is stored in the filename (perhaps with an integral prefix for sorting purposes) and have your decompressor just be some variant on `echo` that strips the prefix and echoes the rest of the filename (without space separation). That way you could claim infinite compression!
---
If you're still not convinced, then how about this: nowhere did Mike agree that he would not rename the decompressor or compressed file(s) prior to running the program. And a trivial renaming would have broken Patrick's "decompressor". That alone should cause his entry to obviously be a failure.
You mean, like...
> I meant can I send you a compressor and several compressed files whose total file size is less than the original uncompressed file and from which I can regenerate the original uncompressed file.
(to which Mike agreed)?
Then what is "agreeing"? These two sentences appear logically inconsistent.
Only, this trickerly was not Mike's intent, otherwise, of course, he would have played this card immediately. For instance:
"I said you could send that to me because that is a true statement with which I therefore agree. It is undeniably true that you can send me anything you like. You can send me an e-greeting card for my birthday, and you can send me a Britney Spears MP3 as a MIME attachment. You can send me questions asking about what you can send me. Obviously, though, the only material which you can send me which also happens to conform to the contest rules is a single program and a single data file. Please re-read the contest statement; I will gladly explain any portion of it that is not clear."
Mike had no need to complain that the program isn't a decompressor. He should have played it as above.
Instead, he demonstrated acceptance of the the multi-file structure of the solution by complaining that the algorithm in the program file isn't a form of compression.
Providing multiple files with the (deceptive) intention of storing data via filesystem metadata, but then failing to specify how filesystem metadata is to be treated is just asking for it.
Mike will always be able to find an excuse not to pay. If Parrick had imposed the 'no file renaming' condition, Mike could have found another way in which to break his submission with a counter loophole.
This type of challenge should never be made or accepted, if financial incentives are involved, without an impartial adjudicator.
The point of a challenge like this is the same as the point of the Randi challenge: to provide a means to demonstrate that impossible claims are impossible (in this case, that of being able to compress truly random data, and in the case of the Randi challenge, supernatural/magical abilities such as ESP). After all, if any such claim were valid, then the claimant would be able to defeat the challenge, assuming that the stated rules are fair (and they are).
Which is to say, the point of a challenge like this is not actually to have anyone enter. It's just to be.
> This type of challenge should never be made or accepted, if financial incentives are involved, without an impartial adjudicator.
Did you read the whole page? Mike did offer an impartial adjudicator:
> I would gladly submit any such submission to an impartial ombudsman to determine the question of whether data compression has occurred.
Then again, the purpose apparently was to make crackpots put their money where their mouth is rather than spam the usegroup, so perhaps fairness isn't the best success criterium.
The same process would work with a single stream input to the decompressor, as long as the length of each block where an additional '5' must be output is available - the list of file sizes - so that's where the additional information is stashed.
> Rather, you simply split the file into 218 parts ending with the
> character "5" and then stripped that final character from each part. Thus the
> "decompressor" is nothing more than a reassembler,
> concatenating the parts and reappending
> the character "5" after each.
Normally you'd need a delimiter to separate those chunks, a delimiter that doesn't occur in the chunks e.g. through padding or escaping. That, in turn, increases the filesize, and now you're in trouble. What Patrick did was to use EOF as a new fresh "delimiter" that doesn't occur anywhere, and at a cost of zero bytes, no less.
Cheating, or inventive.
In my experience, people who set up such tricks do not usually respond well when the tables are turned.
There are some people in the world who take it personally when other people don't understand their area of expertise as well as they do. They get angry and offended at naive questions, and seek to punish the idiots. This is a great way to take an interesting subject and ruin it for everyone.
One of the best aspects of the HN culture is that experts here tend to incline more toward teaching and less toward chastising. It's a nice change from Usenet.
> Before naming the individual and giving additional details of our > correspondence, I would like to give him some time to analyze the > data I will be sending him. It would be very easy to point out to > him the impossibility of his task, but far more interesting to see > how long he will struggle with the problem before realizing it for > himself. > > I am supposing that one of his fellow co-workers probably referred > him to my challenge, as I cannot fathom that someone would read the > comp.compression faq first and then want to participate after > understanding the futility of the effort. On the other hand, some > people just don't understand information theory too well. > > I'll try to give him a complete explanation of his error after a > week or so, I guess. :)
So Mike is just smug about how clever he is, how stupid the other person is, not even suspecting there might be a loophole in the challenge.
I see no sign of interest in learning what the other person is up to, or even admitting that there might be something to learn.
A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair.
A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ up to 50.000$ prize money, but severe restrictions on memory and running time.
You can not beat Goldman's troll-ish challenge (certainly if the rules are retro-actively clarified in favor of the organizer). You could however try to put the challenge in limbo by creating a decompressor which bruteforces a solution, 'till some hashes match or the final heat death of the universe or the halting problem is solved, whichever comes first. Goldman will not be able to ever verify your solution, and when he does (theoretically it is not impossible), it means you win.
Or, instead of above Schrödinger's Compressor you can send a good random number generator back as your solution. If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Why does he want to do a diff between two random files, is he perhaps looking for order where there is none? But that's the same foolishness he accuses his participants of.
At the 10-year scale, a whole new set of tricks opens up. Invent a sufficiently popular programming language, or contribute a lot to the linux kernel, and start surreptitiously hiding bits of the file on his OS (the easiest would be for you language to have a builtin function that spits out a small part of the file).
(I made the same mistake some time ago when I tried to bruteforce a 4 byte RC4 key with 3 known bytes in the plain text; I found 256 solutions.)
There is no such thing as random file. Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". It can be random looking, you can run some statistic analysis on the byte sequence and say "It's probably generated by some good random algorithm", but even here "probably" doesn't mean any probability in [0,1].
Also there are cases in practice where you expect back the same random byte sequences even if they are randomly generated. Think about public key authentication and symmetric session key's exchange.
Randomness can be tied to the algorithm which generates a byte sequence. This information is not stored in the file in any way, it's just the mere result of an algorithm. Randomness is the "color of the bits" [1].
Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true here as well because it is algorithmically undecidable how random the string is.)
(In fact one of the definitions of a random string is one that is incompressible, i.e. there is no algorithm with shorter description than the string that produces the string.)
I read into the wiki article and this approach is certainly interesting. However this complexity depends on the description language so there is no unique way to determine if a string is random.
Maybe because the file was XOR'd with a secret one time pad?
A file with output from AES-256("sekrit") would not be random to Goldman. It would appear random to us, until we crack it with a plausible password. Key to randomness is unpredictability. The moment Goldman saves some atmospheric noise on his computer and makes a short pointer to it on his filesystem, is the moment this file loses its claimed unpredictability. Goldman knows this file deeply: He himself has compressed meaningless random data into predictable information that has meaning and purpose, a feat he set out to prove impossible. By simply entering the challenge with real meaningless randomness you make Goldman solve it for you.
He's running a model and needs to use the same random data each time.
I feel that the compressor for a true random stream is a true random generator. If I quickly show you a screen of black-and-white unpredictable noise, and ask you what it was, you'd compress/understand/recall that as "generate_noise()". I do not feel that this is lossy compression, for what did you lose? The ordering of a random file? Random files have no order to lose.
Because not all random files are equally random? DUH! He had to ensure there's no bias in the distrubution, use a good random generation, check for skewed data etc...
So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win.
The correct price for this game is probably closer to 200$.
Ah, how things have changed in 14 years
Bitcoin improves on that by not requiring a trust account - their trusted third party would simply hold one key in a 2-of-3 multi-signature scheme, giving him the authority to resolve disputes and adjudicate between them, but without holding any funds under his full control.
I find the legal implications of Bitcoin smart contracts very exciting - this significantly lowers the entry barriers for providing many kinds of financial services and opens up these markets for competition in a way that was simply impossible before. There's lots of room for innovation and disruption with that.
Disclaimer: standard IANAL/TINLA apply, but I'm the founder at a startup that facilitates exactly that (https://www.bitrated.com/) and received extensive legal guidance on the matter.
It sounds like your startup is trying to solve that and create a "Trust Marketplace". Godspeed. Establishing trust between strangers is a very hard problem.
And while you may find a way to innovate around existing laws, new laws will be written.
I would say that in this specific instance, they could've quite easily agreed on a reputable user from the comp.compression newsgroup whom they both trust.
> adjudicate at very low cost.
It makes sense that arbitrators for niche markets with considerable domain expertise could charge a premium for their services. Say, $50-$150 for that specific case doesn't seem like a stretch.
Also, note that the fee could be charged only in case of dispute. (and indeed, many trust agents on Bitrated offer their services for free or nearly-free when there's no dispute and no work on their part. 0.1% base fee + 2% for disputes seems to be a popular fee structure.)
> Establishing trust between strangers is a very hard problem.
Indeed! This is the main problem we're trying to tackle, which is arguably much harder than providing the technological platform for payments.
> And while you may find a way to innovate around existing laws, new laws will be written.
The thing is, we aren't taking advantage of some "loophole" or anything like that. The escrow regulations exists for a reason and makes a lot of sense - holding funds on behalf of others should have strict regulations attached to it. Escrow providers are trusted to keep the funds safe from thieves, not to "run away" with them, and to resist the temptation to invest user funds to make a (potentially quite high) profit while holding them (which could result in losing them, even in relatively "safe" investments).
With multi-signature, none of that risk exists, and so it makes sense that the regulation won't either. Even when new laws gets written to address that, they're likely to be much less strict.
The legal situation with multi-signature is very similar to a binding arbitration clause, so we anticipate regulations to be based off of that (and arbitration is significantly less strictly regulated than escrow).
I don't really agree with that, given the fact that he used the information about the size of the files.
Compression exploits redundancy in a data stream (basically). You basically get "all symbols" (and how you define this varies according to your compression method: you could do all letters in the case of text, or even text snippets that repeat, etc) and reassemble them in a way that the ones that repeat the most take less space (and you also need to start from a basic dictionary known by all uncompressors or ship it with your compressed file)
One simple analogy is writing with abbreviations, but if you write e.g. the reader has to know what "e.g." means or you have to put in the beginning "e.g. = example" (and this also takes space)
Now, a randomly generated file ideally has all symbols repeating with the same frequency, (we say all symbols have the same entropy - I'm not sure about this exact wording), hence you can't take a symbol that repeats more or less and make it take less space in your compressed file
While Pi has all pairs of 2 digits, your index would take more space than storing the pairs itself (because you might need to go beyond position 99)
For one situation you might "get lucky" and find a coincidence, but this won't scale generically
I admit this fooled me for a bit. Good news is, I won't be fooled again by something similar :)
It's just a shame that the heat death of the universe will probably occur before your program finishes.
Mike can escape his unthinking agreement to multiple files by the rules forbidding information in filenames.
http://www.si.com/vault/1972/10/09/618832/soundings-from-tit...
(The risk being that half of it is made up, but he definitely had a reputation for this sort of thing.)
"You might wonder why, if I was the best golfer in the world, like I say I was, I didn't turn pro and win all the championships? Well, you were liable to win a golf bag if you won a tournament in those days. A top pro wouldn't win as much in a year as I would in a week as a hustler. People would get to know a pro, and I wanted to keep my skill a secret as far as possible. I didn't care about championships. I wanted the cash."
In fact, as the data being hashed increases in size, the amount of data required to identify which preimage is the correct preimage must be greater than or equal to the difference in size between the digest and the preimage.
For example, let's say you are using a perfect hash function, with a 64-bit digest. If you feed data into the hash function in 64 bits chucks, and then try to brute-force the results, each preimage you find will be the right one, and you can assemble the original file, but you have exactly as many bytes as when you started!
Now lets say you feed in 65 bits to the perfect hash function, saving 1/65 space in the resulting list of digests. But unfortunately, there are two 65-bit preimages which will result in each of your stored digests, so you need a bit to decide which one is correct.
And so on...
Given a hash function that hashes an input I (of size N, comprised of N arbitrary bytes) to a digest D (of size M), then assuming that M is a fixed value, then for each output digest D_0, there will be 2^(N-M) values that hash to that D_0. How will you tell which is the "right" one?
By the pigeonhole principle, we can't fit 2^25165824 objects into 2^256256 holes; indeed each file will have on average 2^24909568 other files that share the same set of 1001 sha256 hashes.
The reason that we are able to work with hashes, and that compression works in practice, is that we don't have to deal with every 3M file. Most of these files are gibberish and will never be seen, and finding two files that match even one hash is incredibly difficult. But once we start talking about brute-forcing, we start encountering problems -- and having to dedicate an awful lot of processing power to the problem isn't the biggest one...
To be more formal, the challenger is finding what he believes to be a string that is Kolmogorov-random, and betting (quite safely) that the challenged party can't prove him wrong.
http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
What's funny is that Patrick (the challenger) asked if a bash script consisting solely of a call to gunzip would suffice as the decompressor. In other words, all he had to do was compress the file by more than the amount of the script. Mike allowed it, knowing that even a tiny "decompressor" that really just called out to the real thing, would still be larger than the compression achievable on a well-crafted random blob.
So the compressed data + gzip decompressor would very likely be a greater size than the original data.
Even without a filesystem - just sending data over the wire - you have to be able to delimit files in some way, and there's going to be overhead associated with that.
Another way to think of this is that any particular volume could be viewed as a single big file. How much space in that big file is he taking up?
Deleted comment
By the way in a theoretical sense Mike lost when he said he would allow multiple files and count their sizes: this is because [] is not the same as [[][][]], but consists of 3 empty sets. You can theoretically encode a file into just a bunch of 0-byte files, without using the order of the files or their names. He shouldn't have agreed to count only their sizes.
For the theoretical encoding into 0-sized files, you can simply interpret the input file as a binary number, and then create that many empty files.
This is not a practical solution of course - you can only compress two bytes down to 0-byte files this way, as 2^16-1 is already up to 65535 empty files. For three bytes it's up to 16,777,215 files.
If you wanted to store 9 bytes in unary as the number of empty files, you would need 2^72-1 = 4.7 sextillion (million quadrillion) files. Obviously that is not actually possible. But even 9 bytes is hardly enough to interpret the files as binary again. (Unless you can somehow get Mike to agree to the invocation - since the decompression program itself doesn't need to store any information and theoretically could be 0, 1 or 2 bytes.) But theoretically you don't need anything other than what Mike foolishly agreed to: allowing multiple output files counting their sizes.
2.
There is also another theoretical way to make money off of Mike, but it is not practical. (It doesn't work.) If we were not limited to bytes but could use bits, you could shave up to 5 bits off of every input file, if you figured out a way to decompress it by always prepending the bits 00000. (Theoretically there is only 1 pigeonhole to decompression, so you do not need to store any information in the decompression algorithm and it has no minimum size).
If Mike is using a random source for the files, this would result in a correct decompression in 1/32 of cases. But Mike is giving 49:1 odds (risk $100, get $5000), which is better than 31:1. So you could simply repeat the game with Mike thousands of times, always using the same decompression algorithm, until you have all of Mike's money. This works better if Mike is a computer, of course.
And it doesn't work at all on any actual systems, as a nibble is less than a byte and would not count as savings even if you could encode the decompression algorithm into a 0-byte (or up to 3 bit) invocation.
There are grey areas here. Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size?
I know this was written 14 years ago, but we had the net then, and shared libraries aren't exactly a new thing. Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way?
I'd say that using the filesystem to "hide" bytes is the least of the possible loop-holes with this challenge, if you were being pedantic about the rules.
The judge can disconnect his computer from the Internet, attempt to run the submitted decompressor and file, and declare failure when it doesn't work. Nothing in the challenge guarantees Internet connectivity on the machine.
> Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size?
Nope. In the email exchange, Mike said that just a script that called out to gunzip would be fine, and that he'd only count the size of the script as the decompressor size
> Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way?
Yup, as long as the dependency is already on the machine I suppose.
That's what's so enlightening about this challenge. Even a tiny, tiny script that calls to other programs still can't compress a "pathologically" random file by more than a few bytes.
That's exactly what I was getting at.
If gzip was allowed, then any common decompression utility should be allowed.
If that's the case, and said utility relies on an external library, should that library be included as part of the size of the decompression utility?
It's arguable that the "fabric" over which the data is delivered shouldn't matter. If shouldn't really matter if the linked library comes from the same SSD as the executable, or from a server on the other side of the world.
We currently define "the machine" as the internals of a box. Would this count if you were running the executable from a removable drive? If not, why does "network storage" trigger the disqualification, and not "USB storage"?
I understand the original premise of Mike's challenge, but considering a loophole is being discussed here, I'd like to know where people see that the boundaries of similar loopholes lie.
I agree that it shouldn't matter what the filesystem does to store it, if the rules state that file size is determined by a specific command to count all the inodes, then he lost. If the command is 'du' or 'wc', then he won.
> RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.
Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0.
Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
This proof of the impossibility of a compressor that can compress any file has been known for decades.
An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)
No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.
(* ) There's a little bit of leeway here because the challenge as stated isn't actually precise about the execution environment. You could probably sneak in a small number of illicit bits by negotiating out-of-band whether the decompressor is to be a C program, ELF binary, Perl script, etc. It's not obvious how to make this useful though.
While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.
Another way to say this is that although you have the 'privilege' of a designing a custom decompressor for this one file, this is not really a benefit since your custom decompressor counts against the space limit. (in contrast to the typical information-theoretic setting where the channel can have an arbitrary pre-specified decoder).
Not a good bet to take.
> my point is that this is not information-theoretically relevant.
Exactly. This whole post is about the challenger trying to be clever with the rules and trying to sidestep the core information theory.
You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros.
Since you can inspect the data before writing the decompressor, if we can figure out how to pad the beginning or end of a byte sequence with five 1s or five 0s in 5 bytes or less, then your expected outcome is $625 (minus $100 to play). Using 6 bytes would give you an expected outcome of $312.5, 7 bytes would give you an expected outcome of $156.
7*'0'+a
That's 7 bytes. It's not really a executable decompressor, but it does capture the necessary steps required to decompress.
Pre-file we can communicate as much as we want without being penalized. We can say for instance that we want our bitstring to be interpreted as an elf binary to be run in ubuntu 14, with specific libraries installed. Or we can say that it will be a zip file. Or we can say that it should be pre-concatenated with 0's. We can specify hundreds of thousands of lines of code that should be compiled now, and then later be executed with the bitstring as input.
Then we get the file, and now every bit we communicate is penalized. If we have asked for a turing-complete format we may now send a decoder specific for the file.
Similar cheats would be to leverage hardware instructions (imagine if x86 had a "pad with N zeros" instruction that fit in 7 bits). That's still cheating because the information is hiding in the architecture.
Assume that you split a m byte string into k byte decompressor and l byte input data. If k+l < m, that is you actually compress, then there are only 2^(k+l) possible output strings. And since
sum_{i=0}^{m-1} 2^i = 2^m -1
But consider a more strongly formulated problem, where you must provide the decompresser and then a file is randomly selected to be put through it - as long as it's still a matter of compressing one particular file it is statistically possible to win (especially at $5000:$100) - The idea being that you can reinterpret data to make certain outputs cheaper while others more expensive.
Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file.
http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
But modern OS's have non-determinism available: take a Kolmogorov-random file of size n which can be generated by a program n+1. Then, replace a certain part of the program (totaling k bits, and delete 2 extra bits) with a function drawing k+2 random bits from the OS. Then with probability 2^-(k+2), you win.
The only approach is to try a perfect kolmogorov compressor, which doesn't exist (well, excepting brute force over the space of possible turing machines).
I think the data is available so you can always try to beat the bet.
A binary string of all ones followed by all zeroes has very low entropy, while a purely random binary string has high entropy. (I think. I'm skimming the Wikipedia article on entropy now)