ExampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A finite information-bottleneck privacy model

Statement

Let $S$ be a fair bit, let $N \sim Bernoulli (1 / 10)$ be independent, and set $Y = S \oplus N$ . For every finite stochastic release kernel $K (z ∣ y)$ , the induced law is $S - Y - Z$ . With $h (p) : = - p \ln p - (1 - p) \ln (1 - p)$ and $0 \ln 0 : = 0$ ,

$I (Y; Z) - \frac{1}{2} I (S; Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10),$

and equality is attained by releasing $Z = Y$ (or any bijective relabeling of $Y$ ). If $I (S; Z) = 0$ , then necessarily $I (Y; Z) = 0$ for every such release kernel.

Facts & Assumptions

Given: A fair sensitive bit $S$ , independent noise $N \sim Bernoulli (1 / 10)$ , useful bit $Y = S \oplus N$ , and a finite release kernel $K (z ∣ y)$ .

[F1]

Finite-source privacy–utility region: the kernel induces $P_{S Y Z} = P_{S Y} K_{Z ∣ Y}$ , written $S - Y - Z$ , with leakage $I (S; Z)$ and retained-information utility $I (Y; Z)$ .

[F2]

Finite mutual information: mutual information is finite joint-law KL in nats.

[F3]

Finite conditional entropy: conditional entropy is the finite average of the conditional entropies, with zero-mass branches omitted.

[F4]

Finite entropy and mutual-information chain rules: mutual information equals the corresponding entropy difference and the finite entropy chain rule holds.

[F5]

A finite kernel criterion for perfect privacy: $I (S; Z) = 0$ exactly when each positive-support conditional output law $P_{Z ∣ S = s}$ is the same across $s$ .

[F6]

Finite distributions, entropy, divergence, and stochastic matrices: finite entropy is $H (p) = - \sum_{p_{i} > 0} p_{i} \ln p_{i}$ with $0 \ln 0 = 0$ .

Proof

1.1F1F3F6givenalgebra

The fair bit $S$ has entropy $\ln 2$ . Since $S$ is fair and independent of the symmetric noise, $Y$ is fair as well. Given either value of $Y$ , the posterior error probability for estimating $S$ is $1 / 10$ , so $H (S ∣ Y) = h (1 / 10)$ . The factorization in [F1] is $P_{S Y Z} = P_{S Y} K_{Z ∣ Y}$ .

2.1F1F2F3F4F6step 1.1algebra

Using [F2] and [F4], expand the objective as $I (Y; Z) - \frac{1}{2} I (S; Z) = \frac{1}{2} \ln 2 - H (Y ∣ Z) + \frac{1}{2} H (S ∣ Z) .$ The conditional-entropy chain rules in [F4] give $H (S, Y ∣ Z) = H (S ∣ Z) + H (Y ∣ S, Z) = H (Y ∣ Z) + H (S ∣ Y, Z)$ . By [F3] and [F6], $H (Y ∣ S, Z) \geq 0$ and $H (Y ∣ Z) \geq 0$ , so $H (S ∣ Z) \leq H (S, Y ∣ Z)$ . The factorization in [F1] gives $P_{S ∣ Y, Z} = P_{S ∣ Y}$ on positive-mass pairs, hence $H (S ∣ Y, Z) = H (S ∣ Y) = h (1 / 10)$ by step 1.1. Therefore $H (S ∣ Z) \leq H (Y ∣ Z) + h (1 / 10)$ , and $I (Y; Z) - \frac{1}{2} I (S; Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10) - \frac{1}{2} H (Y ∣ Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10)$ .

2.2F2F3F4step 1.1algebra

For the identity release $Z = Y$ , $H (Y ∣ Z) = 0$ and step 1.1 gives $I (S; Y) = H (S) - H (S ∣ Y) = \ln 2 - h (1 / 10)$ . Substitution gives equality in the bound. A bijective relabeling preserves these conditional entropies and mutual informations, so also attains equality.

3.1F1F5step 1.1algebra∎

Suppose $I (S; Z) = 0$ . By [F5], for each $z$ with $P_{Z} (z) > 0$ , the two rows of $P_{Z ∣ S}$ agree. If $P_{Z} (z) = 0$ , then $0 = \frac{1}{2} P (z ∣ S = 0) + \frac{1}{2} P (z ∣ S = 1)$ , and nonnegativity forces both entries to be zero, so the rows agree for every release value. With row order $s = 0, 1$ and $y = 0, 1$ , the binary symmetric channel matrix from $S$ to $Y$ is $T = (\begin{array}{cc} 9 / 10 & 1 / 10 \\ 1 / 10 & 9 / 10 \end{array}),$ so for the column $k_{z} = (K (z ∣ 0), K (z ∣ 1))^{T}$ the output column is $T k_{z} = c_{z} (1, 1)^{T}$ for some $c_{z}$ . Since $\det T = 4 / 5 \neq 0$ and $T (1, 1)^{T} = (1, 1)^{T}$ , invertibility gives $k_{z} = c_{z} (1, 1)^{T}$ . This holds for every $z$ , so the two rows of $K$ coincide and $Y, Z$ are independent. Therefore $I (Y; Z) = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ali Makhdoumi, Salman Salamatian, Nadia Fawaz, and Muriel Médard, From the Information Bottleneck to the Privacy Funnel, ITW 2014 (standard reference, not scraped)
Paul Cuff, Princeton ELE 538: Information Theoretic Security, Lecture 15 (standard reference, not scraped)