1．ある宝くじにおいて，X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} から選ばれた 4 つの数字が順番に券面に印刷されており，抽選時においては，X の番号がそれぞれ 1 つずつ書かれた 10 個のボールをランダムに 4 つ選び (同じ番号のボールは 1 つしかないので，同じ番号が複数選ばれることはない)， 1 等賞はすべての数字が (選ばれた順番も含めて) 一致するもの，2 等賞はすべての数字が (順番を考慮せずに) 一致するもの， 3 等賞は一致する数字がちょうど 1 つ (順番を考慮せずに) あるもの， とする．この宝くじにおいて 1 等賞から 3 等賞までの当選確率を計算せよ．

2．(a + b + c + d)¹⁰ を展開した場合の，a⁴bcd⁴ および a²bc³d⁴ の係数を計算せよ．

3．a + b + c + d + e = 10 を満たす非負の整数 (a, b, c, d, e) の組合せは何通りあるか．

1．解答

(i) 1 等賞の確率
宝くじの番号の全組合せは，₁₀P₄ = 10・9・8・7 = 5040 通りあり，1 等賞の可能性はそのうちの一つだけなので，1 / 5040 となる．
(ii) 2 等賞の確率
10 個のボールから，順番を無考慮で特定の 4 個を選び出す組合せは，₁₀C₄ = 10・9・8・7 / 4・3・2・1 = 210 通りあり，2 等賞の可能性はそのうちの一つだけなので， 1 / 210 となる．
(iii) 3 等賞の確率
選ばれなかった 6 個から 3 個を選び，選ばれた 4 個から 1 個を選ぶ組合せは，₆C₃ ・ ₄C₁ = 80 個あるので， 80 / 210 = 8 / 21 となる．

2．解答
(i) a⁴bcd⁴
多項定理より，10 ! / 4 ! ・ 1 ! ・ 1 ! ・ 4 ! = 10・9・8・7・6・5・4・3・2・1 / 4・3・2・1・1・1・4・3・2・1 = 6300
(ii) a²bc³d⁴
多項定理より，10 ! / 2 ! ・ 1 ! ・ 3 ! ・ 4 ! = 10・9・8・7・6・5・4・3・2・1 / 2・1・3・2・1・4・3・2・1 = 12600

3．解答
この問題は，「10 個の区別のできないボール (10) を，一つももらえない人がいてもかまわない (非負の整数 ; 0 以上) から，5 人 (a, b, c, d, e) に分配せよ」， という問題と等価である．
10 個のボールを，4 つの仕切りで区切れば良いので，全ての順列14 ! から，ボールの重複 10 ! と，仕切りの重複 4 ! を取り除けば良い．すなわち，整数の組合せは
14 ! / 10 ! ・ 4 ! = 1001
通りとなる．

高校生のころ，順列・組合せは特に苦手な分野だったので，未だにトラウマが… (^-^;)

いまさら学び直しです (笑) ちょっとはあの頃よりも成長できたかなぁ… もっとちゃんと勉強しておけばよかった… (> _ <;)

ちなみに，大学には書類と面接だけで入りました (笑) 10 月にはもう合格が決まっていたのですが，お金を払った後だったので，一応センター試験は受けました．ほぼ受けられるものは全部受けて，トータルで偏差値 50 ちょいぐらいでしたね．

でも，ちょっと自慢できるのは，化学で 90 点を取ったこと．先生が厳しかったんですよ :-)

もうほとんど忘れてしまいましたが… 恩師の K 先生，ごめんなさい (笑)

# もうあれから 4 年も経つのかぁ… いまとなっては全てが懐かしい．物理や数学をもっとちゃんとやっておけば良かったなぁ… いちおう III と C まではやっているのですが，田舎の名も無き高校のレベルでしたからねぇ… というか，あのころはまだ数学の面白さに気付いていなかった．

今回は，人生初の筆記試験による入試です．全然自信がない．まいったなぁ… (- o -;)

---

下の図に示すシャノン線図で表される情報源について次の問に答えよ．



1. この情報源がエルゴード情報源であるとき，各々の状態確率 p(S1) および p(S2) を状態遷移確率 p, q を使って示せ．

2. この情報源のエントロピーを p, q を使って表せ．

用語の簡単な確認

情報源には，(1) 記憶のない情報源 と (2) 記憶のある情報源 の 2 種類があります．

例
サイコロの目は，前の目の影響を全く受けないので (1)．
英語の文字列は，前のアルファベットによって，次にくるアルファベットの確率が変わって来るので，(2)．例えば，q の次には，ほぼ 100 % u がくる．(question, quantum など)


