Dice Entropy – A Programming Challenge

Given the importance of information theory to some intelligent design arguments I thought it might be nice to have a toolkit of some basic functions related to the sorts of calculations associated with information theory, regardless of which side of the debate one is on.

What would those functions consist of?

Over in the In Slight Defense of Granville Sewell thread there’s a discussion going on between myself and keiths over the entropy of a pair of dice. A tempest in a teapot I’m sure, with any disagreement probably revolving around his use of the Boltzmann equation and my use of the Shannon measure.

Perhaps we can have some fun and learn something as well. Here’s a programming challenge:

Write the code necessary to calculate the entropy of a pair of standard six-sided dice.

What functions should we write to do this? Please explain your code. Extra credit for writing tests to validate the code. Let me know if you have any questions.

33 thoughts on “Dice Entropy – A Programming Challenge”

1. Feel free to offer your comments on probability, statistics, and information theory. No rule against making this thread informative as well as boring.

2. According to Mung, there is no such thing as a random throw of dice so therefore the entropy is whatever his god wants it to be – it depends on what way his god adjusts it.

So therefore it is impossible to calculate such a value as Mung’s god can change it on a whim.

To appeal to an omnipotent deity is to allow that at any moment the regularities of nature may be ruptured, that Miracles may happen and that the entropy of a pair of dice can be changed without regard to it’s previous value.

3. Normally in such a challenge, I’d post my code first and ask others to critique it and/or provide their own to compare with.

Will you be writing code Mung? Or just asking others to?

4. Mike Elzinga has a great entropy concept test:

The following is an elementary concept test.

Take a simple system made up of 16 identical atoms, each of which has a non-degenerate ground state and a single accessible excited state.

1. What is the entropy when all atoms are in the ground state?

2. Add just enough energy to put 4 atoms in the excited state. What is the entropy now?

3. Add more energy so that 8 atoms are in the excited state. What is the entropy now?

4. Add still more energy so that 12 atoms are in the excited state. What is the entropy now?

5. Add more energy so that all atoms are in the excited state. What is the entropy now?

6. Rank order the temperatures in each of the above cases.

After completing the test, generalize the number of atoms to an arbitrary size N and plot the temperature versus energy.

Explain what is “ordered” or “disordered” and what is “information” in the above calculations.

It would be interesting to see the various participants in the other thread provide their answers. I volunteer to hold them all for simultaneous release.

5. So the first method I decided I needed was one to sum the values in a collection. Turns out that a sum method already exists in Python and there will be one in the next version of Ruby, but there isn’t one in the current version of Ruby.

A sum() method is available in Rails, one could use just the needed rails gem, but that’s a bit of overkill for this project. The method itself is simple enough to write.

But why a sum method? Well, say, I want to calculate probabilities from frequencies or make sure all my probabilities add up to 1.

For the case of a pair of dice I need a way to count the “ways”. For each number I can count the ways to to roll that number and then sum of all of them.

1 way to roll a two
2 ways to roll a three
3 ways to roll a 4
4 ways to roll a 5
5 ways to roll a six
6 ways to roll a seven
5 ways to roll an eight
4 ways to roll a nine
3 ways to roll a ten
2 ways to roll an eleven
1 way to roll a twelve
—–
36 ‘ways’

I’ll post my code and tests in another post.

6. Patrick: It would be interesting to see the various participants in the other thread provide their answers. I volunteer to hold them all for simultaneous release.

Well, given that the entropy can be different depending on the observer, I have no fear of being wrong. Do you have the “correct” answers?

7. OMagain: Normally in such a challenge, I’d post my code first and ask others to critique it and/or provide their own to compare with.

Of course you would, but you’re a far better coder than I am.

8. require ‘minitest/autorun’

def sum(array)
array.inject(0, :+)
end

class SumTest < MiniTest::Test

def test_sum_with_empty_array
assert_equal 0, sum([]), "summed elements of an empty array should be zero"
end

def test_sum_of_a_pair_of_dice
assert_equal 36, sum([1,2,3,4,5,6,5,4,3,2,1])
end

def test_sum_of_probabilities
assert_equal 1.01, sum([0.03,0.06,0.08,0.11,0.14,0.17,0.14,0.11,0.08,0.06,0.03])
end

def test_sum_of_frequencies_as_probabilities
s = 36.0
assert_equal 1.0000000000000002, sum([1/s,2/s,3/s,4/s,5/s,6/s,5/s,4/s,3/s,2/s,1/s])
end
end

