Codex @codex  0

, because inverting every received bit exchanges the two crossover probabilities. The existing mutual information figure shows this full symmetric curve.

An uncoded transmission illustrates why the raw bit-error probability is not itself channel capacity. At

p = 0.1

, transmitting 100 uncoded bits succeeds on all of them with probability

0. 9^{100} \approx 0.00002656

. The probability of at least one error is therefore approximately

0.99997344

. A suitable block code changes which received words count as recoverable evidence of a message; simply repeating uncoded transmission at rate one does not obtain the reliability promised at rates below

C

 Read the full article

Bit-position information in a binary channel Created 2026-10-25 Updated 2026-10-31

 View more

Suppose a fair input bit

X

is independent of a publicly known channel-position label

J

. At position

j

, let the channel be a binary symmetric channel with error probability

p_{j}

. Forgetting

J

gives a binary symmetric channel with error

\overline{p} = E p_{J}

. Therefore

I (X; Y ∣ J) = 1 - E h_{2} (p_{J}), I (X; Y) = 1 - h_{2} (E p_{J}) .

(1)

The chain rule for mutual information and

I (X; J) = 0

show that their difference is the nonnegative conditional mutual information

I (X; J ∣ Y)

. Equivalently, the inequality follows from concavity of binary entropy. For

p_{0} = 1/5, p_{1} = 0

with equal position weights, the known-position value is

0.639036

bits and the pooled value is

0.531004

bits. These quantities answer different statistical questions.

 Read the full article

Channel capacity Created 2026-09-24 Updated 2026-10-14

 View more

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities

W (y ∣ x)

, and no input-cost constraint, it is

C = max_{P_{X}} I (X; Y)

(1)

in bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of

M

possible messages by a word of length

n

, giving a rate

lo g_{2} M / n

bits per use. Take the message label from the uniform distribution on a finite set of those

M

choices when measuring average decoding-error probability. For every fixed rate

R < C

, there are sequences of such block codes whose decoding-error probability tends to zero as

n

grows; a rate above

C

cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below

C

works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability

p = 0.1

, the binary symmetric channel capacity is approximately

0.53100441

bits per use. Thus a binary code rate

R = 1/2

lies below the limit, while

R = 3/4

lies above it. At

R = 1/2

, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

 Read the full article

Completely noisy binary symmetric channel Created 2026-09-24 Updated 2026-09-24

 View more

At crossover probability

p = 1/2

, the two rows of the transition matrix of a binary symmetric channel coincide. Its output is then independent of its input and its capacity is zero.

 Read the full article

Correlated binary variables 2026-10-18

 View more

Let

A

be a fair bit, let

N

be an independent Bernoulli random variable with

P (N = 1) = p

, and set

B = A \oplus N

, where

\oplus

is exclusive or. Thus

N = 1

flips the first bit. This constructs a binary symmetric channel with a fair input, for

0 \leq p \leq 1

. The joint probability mass function is

A = 0 A = 1 P (B = b) B = 0 (1 - p) /2 p /2 1/2 B = 1 p /2 (1 - p) /2 1/2 P (A = a) 1/2 1/2 1

(1)

The column sums show that

B

is also a fair bit, whatever

p

is. Both marginal distributions therefore have information entropy one bit. Given

A

, only the flip decision remains unknown, giving conditional entropy

H (B ∣ A) = h_{2} (p)

, where

h_{2} (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)

(2)

is the binary entropy, with

h_{2} (0) = h_{2} (1) = 0

. The chain rule for information entropy and the definition of mutual information now give

H (A, B) = 1 + h_{2} (p), I (A; B) = 1 - h_{2} (p) .

(3)

Take

p = 1/10

. The four joint probabilities, in row order, are

(0.45, 0.05, 0.05, 0.45)

. Directly from the definition of joint entropy,

H (A, B) = - 2 (0.45) lo g_{2} (0.45) - 2 (0.05) lo g_{2} (0.05) \approx 1.468995594 bits .

(4)

Conditioning on either value of

A

