1
$\begingroup$

Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are equal, give wildly wrong results? Here is a MatLab program that exemplifies that, also available on my blog:

% Ovo je MatLabski program koji uspoređuje rezultate koje daje moj algoritam
% procjenjivanja entropije s rezultatima koje daje Shannonov algoritam.
suglasnici = 'bcdfghjklmnpqrstvwxyz';
testni_stringovi=cell(100 - length(suglasnici) + 1, 1);
for koliko_cemo_staviti_b_ova = 100 - length(suglasnici) + 1 : -1 : 1
  for i = 1 : koliko_cemo_staviti_b_ova
    testni_stringovi{koliko_cemo_staviti_b_ova} = [
      testni_stringovi{koliko_cemo_staviti_b_ova} 'b'
    ];
  end
  for i = 1 : 100 - koliko_cemo_staviti_b_ova
    testni_stringovi{koliko_cemo_staviti_b_ova} = [
        testni_stringovi{koliko_cemo_staviti_b_ova} suglasnici(int32(floor((i - 1) / (100 - koliko_cemo_staviti_b_ova) * (length(suglasnici) - 1))) + strfind(suglasnici, 'c'))
        ];
  end
end
samarzijine_entropije = [];
shannonove_entropije = [];
for i = 1 : length(testni_stringovi)
  str = testni_stringovi{i};
  samarzijine_entropije = [samarzijine_entropije samarzijina_entropija(str)];
  shannonove_entropije = [shannonove_entropije shannonova_entropija(str, suglasnici)];
end
sgtitle('Usporedba Shannonove i Samarzijine entropije generiranih stringova');
subplot(1,2,1);
plot(shannonove_entropije, samarzijine_entropije);
xlabel('Shannonova entropija');
ylabel('Samarzijina entropija');
subplot(1,2,2);
plot(shannonove_entropije);
hold on;
plot(samarzijine_entropije);
xlabel('Broj b-ova u stringu');
ylabel('Entropija (bit/simbol)');
legend('Shannonova entropija', 'Samarzijina entropija');
function ret = shannonova_entropija(str, suglasnici)
  apsolutne_frekvencije = [];
  for i = 1 : length(suglasnici)
    apsolutne_frekvencije = [apsolutne_frekvencije 0];
  end
  for i = 1 : length(str)
    znak = str(i);
    apsolutne_frekvencije(strfind(suglasnici, znak)) = apsolutne_frekvencije(strfind(suglasnici, znak)) + 1;
  end
  relativne_frekvencije = apsolutne_frekvencije / length(str);
  ret = 0;
  for relativna_frekvencija = relativne_frekvencije
    if relativna_frekvencija > 0
      ret = ret - log2(relativna_frekvencija) * relativna_frekvencija;
    end
  end
end
function ret = samarzijina_entropija(str)
  broj_pokusaja = 10000;
  broj_pogodaka = 0;
  for i = 1 : broj_pokusaja
    prvi = int32(floor(rand() * length(str) + 1));
    drugi = int32(floor(rand() * length(str) + 1));
    if str(prvi) == str(drugi)
      broj_pogodaka = broj_pogodaka + 1;
    end
  end
  omjer_pogodaka = broj_pogodaka / broj_pokusaja;
  ret = -log2(omjer_pogodaka);
end

Here is what outputs:
What the MatLab program outputs
So, what is going on here? I would expect the curve on the left to be approximately a y=x straight line, and the curves on the right to be approximately identical. But obviously, they are not. My algorithm for estimating the entropy gives close-to-correct results (or slightly overestimates them) when the entropy of the string in question is high, but it severely underestimates entropies of low-entropy strings.

$\endgroup$
15
  • 1
    $\begingroup$ Why do you expect it to work? $\endgroup$ – Yuval Filmus Apr 17 at 15:13
  • $\begingroup$ Consider a source of the form $0101010101\ldots$ How would you differentiate it from a completely random source? $\endgroup$ – Yuval Filmus Apr 17 at 15:13
  • 1
    $\begingroup$ You seem to be estimating what is known as collision entropy, which is different from Shannon entropy. In both cases, you are estimating the entropy of the empirical distribution of the text. $\endgroup$ – Yuval Filmus Apr 17 at 18:54
  • 1
    $\begingroup$ You can start with the Wikipedia article. The subject might also be covered in standard textbooks such as Cover & Thomas' Elements of Information Theory. $\endgroup$ – Yuval Filmus Apr 17 at 18:59
  • 2
    $\begingroup$ We discourage posting code. Not everyone reads Matlab. Instead, please use concise pseudocode or mathematics. This is not a coding site and code is off-topic here. $\endgroup$ – D.W. Apr 18 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.