Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The undeserved status of the pigeon-hole principle (1991)

cs.utexas.edu

Post reply on HN
Print view View original

31–37 of 37 posts

Re: The undeserved status of the pigeon-hole principle (1991)

#31

Post by morelisp »

atq2119 wrote: post #30
morelisp wrote: post #21

Earlier quoted context omitted.

This is still the pigeonhole principle, just inverted - If you have more holes than pigeons (and you can’t make fractional or quantum pigeons) at least one hole must have no pigeons.

It's similar, but that's not usually referred to as the pigeon hole principle.

It's more than similar, it's gone from talking about the necessary properties of a function with an image smaller than its domain, to the impossibility of an inverse function as the image cannot be larger than its domain.

We might as well call this "the whole-pigeon principle."

Re: The undeserved status of the pigeon-hole principle (1991)

#32

Post by kd0amg »

bloaf wrote: post #18
starchild_3001 wrote: post #13

I (or any math noob) can easily understand the pigeon hole principle. His more detailed arguments about max, avg and a bunch of other stuff is more obtuse and harder to follow. IMO, pigeon hole principle, where applicable, wins this argument. If you're dealing with a sequence of real numbers, you might need max >= avg.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

Yes, talking about averages sounds like it might lead a prover astray into reasoning about the average size of compressed data. The average that matters here though is how many inputs map to the same output.

Compressing (n+1)-bit input to n-bit output makes the average output correspond to 2^(n+1)/2^n = 2 inputs. By Dijkstra's rephrasing of the pigeonhole principle, the maximum number of inputs colliding on the same output must be at least 2.

Or we could make it more robust and say we're compressing to n-bit-or-smaller output. Then the average output corresponds to 2^(n+1)/(2^(n+1)-1) inputs. That average is still strictly greater than 1, so the maximum number of inputs colliding on the same output must also be strictly greater than 1 (at least 2, since that's the smallest natural which is greater than 1).

Re: The undeserved status of the pigeon-hole principle (1991)

#33

Post by Dylan16807 »

phaemon wrote: post #27
bloaf wrote: post #18

Earlier quoted context omitted.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

A "file" on a computer is just a number. When you compress a file, you are representing a big number with a small number. There are more big numbers than there are small numbers.

You've just expressed part of the problem with numbers, you haven't tied them into averages and minimums/maximums.

Re: The undeserved status of the pigeon-hole principle (1991)

#34

Post by FartyMcFarter »

The pigeonhole principle is about counting things.

Counting things is one of the simplest things in mathematics. Much simpler than "averages", "real numbers" (a very complicated subject) and other things Dijkstra mentions in his alternative formulation.

It seems like he's sacrificing simplicity and ease of understanding for other properties that aren't generally applicable.

Re: The undeserved status of the pigeon-hole principle (1991)

#35

Post by phaemon »

Dylan16807 wrote: post #33
phaemon wrote: post #27

Earlier quoted context omitted.

A "file" on a computer is just a number. When you compress a file, you are representing a big number with a small number. There are more big numbers than there are small numbers.

You've just expressed part of the problem with numbers, you haven't tied them into averages and minimums/maximums.

Why is that required?

Re: The undeserved status of the pigeon-hole principle (1991)

#36

Post by Dylan16807 »

phaemon wrote: post #35
Dylan16807 wrote: post #33

Earlier quoted context omitted.

You've just expressed part of the problem with numbers, you haven't tied them into averages and minimums/maximums.

Why is that required?

The prompt you were responding to was "I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand."

Specifically, they were looking for how you write the can't-always-compress proof using formulation (1)

Re: The undeserved status of the pigeon-hole principle (1991)

#37

Post by phaemon »

Dylan16807 wrote: post #36
phaemon wrote: post #35

Earlier quoted context omitted.

Why is that required?

The prompt you were responding to was "I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand." Specifically, they were looking for how you write the can't-always-compress proof using formulation (1)

Oh right. I read it as "how else could you explain it simply". I always thought the pigeon hole principal was a needless metaphor.
Post reply on HN