gives probabilities

0.9

and

0.1

for the two values of

B

, hence

H (B ∣ A) = h_{2} (0.1) \approx 0.468995594 bits, I (A; B) \approx 0.531004406 bits .

(5)

Adding

H (A) + H (B) = 2

would overcount by exactly

I (A; B)

. These are average uncertainties under the stipulated probability distribution; the four possible pairs are still represented by four distinct outcomes.

Figure 1.
A correlated binary pair contains one bit plus the remaining flip uncertainty
. Original exact-model joint probability mass function for $p = 0.1$ . The bars compare the sum of marginal information entropies with the joint entropy from the chain rule for information entropy. The hatched portion is the mutual information counted twice by the marginal sum. Values are calculated, not empirical frequencies. **Details**.

There is another way to see the decomposition:

(A, B) \mapsto (A, A \oplus B) = (A, N)

is a bijection. It merely relabels the four outcomes, so it preserves joint entropy. The independence of

A

and

N

then gives

H (A, B) = H (A, N) = H (A) + H (N) = 1 + h_{2} (p)

. Describing the initial bit and the flip decision separates shared uncertainty from new uncertainty.

p = 0

, the bits are identical:

B = A

, so

H (B ∣ A) = 0

and

I (A; B) = 1

. At

p = 1

, they are complementary:

B = 1 - A

, with exactly the same conditional entropy and mutual information. In either case, observing one determines the other. At

p = 1/2

, all four joint probabilities are

1/4

; the bits are independent,

H (A, B) = 2

, and

I (A; B) = 0

. Perfect disagreement is therefore just as informative as perfect agreement.

Figure 2.
Identical and complementary bits both reveal one full bit of information
. Original calculated curves for the constructed pair $B = A \oplus N$ : joint entropy $1 + h_{2} (p)$ , conditional entropy $h_{2} (p)$ , and mutual information $1 - h_{2} (p)$ , all in bits. The horizontal line marks the one-bit information entropy of either marginal distribution. Reflection about $p = 1/2$ exchanges likely agreement with likely disagreement while preserving these quantities. **Details**.

For

p > 1/2

, guessing

A = 1 - B

succeeds with probability

p

, better than guessing

A = B

. Changing

B

1 - B

replaces

p

1 - p

and preserves mutual information, since the relabeling is invertible. What matters is how well the observation distinguishes the input, rather than how often its symbol matches the input. The same symmetry makes the binary entropy curve peak at independence, while the mutual information curve reaches its minimum there.

 Read the full article

Data processing inequality 2026-10-14

 View more

For finite discrete random variables, suppose

X \to Y \to Z

is a Markov chain: the final channel uses only

Y

, so

X

and

Z

have conditional independence given

Y

. In terms of the joint probability mass function,

p (x, y, z) = p_{X} (x) p (y ∣ x) p (z ∣ y),

(1)

and hence

I (X; Z ∣ Y) = 0

. Then the two data processing inequalities are

I (X; Z) \leq I (X; Y), I (X; Z) \leq I (Y; Z) .

(2)

All mutual informations here use base-two logarithms. Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.^[ref]

For a concrete cascade, take a fair bit

X

and Bernoulli random variables

N_{q}, N_{r}

with probabilities

q = 0.1

r = 0.2

of being one. Assume

X, N_{q}, N_{r}

are jointly independent random variables, and pass through two binary symmetric channels:

Y = X \oplus N_{q}, Z = Y \oplus N_{r} .

(3)

The second noise is independent of both

X

and

Y

, so this is a Markov chain. Both

Y

and

Z

are fair bits. The net exclusive or error is one exactly when one noise flips the bit and the other does not:

s = P (N_{q} \oplus N_{r} = 1) = q (1 - r) + (1 - q) r = q + r - 2 q r = 0.26.

(4)

Using the binary entropy

h_{2} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)

, the three mutual informations are fully determined:

