Monte Carlo Experiment in Huffman

I have an exercise in which I have a random variable X = {1, 2, 3} with probabilities 1/2, 1/4, 1/4.

Apply Huffman coding in x (1..n), where x vector. Repeat for 1000 Monte Carlo experiments. What does the second part of the question mean?

Thanks

Answer 1

[George Karystinos]

Thalia den rotame sto matlab answers gia ta project. kovesai! :)

Answer 2

[Walter Roberson]

for generation = 1 : 1000
  X = generate_symbols(N);
  H = huffman_compress(X);
  HS(generation) = numel(H);            %how much space did it take?
end

Answer 3

[Roger Stafford]

In case you don't have access to a huffman compression algorithm, I would expect in your particular case the huffman encoding would be

   1 <--> 0
   2 <--> 10
   3 <--> 110
   4 <--> 111

See these websites for further information:

   https://en.wikipedia.org/wiki/Huffman_coding
   https://en.wikipedia.org/wiki/Variable-length_code#Uniquely_decodable_codes

Answer 4

[T]

My problem is that I don't know what Monte Carlo is. I searched in Google and it didn't help me, since I don't have random probabilites.

[Roger Stafford]

Here's how you would produce the values 1, 2, 3, or 4 with probabilities of 1/2, 1/4, 1/8, and 1/8 respectively:

   r = rand(n,1);  % Generate n random numbers between 0 and 1
   x = 1*(r<=1/2) + 2*((r>1/2)&(r<=3/4)) ...
       + 3*((r>3/4)&(r<=7/8)) + 4*(r>7/8);

The values of x will have the given probabilities. Such a procedure is known as a Monte Carlo method.

Answer 5

[George Karystinos]

Thalia mono i vandi ekane kariera me allo onoma, kserw oti eisai esu miss T, mn krivesai