I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made.

The statistical experiment is very simple and is as follows:

We have a random source that generates symbols belonging to an alphabet A that contains ten symbols therefore, |A|=10 with uniform distribution so, the emission probability of each symbol is 1/10.

Using this source, simulate 1000 sequences made up of 1000 symbols therefore having length N = 1000.

We encode these sequences using arithmetic coding, under the hypothesis that the encoder does not know the source and consequently calculates the frequencies of each symbol every time that a sequence arrives.

Now, you simulate 10000 sequences (with the same source) but with N=1001, so you have one more symbol than in the previous case. Encode the 10000 simulated sequences with the same algorithm. Select 1000 sequences, from 10000 sequences encoded, that have been encoded with the fewest bits.

In this way, we have two sets containing 1000 sequences encoded with the same algorithm under the same hypothesis.

Now, I ask you the following question: which of the two sets has a smaller size?

The interesting aspect is not the choice you make but the justification you give for your choice.

Try to answer without running the simulation, in such a way that your justification is not affected by the result.

  • 2
    $\begingroup$ Your wording makes it sound like you are assigning work to readers here, which is not the purpose of this site. What are your thoughts? Questions must demonstrate a minimal understanding of the problem being solved. Tell us what you've tried to do, why it didn't work, and how it should work. What is the motivation for your question? Why should we care? What's the context where you encountered this? Are you sure you have credited the original source of all copied material? How is this a research-level question? $\endgroup$
    – D.W.
    Jun 7, 2022 at 6:01
  • $\begingroup$ Honestly, I do not understand such an aggressive reaction. It is simply a very complex problem, whose theoretical discussion can lead to many interesting ideas. Maybe there’s some information theory expert who can find this stimulating problem. If you are not interested, you can simply move on to anything else. $\endgroup$
    – Alix
    Jun 7, 2022 at 10:36
  • 5
    $\begingroup$ This site works differently from others you might be used to. We are not a discussion forum (and we're not here for opinion polls). As you're a new member here, perhaps I can encourage you to take a look around and get familiar with the norms and expectations here? $\endgroup$
    – D.W.
    Jun 7, 2022 at 17:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.