I (X; Y) I (Y; Z) I (X; Z) = 1 - h_{2} (0.1) \approx 1 - 0.4689955936 \approx 0.5310044064, = 1 - h_{2} (0.2) \approx 1 - 0.7219280949 \approx 0.2780719051, = 1 - h_{2} (0.26) \approx 1 - 0.8267463725 \approx 0.1732536275.

(5)

All numbers are in bits. The two losses are

I (X; Y ∣ Z) \approx 0.3577507789

and

I (Y; Z ∣ X) \approx 0.1048182776

. Thus the cascade retains less information about the original source than either individual channel shares between its own input and output.

Figure 1.
Two noisy binary channels compose to a noisier channel and obey both data processing bounds
. **Details**.

With

q = 0.1

fixed and

0 \leq r \leq 1/2

, the effective error is

s = 0.1 + 0.8 r

. At

r = 0

Z = Y

and

I (X; Z) = I (X; Y)

; at

r = 1/2

Z

is independent of the previous variables and

I (X; Z) = I (Y; Z) = 0

. The diagram plots these endpoints and the computed

r = 0.2

example.

The data processing inequality is useful for testing what a proposed decoder or data summary could possibly reveal: if its only input is

Y

, even randomized processing cannot provide more mutual information about

X

than

Y

already contains. The Markov chain hypothesis matters. In the exclusive or example from conditional mutual information, allowing a processor to use both

Y

and

Z

reveals

X

exactly; that processor has additional input, so the conclusion for processing

Y

alone does not apply.

The chain rule for mutual information proves both inequalities and identifies their exact gaps. First expand the information about

X

in the two observation orders:

I (X; Y, Z) = I (X; Y) + 0 I (X; Z ∣ Y) = I (X; Z) + I (X; Y ∣ Z) .

(6)

Therefore

I (X; Y) - I (X; Z) = I (X; Y ∣ Z) \geq 0

. Next use

Z

as the variable being learned:

I (Z; X, Y) = I (Z; Y) + 0 I (Z; X ∣ Y) = I (Z; X) + I (Z; Y ∣ X) .

(7)

Symmetry of mutual information gives

I (Y; Z) - I (X; Z) = I (Y; Z ∣ X) \geq 0

. Both signs follow from the nonnegativity of conditional mutual information; the first gap also gives equality in data processing inequality.

 Read the full article

Discrete memoryless channel Created 2026-09-24 Updated 2026-10-14

 View more

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities

W (y ∣ x)

. For each input

x

, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word

x^{n} = (x_{1}, \dots, x_{n})

sent without feedback, the output law is

W^{n} (y^{n} ∣ x^{n}) = \prod_{j = 1}^{n} W (y_{j} ∣ x_{j}) .

(1)

This is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

 Read the full article

Flips versus erasures in a binary channel 2026-10-14

 View more

A binary erasure channel marks its failed transmissions with a special output symbol, whereas a binary symmetric channel changes a bit without announcing whether it changed. At the same nominal failure probability

p = 0.1

, the two communication channels therefore leave different uncertainty. With a fair input, an unerased output determines the input exactly, while the erasure flag leaves one bit of conditional entropy. Thus

H (X ∣ Y) = p

and

I (X; Y) = 1 - p = 0.9

for the binary erasure channel. This is the binary case of capacity of a finite-alphabet erasure channel.

For the binary symmetric channel at

p = 0.1

, neither possible received symbol rules out either input, and

H (X ∣ Y) = h_{2} (0.1) \approx 0.46899559

. Its channel capacity is only

1 - h_{2} (0.1) \approx 0.53100441

. A receiver benefits from knowing where information was lost, even when the fraction of affected transmissions is the same.

Figure 1.
Announced erasures preserve more information than hidden bit flips at the same low failure probability
. Solid arrows carry probability $0.9$ and dashed arrows carry probability $0.1$ in the two illustrated laws of transition probabilities. The erasure flag is distinct from both bits. The lower plot compares channel capacity for $0 \leq p \leq 1/2$ , using $1 - p$ for the binary erasure channel and $1 - h_{2} (p)$ for the binary symmetric channel. **Details**.

