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.
