2009年(平成21年)東京大学後期-総合科目ＩＩ[1]B - [別館]球面倶楽部零八式markIISR

[1] 多くのデータを扱うことは，さまざまな分野で必要になる．大量のデータを整理する際に，ある基準によってデータの間に序列をつけることが有用である．また，データを転送するときには，ノイズによる転送の誤りの確率を小さくするような工夫が必要である．

B
コンピュータで扱うデータは，2つの数字 0，1 からなる列として表されることが多い．数字 0，1 からなる長さ $n$ の列を，送信者 A から受信者 B に転送することを考える．情報を転送する際にノイズが入るために，0が1に，1が0に，それぞれ確率 $p$ で入れ替わって伝わる．ここで， $p$ は $0\leqq p\lt 1$ を満たす定数である．

例えば、長さ8の数字の列 01001100 が
11001100
と伝わる確率は，1番目の数字のみが入れ替わっているので， $p(1-p)^7$ である．また 01001100が
00011100
と伝わる確率は，2番目と4番目の数字が入れ替わっているので， $p^2(1-p)^6$ である．

(B-1) 数字0，1からなる長さ $n$ の列を1回送るとき，誤って伝わる数字の個数が偶数個である確率を $P(n)$ とおく．ただし，誤りがない場合は0個の誤りがあったと考える． $P(n+1)$ を $p$ と $P(n)$ を用いて表せ．

(B-2) $P(n)$ を $p$ と $n$ を用いて表せ．

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

(B-3) 送信者 A が， $n$ 個の数字からなるデータとパリティビットを合わせて $n+1$ 個の数字からなる列を1回目に送るとき，受信者Bが A に再送を要求する確率を $p$ と $n$ を用いて表せ．

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

2021.02.11記
誤り訂正符号．

[解答]

(B-1) 最初の $n-1$ で偶数個か奇数個で場合分けして，
$P(n+1)=(1-p)P(n)+p\{1-P(n)\}$ $=(1-2p)P(n)+p$

(B-2) (B-1)と $P(1)=1-p$ により $P(n)-\dfrac{1}{2}$ $=(1-2p)\Bigl\{P(n-1)-\dfrac{1}{2}\Bigr\}$ $=\dfrac{(1-2p)^{n} }{2}$ となり， $P(n)=\dfrac{1+(1-2p)^{n} }{2}$ となる．

(B-3) データとパリティビットが食い違うのは，奇数個が入れ替わった場合だけであり，そのときに再送を要求するので，求める確率は $1-P(n+1)=\dfrac{1-(1-2p)^{n+1} }{2}$ となる．

(B-4) 成功確率が $P(n+1)$ のときの成功回数の期待値が $\dfrac{1}{P(n+1)}$ であり，1回あたり $n+1$ 個の数字を送信するので、求める送信文字数の期待値は $\dfrac{n+1}{P(n+1)}=\dfrac{2(n+1)}{1+(1-2p)^{n+1}}$ となる．