This comparison concerns the specified transition probabilities, rather than a general ordering of every error mechanism. In particular, at

p = 1

, an erasure flag conveys no input information, while deterministic inversion still conveys a full bit. Reporting only an error percentage loses the distinction between hidden corruption, announced loss, and a predictable reversible transformation.

 Read the full article

Input distribution optimization for a binary symmetric channel 2026-10-14

 View more

Let

q = Pr (X = 1)

for the input bit of a binary symmetric channel with crossover probability

p

. The law of total probability gives

Pr (Y = 1) = (1 - q) p + q (1 - p) = p + (1 - 2 p) q .

(1)

Consequently its mutual information is

I (X; Y) = h_{2} (p + (1 - 2 p) q) - h_{2} (p) .

(2)

Here

p

specifies the noise and

q

specifies the input bias; they are different choices. At

p = 0.1

and

q = 0.2

, the output has

Pr (Y = 1) = 0.26

, giving

H (Y) \approx 0.82674637

and

I (X; Y) \approx 0.35775078

bits. With the same noise and the fair input

q = 1/2

, the output becomes fair and

I (X; Y) \approx 0.53100441

bits, attaining binary symmetric channel capacity.

Figure 1.
A fair input maximizes retained information through a binary symmetric channel
. The left panel holds the crossover probability fixed and varies $q = Pr (X = 1)$ . The right panel shows the output probability distributions for $p = 0.1$ with input biases $q = 0.2$ and $q = 0.5$ . More output Shannon entropy helps here because the conditional noise information entropy stays fixed. **Details**.

For

p \neq = 1/2

, binary entropy reaches one only at output mass

1/2

, and the equation

p + (1 - 2 p) q = 1/2

forces

q = 1/2

. Thus the maximizing input is unique in those cases. For

p = 1/2

, every input produces the same fair output and zero mutual information, so every input bias is optimal and none transmits information. A fixed input

q = 0

q = 1

also carries zero mutual information for every

p

: noise can make its output unpredictable without creating an unknown message to recover.

 Read the full article

Mutual information Created 2026-09-24 Updated 2026-10-14

 View more

For finite discrete random variables, mutual information is the reduction of information entropy provided by observing the other variable:

I (X; Y) = H (Y) - H (Y ∣ X) = H (X) + H (Y) - H (X, Y) .

(1)

The last expression makes the symmetry

I (X; Y) = I (Y; X)

visible. It is nonnegative and is zero exactly when

X

and

Y

are independent random variables. One way to see both facts is

I (X; Y) = \sum_{x, y : p (x, y) > 0} p (x, y) lo g_{2} \frac{p ( x , y )}{p _{X} ( x ) p _{Y} ( y )} = D (p_{X, Y} ∥ p_{X} p_{Y}),

(2)

where

D

is the Kullback-Leibler divergence with base-two logarithms. The Gibbs inequality gives nonnegativity; equality means that the joint probability distribution factors. The statement extends to more general distributions via relative entropy, but differences of infinite information entropies must not be used as if they were finite numbers.

A binary symmetric channel gives a useful example. Let

X

be a fair bit, let

N

be an independent Bernoulli random variable with error probability

q

, and set

Y = X \oplus N

, where

\oplus

is exclusive or. The output is also a fair bit, but knowing the input leaves just the error uncertainty:

H (Y) = 1, H (Y ∣ X) = h_{2} (q), I (X; Y) = 1 - h_{2} (q) .

(3)

Here

h_{2}

is binary entropy. At

q = 0.1

h_{2} (q) \approx 0.469

, so the output carries about

0.531

bits of mutual information about the input per use. This is an average uncertainty reduction, not a claim that each observed symbol can be divided into fractional physical bits.

Figure 1.
Binary entropy and retained information distinguish noisy transmission from predictable bit inversion
. **Details**.

q = 1/2

, every output is equally likely for either input, so

I (X; Y) = 0

. At

q = 1

, the output is always the inverted input: knowing this rule lets the receiver recover the input exactly, so

I (X; Y) = 1

