データ送受信の誤り訂正の仕組み（東大入試より）

（東大後期・総合科目Ⅱ2009）

　コンピュータで扱うデータは、２つの数字 0,1 からなる列として表されることが多い。数字 0,1 からなる長さ n の列を、送信者Ａから受信者Ｂに転送することを考える。情報を転送する際にノイズが入るために、0 が 1 に、1 が 0 に、それぞれ確率 p で入れ替わって伝わる。ここで、p は 0 ≦ p＜1 を満たす定数である。
　例えば、長さ 8 の数字の列 01001100 が
　　　11001100
と伝わる確率は、１番目の数字のみが入れ替わっているので、p(1－p)⁷ である。また、01001100 が
　　　00011100
と伝わる確率は、２番目と４番目の数字が入れ替わっているので、p²(1－p)⁶ である。

(1)　数字 0,1 からなる長さ n の文字列を１回送るとき、誤って伝わる個数が偶数個である確率を P(n) とおく。ただし、誤りがない場合は 0 個の誤りがあったと考えられる。P(n＋1) を p と P(n) を用いて表せ。

(2)　P(n) を p と n を用いて表せ。

　データが誤って伝わる可能性を小さくするために、データを表す 0,1 からなる n 個の数字の後に、データの中に 1 が奇数個あるときは 1 を、偶数個あるときは 0 を付け加えて、全部で n＋1 個の数字の列をＡからＢに送る。この末尾に付け加える数字をパリティビットとよぶ。受信者Ｂは、パリティビットが、受け取ったデータの n 個の数字の中の 1 の個数と合っていれば、情報が正しく送られたと判断してそのまま情報を受け取る。合っていなければ、情報が誤って送られたと判断して、Ａに再度同じ情報、つまり n 個の数字の列とパリティビットを送ってもらう。この手続きを、受信者Ｂが、正しくデータを受信できたと判断するまで繰り返す。ただし、パリティビットも、他の n 個の数字と同様に確率 p で入れ替わって伝わる。

(3)　送信者Ａが、n 個の数字からなるデータとパリティビットをあわせて n＋1 個の数字からなる列を１回目に送るとき、受信者ＢがＡに再送を要求する確率を p と n を用いて表せ。

(4)　Ｂがデータを正しく受信したと判断して通信が終了するまでに、Ａが送信する数字の個数の期待値を p と n を用いて表せ。

---

《解答》
(1)　P(n＋1)＝P(n)×(1－p)＋{1－P(n)}×p＝(1－2p)P(n)＋p
　　　　　　↓ 漸化式を解く
(2)　P(n)＝{ (1－2p)ⁿ＋1}／2
　　　　　　↓ 意味がわかればすぐ
(3)　1－P(n＋1)＝{1－(1－2p)^n＋1}／2
　　　　　　↓ 数Ⅲ範囲
(4)　k回目に通信が終了する確率は{1－P(n＋1)}^k－1×P(n＋1)
　　求める期待値はΣk(n＋1){1－P(n＋1)}^k－1×P(n＋1)
　　　　　　　　　＝　　・・・（中略）・・・
　　　　　　　　　＝2(n＋1)／{ (1－2p)^n＋1＋1}