Skip to content

Noisy yes or no message passed down a long chain

Question

A yes/no message is handed to person P1P_1, who passes it to P2P_2, who passes it to P3P_3, and so on along a chain P1,…,PnP_1,\dots,P_n. Each person, independently of everyone else, relays what they heard faithfully with probability pp and relays the opposite with probability 1−p1-p, where 0<p<10<p<1.

Let pnp_n be the probability that what PnP_n passes on matches the message P1P_1 originally received. Find lim⁡n→∞pn\lim_{n\to\infty}p_n, or answer −1-1 if the limit does not exist.

Short answer

12\tfrac12. Conditioning on whether PnP_n heard the right message gives pn=p pn−1+(1−p)(1−pn−1)p_n=p\,p_{n-1}+(1-p)(1-p_{n-1}), so pn−12=(2p−1)(pn−1−12)p_n-\tfrac12=(2p-1)\left(p_{n-1}-\tfrac12\right). Since ∣2p−1∣<1|2p-1|<1, the deviation from 12\tfrac12 shrinks geometrically to zero.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free