Re: More of an Algorithems question

On Thu, 17 Nov 2005 17:59:28 +0000 (UTC), Dave Seaman
<dseaman@xxxxxxxxxxxx> wrote:

>On Thu, 17 Nov 2005 12:51:17 -0500, quasi wrote:
>> On Thu, 17 Nov 2005 17:21:45 +0000 (UTC), Dave Seaman
>><dseaman@xxxxxxxxxxxx> wrote:
>
>>>On Thu, 17 Nov 2005 12:15:12 -0500, quasi wrote:
>>>> On Thu, 17 Nov 2005 15:07:58 GMT, cri@xxxxxxxx (Richard Harter) wrote:
>>>
>>>>>On 15 Nov 2005 14:55:51 -0800, "Filter" <filtermedialtd@xxxxxxxxx>
>>>>>wrote:
>>>>>
>>>>>>
>>>>>>Hi,
>>>>>>
>>>>>>How can I proove that no Algorithm can compress every file of length
>>>>>>10^6?
>>>>>
>>>>>However there is an algorithm that will losslessly compress every file
>>>>>of length 10^6 except one.
>>>>>
>>>
>>>> I don't believe that.
>>>
>>>> The pigeonhole principle applies easily to invalidate such a claim ...
>>>
>>>> Let n=10^6.
>>>
>>>> There are 2^n possible files with n bits, but only 2^(n-1) files with
>>>> n-1 bits. Hence, at most half the files can be compressed.
>>>
>>>There are 2^n-1 files with fewer than n bits. Hence, the claim stands.
>
>> Not by my count.
>
>> For example, 16 possible files with 4 bits but only 8 possible files
>> with 3 bits, no?
>
>Are there any other files with fewer than 4 bits that you have overlooked in
>your count?

Ok, I see my confusion.

I failed to take into account files with less than (n-1) bits.

I get it now -- thanks.

quasi
.

Relevant Pages

  • Re: More of an Algorithems question
    ... >I failed to take into account files with less than (n-1) bits. ... In any lossless compression scheme, less than half of the files with n ... Prev by Date: ...
    (sci.math)
  • Re: Compact connected Hausdorff
    ... > of U are also open in X (a relatively open subset of an open set is ... > What am I missing? ... Prev by Date: ...
    (sci.math)
  • Re: Rational and irrational numbers
    ... yourself, and where possible, go for depth of understanding -- after ... all, you're deepkdeb. ... Prev by Date: ...
    (sci.math)
  • Re: Random choice of numbers
    ... quasi writes: ... For n in N, n> 2, let pbe the probability that if n numbers are ... Prove or disprove: pis rational, ... Of course if n-1 is divisible by k, ais divisible by n^k - ^k. ...
    (sci.math)
  • Re: Nearing breakthrough...need magic :-)
    ... e = (n-1)! ... Regards, ... Mike. ... Prev by Date: ...
    (sci.math)