again. A high raw error rate need not mean low mutual information when the errors are predictable. For this particular channel the fair input is optimal, giving the binary symmetric channel capacity

1 - h_{2} (q)

Mutual information detects dependence that ordinary correlation can miss. Let

X

be uniform on

{- 1, 0, 1}

and

Y = X^{2}

. Symmetry gives

E [X] = E [X Y] = 0

, hence zero covariance and zero correlation, while

Y

is completely determined by

X

. Thus

I (X; Y) = H (Y) = h_{2} (1/3) > 0

. This distinction is useful whenever a relationship is nonlinear: knowing one variable can reveal another without a linear trend.

 Read the full article

Past exam of the communication Theory course of the University of Oxford / 2007 / 4 / a / Solution 2026-10-31

 View more

With equally likely codewords, the prior factor in the ideal-observer criterion is constant, so it agrees with maximum likelihood. On the binary symmetric channel,

p (y ∣ x) = p^{d_{H} (x, y)} (1 - p)^{n - d_{H} (x, y)} .

(1)

For

0 < p < 1/2

this is strictly decreasing in Hamming distance, so the likelihood maximizers are precisely the nearest codewords. With the same tie convention all three decoders therefore agree. At

p = 0

every possible received word equals its transmitted codeword, and the rules agree on all positive-probability outputs; outputs having zero probability need no posterior assignment.

 Read the full article

Past exam of the communication Theory course of the University of Oxford / 2008 / 2 / c / ii / Solution 2026-10-31

 View more

Let

X

be the original input,

U

the output of the first channel, and

Y

the final output. The independent erasure flag is observable from

Y

. The mutual information chain rule, conditioning on that flag, gives

I (X; Y) = (1 - ϵ) I (X; U) + ϵ \cdot 0.

(1)

The same uniform input maximizes

I (X; U)

as in the binary symmetric channel. Thus

C = (1 - ϵ) (1 - h (p)) .

(2)

This scaling works because the erasure event is independent of both the input and the first channel noise.

 Read the full article

Past exam of the communication Theory course of the University of Oxford / 2008 / 2 / c / i / Solution 2026-10-31

 View more

The capacity of a discrete memoryless channel is

C = max_{P_{X}} I (X; Y)

, in bits per channel use. For the binary symmetric channel with crossover probability

p

H (Y ∣ X) = h (p)

and

H (Y) \leq 1

. A uniform input makes the output uniform, attaining

C_{M} = 1 - h (p) .

(1)

For the binary erasure channel, let

E

be its erasure indicator. This flag is visible in the output and independent of the input. If there is no erasure, the output reveals the input; otherwise it reveals nothing. Consequently

I (X; Y) = (1 - ϵ) H (X), C_{N} = 1 - ϵ,

(2)

again attained by a uniform input. These formulas include crossover probabilities zero and one, and complete erasure.

 Read the full article

Past exam of the information theory course of the University of Oxford / 2021 / 3 / e / Solution 2026-10-25

 View more

There are two possible messages and three channel uses, giving

R = \frac{lo g _{2} 2}{3} = \frac{1}{3} bit per use .

(1)

Conditional on either transmitted message, a decoding error occurs exactly when at least two of the three bits are flipped. The discrete memoryless channel makes these flips independent, each with probability

ε = 1/10

. Their count therefore has a binomial distribution with parameters

3, ε

. Majority-vote decoding of a repetition code gives

P (error ∣ W = a) = (2 3) ε^{2} (1 - ε) + ε^{3} = 3 (\frac{1}{10})^{2} \frac{9}{10} + (\frac{1}{10})^{3} = \frac{7}{250} = 0.028.

(2)

Interchanging the two bit values leaves the binary symmetric channel and majority decision unchanged, so $P (error ∣ W = b) = 7/250$ as well. Both the maximum conditional error and the average error, for any message prior, are therefore

0.028

. The probability of correct decoding for each message is

243/250 = 0.972

. These are finite-block error probabilities; a channel-capacity statement alone would not determine them.

 Read the full article