(2) を特に，マルコフ情報源と呼び，正確な定義は 「過去の有限個の記号の生起が次の記号の生起に影響する情報源」となります．

そして，過去の m 個の記号の影響を受ける情報源を m 重マルコフ情報源と呼び，特に直前の記号の影響のみを受ける場合 (m = 1) を単純マルコフ情報源と呼びます．

一口にマルコフ情報元と言っても，いろいろなパターンが考えられ，中にはあまり好ましくないような場合も考えられます．

例えば，一度特定の状態に入ると抜け出せなかったり (吸収的．それ以外の部分は，状態遷移図としては無意味になってしまう → 消散状態部分の発生)，初期状態に対する依存性が大き過ぎたり，状態遷移に周期性が見られたりするマルコフ情報源は，通常の情報源のモデルとして使用するにはあまり適しません．

そこで，エルゴード性 (ergodic property) という概念が重要になってきます．

エルゴード性とは，どの状態から出発しても，どの状態にも遷移する可能性があり，周期性を持たず，情報源の統計的性質をよく反映した状態遷移を行う，という性質のことです．

エルゴード性を持つマルコフ情報元のことを，エルゴード的マルコフ情報源，またはエルゴード情報源と呼びます．

シャノン線図とは，要は状態遷移図と同じことだと思います．

/*

たぶん，オートマトンや OS のプロセスなどの，一般的な状態遷移を表現する場合には状態遷移図と呼ばれ，情報理論関係で，特にシャノン (Claude Elwood Shannon ; 情報理論の始祖) の名前を強調したい時には，シャノン線図と呼ぶのではないでしょうか ? よくわかりませんが…

ちなみに，図以外にも，状態 Pi から Pj に遷移する場合を Pij とし，行列で状態遷移の確率を表す方法もあります．これを遷移確率行列と呼びます．

例えば，今回の問題の遷移確率行列 S は，

          P11 P12        p     1-p
S =   [ P21 P22 ］ = [ 1-q  q    ]

となります．(HTML では行列を上手く表現できません…)
*/

今回の問題は，最も基本的な 2 元記号のエルゴード的単純マルコフ情報源なので，全ての状態に遷移する可能性があります．

そして，各状態の発生する可能性を定常状態確率と呼び，当然のことながら，全状態の定常状態確率を足すと １ になります．

1. 解答

状態 S1 が発生する確率 p(S1) は，

(1) S1 から，再び S1 に遷移する確率
(2) S2 から，S1 に遷移する確率

の和である．すなわち，

(i) p(S1) = p(S1) × p + p(S2) × (1 - q)

となり，同様に p(S2) は，

(ii) p(S2) = p(S2) × q + p(S1) × (1 - p)

となる．

p(S1) + p(S2) = 1 なので， p(S1) = 1 - p(S2) となり，これを (ii) に代入すると ((i) と (ii) は等価なので，どちらに代入しても構わない)

      p(S2) = p(S2) * q + (1 - p(S2) * (1 - p))
→   p(S2) = p(S2) * q + 1 - p -p(S2) + p(S2) * p
→   p(S2) * 2  - p(S2) *q  - p(S2) * p = 1 - p
→   p(S2)  * (2 - q + p) = 1 - p
→   p(S2) = (1 - p) / (2 - q + p)

/* 確認のため，(i) にも代入してみる

      1 - p(S2) = (1 - p(S2)) * p + p(S2) × (1 - q)
→   1 - p(S2) = p - p(S2) * p + p(S2) - p(S2) * q
→   p(S2) * 2 - p(S2) * p + p(S2) * q = 1 - p
→   p(S2) * (2 - q + p) = 1 - p
→   p(S2) = (1 - p) / (2 - q + p)

*/
ゆえに，各状態確率は，
p(S1) = 1 - (1 - p) / (2 - q + p) = (1 - q + 2p) / (2 - q + p)
p(S2) = (1 - p) / (2 - q + p)
となる．

情報量とは，ある情報がどれだけ不確実性を減らしたかということを数値化したもので，起こり難い事象が起こったときには大きくなり，逆に 100 % 起こる事象が起こった場合には 0 です．

厳密には，発生確立 p(a) の事象 a が起こったとき，これを知ることにより得られる情報量 I(a) は
I(a) = log (1 /p(a)) = - log p(a)
と，p(a) の逆数の対数を用いて表されます．

