Calculating Entropy for Independent Coin Toss Sequences with Varying Differences

[entropy1]

If we have two sequences s1 and s2, both of N coin tosses, is the entropy of getting two sequences that are exactly the same then lower than sequences of which can be said that they differ by x incident tosses? Is the entropy of getting sequences s1 and s2 that differ by N/2 tosses the highest, and is that the reason we most probably get sequences s1 and s2 that differ by about N/2 tosses?

 

[jambaugh]

I believe you misunderstand how entropy applies to probability. There is a singular probability of getting two sequences exactly the same. It is not meaningful to refer to the entropy of such a singular event but rather entropy applies to distributions of probability over many events. So for example if X = the number of differences in the two sequences then there is a single entropy for the probability distribution of X.

Note also that the entropy of a distribution over a discrete finite set of outcomes is maximized when all outcomes are equally likely. But once you begin applying constraints such as the distribution must have a given mean and/or variance etc... then you get more interesting distributions when you maximize entropy.

 

[entropy1]

I believe you misunderstand how entropy applies to probability. There is a singular probability of getting two sequences exactly the same. It is not meaningful to refer to the entropy of such a singular event but rather entropy applies to distributions of probability over many events. So for example if X = the number of differences in the two sequences then there is a single entropy for the probability distribution of X.

I am not sure I understand you, but I was talking about entropy E(x) of s1 and s2 differing in x places, so all the {s1,s2} pairs that differ in x places.

Note also that the entropy of a distribution over a discrete finite set of outcomes is maximized when all outcomes are equally likely.

So all sequences have probability $2^{-N}$.

 

[jambaugh]

Ok, here's my understanding to more precision. As I said entropy applies to distributions but you can also refer to the entropy of an event (set of elementary outcomes) by equating that to the probability of the conditional probability distribution $P(case | case \in E)$. That still depends on the base distribution. In your example, given the assumed fairness of the coins in question each sequence of tosses would be equally probable with probability $2^{-N}$.
Since you are describing two independent sequences of tosses though that would be squared for the probability of a given pair of sequences. It depends on what you want to call the most elementary outcome.

Given that then you pick your even, e.g. that x pairs match between the two sequences and count the number of elementary outcomes in that set. Let's see that will be $2^N$ ways the first sequence can go times ${}_NC_x=\frac{N!}{x!(N-x)!}$ ways to pick $x$ of the second sequence to disagree with the first. The conditional probability distribution is then $q= 1/count = 1/({}_NC_x2^N)$ for those cases and zero otherwise. The entropy of (the conditional distribution for) that event is then:
$$S = \sum_{cases} -q\log(q) = -\log(q) = \log(count)$$

You may say I could have gotten here a bit quicker but consider how things change if the coin is not fair. You'll need to go through this definition since not all elementary outcomes is equally probable and you will need to go through this calculation with the corresponding distributions.