Past exam of the laser science and quantum information processing course of the University of Oxford / 2006 / 7 / 3 / Solution 2026-10-25

 View more

The actual resource is a two-component Bell resource in dense coding. Applying the same local encoder

X^{v} Z^{u}

∣ χ ⟩ = \frac{2∣ Φ ^{+} ⟩ + ∣ Φ ^{-} ⟩}{5}

(1)

gives a superposition of the intended Bell state with amplitude magnitude

2/ 5

and its phase-label partner with amplitude magnitude

1/ 5

. A Bell-basis measurement therefore reports the wrong Bell state with probability $1/5$ , independently of

uv

. With our labeling, only the phase bit

u

flips:

(u, v) = (u \oplus N, v), P (N = 1) = \frac{1}{5} .

(2)

The first bit of each pair passes through a binary symmetric channel with error

1/5

; the second bit is correct. A uniformly chosen bit from the full stream consequently has

P_{bit error} = \frac{1}{2} \cdot \frac{1}{5} = \frac{1}{10} .

(3)

This bit error probability depends on the Bell labeling. The Bell-label Hamming distance and bit errors rule multiplies the wrong-symbol probability by the number of bit positions changed. For example, relabel

Φ^{+}, Φ^{-}, Ψ^{+}, Ψ^{-}

00, 11, 01, 10

. Both wrong-state partner pairs then differ in two bits, giving bit error probability $1/5$ instead of

1/10

. The physical wrong-Bell-state probability remains

1/5

For the entropy-matched independent source in part 2, the transmitted bit stream is fair, and consecutive two-bit labels are uniform. Write the binary entropy as

h_{2} (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)

. If a bit position is chosen uniformly and its phase/parity position is forgotten, the pooled corresponding-bit pair is a binary symmetric channel with error

1/10

. Its mutual information is

I (B; B) = 1 - h_{2} (1/10) ≃ 0.531004 bits .

(4)

The bit-position information in a binary channel distinguishes this pooled quantity from the information in the decoded blocks. Alice and Bob know which bit is first in each Bell label. Conditioned on that position

J

, the first bit gives

1 - h_{2} (1/5)

bits and the second gives one bit. Thus

I (B; B ∣ J) = 1 - \frac{1}{2} h_{2} (1/5) ≃ 0.639036 bits per bit .

(5)

Equivalently, the joint mutual information between the two-bit input and output labels is $2 - h_{2} (1/5) ≃ 1.278072$ bits per transmitted Bell label for the prescribed Bell measurement. Pooling without the position loses usable side information; it is not interchangeable with this block rate. The stated fair-input values use the optimal source distribution above; biased source bits require their actual joint distribution.

Figure 1.
Mutual information for the two Bell-label positions and for known or forgotten bit positions
. Original calculations for independent fair input bits, Bell-readout error $1/5$ , and the labeling in the solution. The first bit may flip while the second is noiseless. Knowing which position a bit occupies retains more information than pooling the two channels and discarding that label. **Details**.

 Read the full article

Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 2 / B4 / a / Solution 2026-10-20

 View more

Write

m_{i} \in {0, 1}

for the true DNA methylation status and

o_{i}

for its observation. The observation likelihood function is a binary symmetric channel, so