# 確率の逆数を取っていることから，a が起こり難ければ起こり難い程，I(a) は大きくなるということがわかります．対数を用いているのは，単純に 1 / p(a) としてしまうと，値が大きくなり過ぎる場合があるし，乗法の計算が加法ですむようになるなどいろいろと便利なためです．

対数の底には様々な値が考えられますが，情報理論では，一般的に2 を底とした bit という単位を用います．

# 他には tat (底が 3) nat (底が e) hartley (底が 10) などがあるそうです

エントロピーとは，情報量の期待値のことで，平均情報量とも呼びます．

# Σ を書くのが面倒なので，なるべく使わないように書いて行きます．(わかりにくいでしょうが…)

m 重マルコフモデルの一般的なエントロピーを求める計算はけっこう面倒なのですが，今回は 2 元の単純マルコフモデルなので，とても簡単です :-)

2. 解答

情報源全体のエントロピー H(S) は，各状態の定常状態確率 P (Sn) とエントロピー H(Sn) の積の和となる．

S1 では，0 と 1 を，それぞれ p, (1-p) の確率で発生させるので，H(S1) は，
H(S1) = - p * log_2 p - (1-p) * log_2 (1-p)
となり，同様に H(S2) は
H(S2) = - q * log_2 q - (1-q) * log_2 (1-q)
となる．

ゆえに，H(S) は

H(S) = p(S1) * H(S1) + p(S2) * H(S2)
       = ((1 - q + 2p) / (2 - q + p)) * (- p * log_2 p - (1-p) * log_2 (1-p))
          + ((1 - p) / (2 - q + p)) * (- q * log_2 q - (1-q) * log_2 (1-q))
       
       (面倒になってきたので，以下省略) [bit]

となる．

参考文献 塩野 充 (著) わかりやすいディジタル情報理論

情報理論のあまり良いサイトが見つからなかったので，さっき図書館に行って借りてきた本なのですが，この本はかなりわかりやすくて面白いです．いまさら暗号理論やセキュリティの面白さに目覚めてしまいました (笑)

# もう試験まで一週間切ってるのに… 遅いよ (^-^;)

まさか，こんなに面白いものだったとは… 今まで，なんとなく無味乾燥な感じがして，情報理論を真面目にやってこなかったのが悔やまれます (+ _ +;)

# 誤り訂正の理論は，けっこう高度な数学を用いるそうです．BCH 符号は，統計学者が，ガロア体という有限数学の概念を用いて考案したそうな．難しそうだけど，工夫次第でいろいろできそうな，とても可能性に富んだ研究領域という気がします (^o^)

---

2 つの符号語 (ビット列) 間のハミング距離 d を，異なるビットの数で定義する．例えば，
A = (0 1 0 0 0 0 0 1)， E = (0 1 0 0 1 0 0 1)， Z = (0 1 0 1 1 1 0 0) のとき，
d(A, E) = 1， d(A, Z) = 4
となる．以下の問に答えよ．

1．英数字を 7 bit で表し，8 ビット目として偶数パリティを追加した 8 ビットの符号語において，異なる符号語の対のハミング距離は 2 以上となることを示せ．

2．相異なる符号語の対をすべて考え，それらのハミング距離の最小値を d_min とする．d_min ≧ 2 t + 1 ならば，t ビット以下のエラーを訂正する方式が存在することを示せ．

1．解答

問題文より，符号語対間のハミング距離が 1 以上であることは自明である．
ハミング距離が常に 2 以上となることを示すために，ハミング距離が 1 の場合の反例を，背理法を用いて以下に示す．

任意の符号語対 A と B の間のハミング距離を 1 とする．
符号語 x 中の，値が 1 であるビットの数を f(x) とする．偶数パリティを用いているため f(x) は常に偶数である．
A と B のハミング距離は 1 なので， B 中の任意の 1 ビットが，
(i) 0 → 1 (ii) 1 → 0
の二通りに変化している場合が考えられ，(i) の場合，f(B) は f(A) + 1 となり，(ii) の場合，f(A) - 1 となる．
しかし，f(A) は偶数であるため，f(B) は必ず奇数となってしまう．
B も A と同様に，偶数パリティを用いているので，これは矛盾である．

よって，異なる符号語対間のハミング距離は 2 以上となることが示された．

2．解答

エラーを訂正する方法が存在するということは，(i) 符号にエラーが生じたことを特定でき，かつ (ii) 正しい符号に一意に訂正できる，ための条件をそれぞれ満たせば良い．

(i) を満たす条件について

