Equality events and joint information

Try

A comparison device selects one of three symbols a, b, c uniformly. Call its output R. Separately, a source produces a pair (S,T). The source is allowed to correlate its two symbols: in this worked example it outputs (a,a) with probability 1/2, (b,c) with probability 1/3, and (c,a) with probability 1/6. The device operates independently of the entire source pair.

Let A mean “R equals S,” and let B mean “S equals T.” Predict whether learning B changes the probability of A. In the first source row, matching requires R=a; in the second it requires R=b; in the third it requires R=c. Every one of those required device outcomes has probability 1/3.

The matching contributions add to 1/3. Also P(B)=1/2 and P(A∩B)=1/6, their product. Thus A and B are independent, although S and T themselves are not. For example, S=b always accompanies T=c, while T=c has overall probability only 1/3. The independence assumption concerns R versus the whole source pair, not the source components versus one another.

Predict

Predict a stronger claim: does the same matching probability remain after any positive-probability report about the pair, such as “T=a” or “the pair is not (b,c)”? In the table those two reports happen to describe the same rows. Their total probability is 2/3, and their joint probability with A is 1/6+1/18=2/9. Dividing gives 1/3 again.

The reason is not that these particular fractions cancel conveniently. Every allowed pair cell contributes exactly one third of its probability to the equality event. Any collection of cells therefore retains the same fraction. A report with probability zero still satisfies the product definition of independence, but a conditional ratio given that report is undefined. Do not divide by zero to state a stronger conclusion.

Now predict what changes if the device chooses a with probability 3/4 and b with probability 1/4 on a two-symbol alphabet. Independence of the device from the source remains possible, but matching different source symbols no longer has the same probability. Uniformity and full-pair independence are different hypotheses; the proof uses both.

Experiment

Take S uniform on the two symbols a,b and let T=a always. Choose R independently, with probabilities 3/4 for a and 1/4 for b. Build the two source rows and multiply by the probability of the required R value. Find P(A), P(B) and P(A∩B), with the same equality-event definitions.

Reveal the nonuniform calculation

The source rows (a,a) and (b,a) each have probability 1/2. Their equality contributions are 3/8 and 1/8, so P(A)=1/2. Event B occurs only in the first row, hence P(B)=1/2 and P(A∩B)=3/8. This differs from the product 1/4. The source and device are independent, but the device is not uniform. Learning B identifies the symbol S=a, which is more likely to match this device.

For a different failure, use residues 0,1,2. Choose S and T independently and uniformly, then define R to be the residue of −S−T modulo 3. Make nine equally likely rows, one for every ordered pair (S,T). Compute A and B before checking the table.

At each fixed S value, the three R values occur once each, so R is independent of S. The same check at each fixed T proves independence of R and T separately. Yet the two equality events are identical: each has probability 1/3 and their intersection has probability 1/3, not 1/9. Knowing both S and T determines R. Separate marginal checks did not establish independence from the pair.

Understand

Let V be a finite nonempty alphabet with m symbols. S and T take values in V with an arbitrary joint distribution p(s,t)=P(S=s,T=t). The probabilities p(s,t) sum to one; some may be zero. Assume R is uniform on V and independent of the entire pair, meaning

P(R=r,S=s,T=t)=(1/m)p(s,t)

for every triple of symbols. This is stronger than checking R against S and T separately. No independence between S and T is assumed.

Every event determined by the pair can be described by some subset D of V×V: it occurs exactly when (S,T) belongs to D. Denote it E(D). The events specifying distinct pair values are disjoint. Inside the cell (s,t), the equality A requires precisely R=s. Therefore

P(A∩E(D)) = the sum of p(s,t)/m over all (s,t) in D = P(E(D))/m.

Taking D to contain every pair gives P(A)=1/m. Substitution proves P(A∩E(D))=P(A)P(E(D)) for every pair-information event. In particular take D to be the diagonal pairs (s,s) to obtain independence from B, the event S=T. The notation in this paragraph identifies an event by its condition; the finite sum proves the claim without dividing by individual cell probabilities.

If E(D) has positive probability, its conditional equality probability is 1/m. If it has probability zero, the product identity still holds because both sides vanish, while P(A given E(D)) is undefined under the finite conditional formula. These are compatible statements: independence is defined by a product identity, not exclusively by conditional ratios.

For an independent but nonuniform R, write q(s)=P(R=s). The exact same disjoint partition instead gives

P(A∩E(D)) = the sum of q(s)p(s,t) over all (s,t) in D.

There is generally no common factor to pull out. The equality probability is the weighted sum of q(s)P(S=s). Uniformity on all V is a sufficient condition, but is stronger than necessary for a particular source: if q(s) has the same value on every symbol that S can actually take, it still factors out of every nonzero pair cell. Conversely, independence of A from every event S=s of positive probability forces those q(s) values to equal P(A). This identifies precisely which support matters.

Finally, in the ternary construction the relation R=S is equivalent to −S−T≡S modulo 3, hence T≡−2S≡S. Thus A=B algebraically, not merely in a sampled table. Also P(R=0,S=0,T=0)=1/9 differs from P(R=0)P(S=0,T=0)=1/27. This explicitly locates the missing full-pair independence assumption in the counterexample.

Apply

Under the theorem’s hypotheses, conditioning on A preserves the complete distribution of the source pair: each cell’s joint probability with A is p(s,t)/m, and division by P(A)=1/m gives p(s,t) back. Does that imply every random variable in the experiment retains its distribution?

Test S=a always, T uniform on three symbols and R independently uniform on the same three symbols. Event A is exactly R=a. Conditioning on A forces R=a, so R’s distribution changes completely, while the source pair’s distribution remains unchanged. The theorem specifies which information is independent; it does not erase all dependence involving the equality event.

For a changed support example, let R have probabilities 1/4,1/4,1/2 on a,b,c, and let S take only a and b. Let T have any joint law with S, independently of R. The matching weight is always 1/4 on the source support, so A is independent of every pair-information event despite R being nonuniform on the unused symbol c. Verify this by the weighted-sum formula rather than by announcing that nonuniformity always causes failure.

The singleton alphabet also fits the theorem: all variables equal its unique symbol and A is certain. An empty alphabet does not support a uniform probability distribution with total mass one, so m≥1 is a genuine domain condition.

Continue

The practice asks for exact tables, general finite-sum proofs and counterexamples with each independence hypothesis checked. Separate three claims: R is uniform, R is independent of each marginal, and R is independent of the joint pair. None should be substituted for another without proof.

When applying the result, identify the information event as a set of pair cells, check the device’s law and its independence from that pair, and retain the positive-probability condition only where a conditional ratio is actually used. A finite counterexample can refute an overbroad statement; the general partition proof establishes the theorem for arbitrary finite joint laws.