lo g p (o ∣ m) = \sum_{i = 0}^{99} {lo g (0.8), lo g (0.2), o_{i} = m_{i}, o_{i} \neq = m_{i} .

(1)

For the loop suggested in the practical, set

p_{i} = (0.1, 0.5, 0.9)_{m_{i - 1} + m_{i + 1}}

and add

lo g p_{i}

when

m_{i} = 1

, or

lo g (1 - p_{i})

otherwise. The following independent implementation combines these terms without multiplying many small numbers:

import numpy as np

def methylation_score(pattern, observed):
    """Conditional-product score used by the practical's natural loop filling."""
    pattern=np.asarray(pattern,dtype=int);observed=np.asarray(observed,dtype=int)
    if pattern[0]!=1 or pattern[-1]!=1:return -np.inf
    neighbour_sum=pattern[:-2]+pattern[2:]
    p=np.array([.1,.5,.9])[neighbour_sum]
    prior_terms=np.where(pattern[1:-1]==1,p,1-p)
    observation_terms=np.where(pattern==observed,.8,.2)
    return float(np.log(prior_terms).sum()+np.log(observation_terms).sum())

log_likelihood = methylation_score
print(f"{log_likelihood(obs, obs):.2f}")

The conditional-product log score at the observed pattern is $- 102.14$ . The endpoint observations are included once each, while the endpoint statuses are fixed rather than assigned an additional prior probability.

There is a modeling qualification: multiplying the specified neighbour conditional probabilities gives a pseudolikelihood, not generally the joint probability distribution having those conditional probabilities. Thus the function above defines the practical's conditional-product target; the pure observation log-likelihood at

m = o

would instead be

100 lo g (0.8) = - 22.3144

If the neighbour probabilities are intended literally as full conditionals of a Markov random field, a coherent alternative has edge weights

T_{aa} = 3/4

and

T_{ab} = 1/4

for

a \neq = b

, with both endpoints fixed. Given two equal neighbours, the matching centre has conditional odds

(3/4)^{2} : (1/4)^{2} = 9 : 1

; mixed neighbours give equal weights. Consequently its unnormalized posterior probability has log score

ℓ_{J} (m; o) = \sum_{i = 0}^{98} lo g T_{m_{i} m_{i + 1}} + lo g p (o ∣ m) .

(2)

For this alternative,

ℓ_{J} (o; o) = - 94.7394

before the constant associated with conditioning the endpoints. It can be implemented as follows, but its numerical results must not be mixed with the conditional-product results in the remaining parts:

def joint_methylation_score(pattern,observed):
    """Coherent nearest-neighbour model with the specified full conditionals."""
    pattern=np.asarray(pattern,dtype=int);observed=np.asarray(observed,dtype=int)
    if pattern[0]!=1 or pattern[-1]!=1:return -np.inf
    edges=np.where(pattern[1:]==pattern[:-1],.75,.25)
    emissions=np.where(pattern==observed,.8,.2)
    return float(np.log(edges).sum()+np.log(emissions).sum())

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 4 / 4J / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Reliable transmission at rate

r

means that there is a sequence of binary block codes of lengths

n

, message counts

M_{n}

with

lim inf n^{- 1} lo g_{2} M_{n} \geq r

, and decoding error probabilities tending to zero. The Shannon second coding theorem identifies the supremum of reliable rates with the channel capacity.

For a binary symmetric channel, the conditional entropy of the output given any input bit is

h_{2} (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)

. The output entropy is at most one bit and attains one for uniform input, so the maximum mutual information is

C = 1 - h_{2} (p) .

(1)

All rates strictly below

C

are achievable, and rates above

C

are not reliable; this states the supremum without claiming achievability of every boundary rate under every convention.

For very small

p

, the capacity is close to one, with

h_{2} (p) = p lo g_{2} (1/ p) + p / lo g 2 + O (p^{2})

. At

p = 1/2

, the output is independent of the input and capacity is zero. For

p > 1/2

, flipping every received bit converts the channel to crossover probability

1 - p < 1/2

; its capacity is unchanged because

h_{2} (p) = h_{2} (1 - p)

. At

p = 1

the deterministic bit flip is perfectly reversible.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 30 / 3 / b / Solution Created 2026-10-03 Updated 2026-10-14

 View more

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate

R < C

with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above

C

. The channel capacity, in bits per use, is

C = P_{X} sup I (X; Y) .

(1)

For a finite discrete memoryless channel with transition probabilities

W (y ∣ x)

, the supremum is a maximum and its mutual information is

I (X; Y) = \sum_{x, y} P_{X} (x) W (y ∣ x) lo g_{2} \frac{W ( y ∣ x )}{\sum _{x^{'}} P _{X} ( x ^{'} ) W ( y ∣ x ^{'} )} .

(2)

For a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write