Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is not homework but an actual problem.

We flip a fair coin ten times. This gives A$_1$ to A$_{10}$. Each coin toss = 10 bits. We flip another fair coin ten times. This gives B$_1$ to B$_{10}$. So we have another 10 bits.

We calculate C from A$_n$ minus B$_n$ (that is A$_1$ minus B$_1$ and so on) giving us 10 outcomes (C$_1$ to C$_{10}$).

What is the total bits of this "experiment"? Is it 20 or 30 bits? The confusion is whether C increases the bits of the experiment, or whether the fact it is based on the previous coin tosses doesn't increase it?

Update: I am trying to work out the bits of an experiment I have done that is essentially based on the coin-toss (p = $\frac{1}{2}$). This should illustrate the problem:

I have a female who says she can correctly guess the outcome of a coin toss, but only in the morning. We do 10 guesses in the morning (10 bits, this is A above) and 10 in the afternoon (10 bits, this is B above). We also calculate a total score based on morning minus the afternoon (this is C above).

Does the calculation of the total (C) add bits to the experiment over the 20 bits of the morning and afternoon (A and B)?

share|improve this question
    
There is confusion bout what it means to subtract bits. If you view them as integers $0$ or $1$, then there are three possible outcomes, $-1$, $0$, $1$. If you view them as values modulo $2$, then the subtraction gives another bit, and there are two posible outcomes. You need to specify which interpretation you intend. –  Marc van Leeuwen Mar 6 '13 at 10:17
    
@MarcvanLeeuwen I am not a mathematician, but a psychologist. I hope the information I have added improves the question? –  Frank_Zafka Mar 6 '13 at 10:27
1  
Does the calculation of C add bits to the experiment? Well, it cannot since C is produced deterministically from A and B. As I explain below, the information in C cannot be more than the sum of the informations in A and B. –  Did Mar 6 '13 at 10:31
1  
You cannot add the information content of C to those of A and B since C is deterministically produced by A and B. Imagine that I give you A (content 10 bits) and then that I give you again A (again, content 10 bits), you would not say I gave you 10+10=20 bits, would you? With A, B and C, things are even worse since you give me A (for 10), then B (for 10), then C whose content adds nothing from what I already knew reading A and B... To sum up: C alone = 15 bits and A + B = A + B + C = 20 bits. –  Did Mar 6 '13 at 10:39
1  
@RSoul: You still did not make clear what C looks like. Your addition makes me think that you are subtracting total scores, not individual bits. There is no reason to compare the 3rd guess in the afternoon specifically with the 3rd guess in the morning. So is C (i) a sequence of 10 values, each $-1$, $0$, or $1$, or (ii) a sequence of 10 values, each $0$, or $1$ (for same or different outcome), or (iii) a single number between $-10$ and $10$ that tells how much better your woman performed in the morning than in the afternoon, or (iv) something else yet? –  Marc van Leeuwen Mar 6 '13 at 11:05

1 Answer 1

up vote 3 down vote accepted

Based on its entropy, the sequence C contains $15$ bits.

Each C outcome is $-1$ with probability $\frac14$ (if the A and B outcomes are $0$ and $1$ respectively), $+1$ with probability $\frac14$ (if the A and B outcomes are $1$ and $0$ respectively), and $0$ with probability $\frac12$ (if the A and B outcomes coincide).

Hence it corresponds to $H$ bits, where $H$ is the (binary) entropy of a discrete measure with weights $(\frac14,\frac14,\frac12)$, that is, $H=-\left(\frac14\log_2\frac14+\frac14\log_2\frac14+\frac12\log_2\frac12\right)=\frac32$.

Thus $10$ outcomes of type C correspond to $10\cdot H=15$ bits.

Edit: Since C is obtained from A and B, the information content of C should be less than the sum of those of A and B. Note that A contains $10$ bits, B contains $10$ bits, A and B are independent hence A and B together contain 20 bits. In the other direction, starting from C, one obtains a sequence statistically similar to A or B forgetting the signs in C, hence the information content of C should be greater than the one of A, which is 10 bits.

Edit-edit: Here is a way to produce sequences of type C with length L which makes apparent why these contain $1\frac12$ times L bits of information. Start from a long sequence D of standard $0$-$1$ bits. Transform each of the first L bits which is at $1$ into $1$ or $-1$, using a later bit in the D sequence, and keep at $0$ each of the first L bits which is at $0$. To get a C sequence of length L, one uses roughly L + $\frac12$ times L bits from D. Since D can be reconstructed from C, the information content of C of length L is the number of D bits used, that is, $1\frac12$ times L bits.

share|improve this answer
    
So total entropy (A + B + C) = 48? –  Frank_Zafka Mar 5 '13 at 20:09
1  
@RSoul: The total entropy of all three sequences is the same as the total entropy of just the A and B sequences, because these completely determine C. –  Andreas Blass Mar 5 '13 at 20:14
    
@AndreasBlass That was my initial thought. Now I'm properly confused. –  Frank_Zafka Mar 5 '13 at 20:15
    
@Did That seems reasonable. But what do I know? That's why I asked the question in the first place... –  Frank_Zafka Mar 5 '13 at 20:58
1  
@RossMillikan C is not producing bits but three-valued signs. –  Did Mar 6 '13 at 7:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.