問題文より，すべての符号間は少なくとも d_min 以上離れているので，ある符号対間のハミング距離が d_min ビット以下ということはありえず，もしそのような符号が存在した場合にはエラーとして検出することができる．

だが，d_min 個以上のビットに対してエラーが発生した場合には，エラーを検出できない場合も有り得る．そのため， (i) を満たすためには，エラーが d_min 個よりも少なくなければならない．

ハミング距離は離散値なので，(i) を満たすためには d_min - 1 以下のエラーでなくてはならない．

(ii) を満たす条件について

符号に対するエラーが (i) の範囲内の場合には，エラー符号 B から最も近いハミング距離を持つ正当な符号 A (全ての符号から，少なくとも d_min 以上ハミング距離が離れているという条件を満たす符号) が，正しい符号と言える．

最も近い符号が一意に定まるためには，d(A, B) ≦ d_min / 2 -1 でなければならない．

(なぜならば，この範囲を越えてしまうと，全く無関係な符号との距離が最も近くなってしまう場合が有り得るから)

ハミング距離の定義より，もし d(A, B) ≦ d_min / 2 - 1 ならば，その他の符号は必ず d(A, B) よりもハミング距離が大きくなる．

(もし，A とは異なる符号 C が最も B に近いと仮定すると，d(B, C) ≦
d_min / 2 - 1 となり，ハミング距離の定義により，d(A, B) + d(B, C) ≧ d(A, C) となるため， d(A, C) < d_min となってしまい，d_min の定義との矛盾が生じる)

そのため，d_min ≧ 2 t + 1 という条件を満たせば，エラーが t ビット以下の場合には必ず一意に一番近い符号が定まるため，(具体的な方法は，符号化の方法に依存するが) エラーを訂正する方式が存在する．

よって，d_min ≧ 2 t + 1 以下ならば，t ビット以下のエラーを訂正する方法が存在することが示された．

● <--- A に訂正できる B のエラーの範囲 (t ≦ d_min / 2 - 1) ---> ○
 A                                                                                   d_min / 2

● <--- A に訂正できない B のエラーの範囲 (t ≧ d_min / 2) ---> ● C
d_min / 2                                                           (全く無関係な符号が一番近くなってしまう)

---

短題 - 以下の小問について 400 字程度で解答せよ．

● 再帰プログラムとは何か．再帰プログラムによる計算が停止し，効率的であるためには，どのようにプログラムを作れば良いか．説明せよ．

再帰プログラムとは，「プログラムの定義中に，そのプログラムの定義自身が含まれているプログラム」 のことである．
プログラムが停止するためには，再帰的に含まれている部分が，必ず元の部分よりも簡単な形で定義されていて，なおかつ最終的な終了条件が明示されている必要がある．
このようにしてプログラムを定義すると，複雑なアルゴリズムを簡潔に定義できる場合が多い．
しかし，一般的に再帰プログラムは，計算の途中経過を全て保存しておく必要がある上に，同じ計算が何度も発生する場合も多く，著しく空間的・時間的な計算量が大きくなり，非効率である．
計算を効率的に行うためには，再帰処理を繰り返し処理に変換する (末尾再帰)， 計算の途中経過を次の処理の呼出時に直接渡し， 途中経過の保存を省略する (継続渡し)， 部分的な計算結果を保存しておき，何度も同じ計算が発生するのを防ぐ (メモ化) などのテクニックを用いてプログラムを作ると良い．

今日は 6 時に大学のネットワークが止まってしまうので，あわててアップ (汗) あさっては停電だ… (+ _ +;)

---

I am trying to write this weblog in English for practice in writing English.

In this morning, I found study books for TOEFL test which have been left in the corner of my bookshelf in my apartment room for a long time.

TOEFL文法問題440 TOEFL大戦略シリーズ
TOEFLテストパーフェクトリスニング
TOEFLテスト パーフェクトライティング
TOEFLテスト パーフェクトリーディング

I have bought those books when I was freshman because all freshman needed to take TOEFL test for the English placement test in our college.

But I didn't study hard enough at that time, and I didn't make good use those books.

Although I don't think so much good books now, I use those books for study because I don't want to waste those books.

I want to use those books effectively this time !

Today, I enjoyed studying READING and WRITING.

It was good that I feel my reading ability, though only gradually, is increasing day by day ;-)

But，then，I worriy about essay-type exam because I almost seemed as if the requirement of a essay at the graduate college entrance examination-level is acrually very high.
hummm… I may have to study it accordingly, too.

I'm nervous … (-o-;)

---