9. Test results:

D:\projects\information_theory>ruby test_sum.rb
Run options: –seed 37497

# Running:

….

Finished in 0.002068s, 1934.2360 runs/s, 1934.2360 assertions/s.

4 runs, 4 assertions, 0 failures, 0 errors, 0 skips

D:\projects\information_theory>

10. Of primary interest for our Dice Entropy is the sum of the number of ways the sum of two dice can be obtained:

1 way to throw a 2
2 ways to throw a 3
3 ways to throw a 4
4 ways to throw a 5
5 ways to throw a 6
6 ways to throw a 7
5 ways to throw an 8
4 ways to throw a 9
3 ways to throw a 10
2 ways to throw an 11
1 way to throw a 12
—-
36 ‘ways’

And that is because from the frequency and the sum we can calculate the probability, by dividing the frequency by the sum:

D:\projects\information_theory>ruby -e ‘puts 4/36.0’
0.1111111111111111

And given that, we can create a probability distribution.

And from the probability distribution we can calculate the entropy.

Or so says the source I am ‘cribbing’ from. 🙂

11. require ‘minitest/autorun’

def shannon_entropy(probability_distribution)
probability_distribution.inject(0) {|sum, px| sum + px * Math.log2(1.0/px)}
end

class EntropyTest < MiniTest::Test

def test_entropy_from_uniform_distribution_4
distribution = Array.new(4) {1.0 / 4}
assert_equal 2, shannon_entropy(distribution)
end

def test_entropy_from_uniform_distribution_8
pr = 1.0 / 8
assert_equal 3, shannon_entropy([pr,pr,pr,pr,pr,pr,pr,pr])
end

def test_entropy_from_uniform_distribution_16
distribution = Array.new(16) {1.0 / 16}
assert_equal 4, shannon_entropy(distribution)
end
end

12. Test results:

D:\projects\information_theory>ruby test_entropy.rb
Run options: –seed 18023

# Running:

Finished in 0.000000s, Inf runs/s, Inf assertions/s.

3 runs, 3 assertions, 0 failures, 0 errors, 0 skips

D:\projects\information_theory>

13. Richardthughes: Mung, why not code your probabilities as fractions, 1/36, 2/36 etc?

Hi. Good to see you. I think I am doing that. To know the fraction I have to know the sum. I’ve chosen to calculate the sum rather than hard code it.

My next post will show the results using fractions, and the following post will show the test results. Let me know if you have any questions.

14. require ‘minitest/autorun’

def shannon_entropy(probability_distribution)
probability_distribution.inject(0) {|sum, px| sum + px * Math.log2(1.0/px)}
end

class EntropyTest < MiniTest::Test

def test_entropy_from_non_uniform_distribution_dice_pair
sum = 36.0
distribution = [1,2,3,4,5,6,5,4,3,2,1].map {|ways| ways/sum}
assert_equal 3.27, shannon_entropy(distribution)
end
end

15. Test results:

D:\projects\information_theory>ruby dice_entropy.rb
Run options: –seed 49598

# Running:

F

Finished in 0.000000s, Inf runs/s, Inf assertions/s.

1) Failure:
EntropyTest#test_entropy_from_uniform_distribution_8 [dice_entropy.rb:13]:
Expected: 3.27
Actual: 3.2744019192887706

1 runs, 1 assertions, 1 failures, 0 errors, 0 skips

D:\projects\information_theory>

16. So there you have it. I’ve calculated the Shannon entropy for a pair of dice. Not only that, but I have written and provided the functions to do so (in Ruby). The code is here for everyone to see.

The value is close enough to the value of 3.27 which I provided in the In Slight Defense of Granville Sewell thread.

17. keiths: 3.27 bits/symbol is the answer to the wrong problem, as I explained here.

Are you saying it fails to calculate the Shannon entropy? Or are you saying that the problem you presented cannot be solved in terms of Shannon entropy?

Is there any chance you’ll present your own coding solutions to how to calculate Shannon entropy?

18. Why would I waste time coding it, Mung? It’s the concepts that matter, and you still haven’t grasped them.

19. OMagain: Normally in such a challenge, I’d post my code first and ask others to critique it and/or provide their own to compare with.

We’re all waiting for your code.

20. I responded in the other thread.

Sorry for the delay in replying. Life is still too interesting by half.