受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

東京大学2009年度後期の総合科目Ⅱの第一問のBの解説
さあて、バフ。


東京大学2009年度理系後期、第一問のBの解説。

[問題]
コンピューターで扱うデータは、2つの数字0,1からなる列として表されることが多い。数字0,1からなる長さnの列を、送信者Aから受信者Bに転送することを考える。情報を転送する際にノイズが入るために,0が1に,1が0に,それぞれ確率pで入れ替わって伝わる。ここで,pは0≦p<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に再度同じ情報、つまりn個の数字の列とパリティビットを送ってもらう。この手続きを、受信者Bが、正しくデータを受信できたと判断するまで繰り返す。ただし、パリティビットも、他のn個の数字と同様に確率pで入れ替わって伝わる。

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

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



[解答と解説]
コンピューターの扱うデータが、ノイズで…とかわけわからんわこれって白目むいて鼻水たらしながら読み流してください。

090603_m1.jpg

P(n+1)をP(n)で表せってことは、典型的な漸化式を使って解く確率の問題です。
nとn+1の関係を見たらええってやつや。

まず長さnの列が奇数個誤るのは1-P(n)です。
この余事象を考えとくんが一つのコツやねんな。


それで長さnの列の一番右にでも数字が一つくわえてn+1の列を考えます。
すると長さn+1の列が偶数個誤るときは

長さnの列の部分が偶数個誤って、一番右側の数字がそのままの時



長さnの列の部分が奇数個誤って、一番右側の数字が誤るとき

の二つです。

これらの確率を足せばP(n+1)になるわけやな。

まず長さnの列の部分が偶数個誤るのはP(n)、一番右側の数字がそのままのは(1-p)で
P(n)(1-p)

長さnの列の部分が奇数個誤るのは1-P(n)、一番右側の数字が誤るのはpで
(1-P(n))p

だから

P(n+1)=P(n)(1-p)+(1-P(n))p
=(1-2p)P(n)+p


漸化式を使って解く確率の問題としてはかなり典型的なものなので、それなりに問題演習してきてたら難しくはないと思います。

あえて言うならデータとかノイズとか関係ないから、あほみたいな顔して読み流すがのがコツです。

(B-2)
090603_m2.jpg

もうこれは漸化式を解くだけや。
これが解けない人は、たぶん小さい時にお父さんに肩車とかしてもらったことないんちゃうかな。
それが今きてるねん。


(B-3)
これもパリティビットうへ~って白目むきなら、半笑いで読み流しておいてください。

090603_m3.jpg

再送を要求されるのは長さnの列に1が奇数個あるときは、

パリティビットが1で、偶数個変わって、パリティビットが0に

パリティビットが1で、奇数個変わって、パリティビットが1のまま

このときは

P(n)p+(1-P(n))(1-p)
=1-P(n+1)=1/2-(1-2p)^(n+1)/2

長さnの列に1が偶数個あるときは、

パリティビットが0で、偶数個変わって、パリティビットが1に

パリティビットが0で、奇数個変わって、パリティビットが0のまま

このときも
P(n)p+(1-P(n))(1-p)
=1-P(n+1)=1/2-(1-2p)^(n+1)/2

だから
1/2-(1-2p)^(n+1)/2
やねんけど、1-P(n+1)は長さn+1の列が奇数個誤るときやから、よう考えたら再送されるのは長さn+1の列が奇数個誤るだけ良かったことに気づいて血吐いて倒れます。

でも解けたのに、そこで倒れるのはもったいないと思います。


(B-4)

090603_m4.jpg

q=1/2-(1-2p)^(n+1)/2と置いておいて、

k回再送して終了する確率は

q^(k-1)(1-q)
だから求める期待値は、

(n+1)Σ(k=1~∞)kq^(k-1)(1-q)

この(n+1)は忘れといてくれ。
単に長さn+1の列を送るから、再送の回数にn+1をかけてるだけやで。

でも解釈によっては、Σ(k=1~∞)kq^(k-1)(1-q)なんかなあって思ってまうけどな。


この計算は等差数列×等比数列の形やから、定石に従った解き方があるけど別にこのままでもバラすと出来るようになっていて

(n+1)Σ(k=1~∞)kq^(k-1)(1-q)
=(n+1)lim(m→∞)(1-q+2q-2q^2+3q^2-3q^3+…-(m-1)q^(m-1)+mq^(m-1)-mq^m)
=(n+1)lim(m→∞)(1+q+q^2++q^3+…+q^(m-1)-mq^m)
=(n+1)lim(m→∞)((1-q^m)/(1-q)-mq^m)

0≦q<1だから

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


まあ文章の複雑さに比べて数学的には簡単やと言う感じやな。
データとかコンピューターとかパリティビットとか全然問題解くのと関係ないやろこれ。
だから文章が長くて何か凄い難しいこと書いてるような感じがするけど、文章の要点を的確に捉えてちゃんと普通に処理すれば簡単やったりするから大丈夫大丈夫。

高校数学の入試問題などの解説

東京大学の入試の数学の過去問の解説




テーマ:大学受験 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/303-185d4b0c
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析