さらに、確率・統計の追加問題 （２月２０日） [お前らに質問]
追加問題１
箱に１、２、・・・、N（N≧２）の数字が書かれたカードがそれぞれ１、２、・・・N枚入っているとする。このとき、次の問に答えよ。
（１） 箱に入っているカードは合計何枚か。
（２） 箱から１枚取り出したカードに書かれている数字がk（1≦k≦N）である確率を求めよ。
（３） 箱から１枚取り出したカードに書かれている数字の期待値（平均値）を求めよ。
こんな問題はチョロいというヒトは次の問題を解いてみる。
追加問題２
２つの箱には１からｎまでの通し番号を書いたカードが入っている。各箱から同時に１枚ずつカードを取り出し、番号を比較して小さくない方をXとするとき、次の問に答えよ。
（１） X=kである確率をnとkで表わせ。ただし、kは整数で1≦k≦nとする。
（２） Xの期待値をnの式で表わせ。
まぁ、ドッチもチョロい問題だろう。秒殺と行こうぜ！！
この追加問題１を解く間のBGMとして
どうしてもわからないヒトは、N=2、n=2の場合についてまず考え、次に、N=3、n=3の場合で解くように。
面倒に思えても、こうした地道なことを繰り返した奴が最後に微笑むものだにゃ。
お前らに質問！！ 統計・確率編 （２月２０日） [お前らに質問]
統計不正という事件で、何やら、世の中が騒がしいので、お前らに確率・統計の問題を一つ出すにゃ。
問題
箱の中には、1〜N（Nは２以上）までの相異なる数字が書かれた玉がそれぞれ１個ずつ、合計N個入っている。その箱の中から１つ取り出した玉に書かれている数字をXとし、取り出した玉を戻さず、さらにもう１つ取り出した玉に書かれている数字をYとする。
このとき、次の問に答えよ。
（１） Xの期待値（平均値）はいくらか。
（２） X＋Yの期待値（平均値）はいくらか。
（３） １回目に取り出した玉を箱に戻したあとに、さらに、２回目の玉を取り出すように変更したとする。１回目に取り出した球に書かれている数をX、２回目に取り出した書かれている数をYとしたとき、X＋Yの期待値（平均値）はいくつになるか。
1,2,・・・,Nだと難しいというヒトは、N=2、N＝３の場合について、考えるといいにゃ。
参考までに、
N＝２の場合、
（１） X=1、X=2の確率はともに1/2だから、期待値〈X〉は
（２） （X,Y）の組み合わせは、（1,2）、（2,1）で、確率は共に1/2だから、
（３） （X,Y）の組み合わせは、（1,1）、（1,2）,（2,1）,（2,2）で、このそれぞれの確率は1/4だから、
「組み合わせ」という言葉は誤解を招くおそれがあり、適切でないかもしれない。何か、いい表現があったら、教えろ！！
（２）は、Z=X+Yとおくと、Z=3で、この確率は１だから、〈Z〉=〈X+Y〉=3
（２）は、Z=X+Yとおくと、確率分布が
|
Z |
2 |
3 |
4 |
|
確率p(Z) |
1/4 |
1/2 |
1/4 |
となるので、期待値は
と解くこともできる。
この場合、（２）と（３）は同じになるようですが、N=3の場合はどうなんだろうね。
より一般のNの場合、どうなるんだろう。
つまり、
１回目に取り出した球を箱に戻してから改めて２回目の球を取り出しても（復元抽出）、戻さずに２回目の球を取り出しても（非復元抽出）、２回取り出した球に書かれている数の和の期待値（平均）は変わらないのであろうか。
ちなみに、
のときの確率を
とすると、この期待値（平均値）
は
ただし
で定義されるにゃ。
期待値を表す記号を
と表す流儀もあるので、好きな方を選ぶといいにゃ。
Golden BallとGold Ballの違いってわかるケロか。
この２つは意味が違うにゃ。
その回答が正しかろうが、間違っていようが、その回答を清書した上に、ブログの記事としてアップするにゃ。
挿入法 [数値解析]
挿入法
基本選択法よりも、さらに、効率のよい整列法である挿入法について、{4,2,5,1,3}を例に説明する。
まず、{4,2,5,1,3}の部分列（部分集合）である{4,2}に注目し、最後尾の要素2の挿入箇所を探し、そこに２を挿入すると
{4,2}→{2,4}
になり、{4,2}の並び替えが終了する。
次に、{2,4,5}の最後尾の５の挿入箇所を探し、そこに１を挿入する。すると、次のようになる。
{2,4,5}→{2,4,5}
同様に、
{2,4,5,1}→{1,2,4,5}
最後に、最後尾の３の挿入箇所を探し、そこに３を挿入すると、
{1,2,4,5,3}→{1,2,3,4,5}
と、{4,2,5,1,3}を昇順に整列することができる。
一般に、
の場合、
i=2,3,・・・,nに対して、
部分列
における
の挿入箇所を探索し、そこにを挿入することによって、整列することができる。
この手順を、アルゴリズム的に書くと次のようになる。
do i=2, 3, ・・・, n
do j=i, i−1, ・・・, 2
a(j−1)>a(j)ならば、a(j−1)とa(j)を交換
end do j
end do i
この方針に基づいてプログラムを書くと、次のようになる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
end if
end do
end do
write(*,*) a
end
このプログラムで昇順にデータを整列できるのですが、たとえば、
{2,4,5}
のように整列の必要のない部分列に関しては、整列の処理を省くことができるので、次のようにプログラムを改良することできる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
end do
write(*,*) a
end
これで無駄な、無意味な挿入箇所の探索省くことが可能となり、より高速に並び替えを行うことができるのですが、a(j−1)とa(j)の交換処理には
w=a(j); a(j)=a(j-1); a(j-1)=w
と３つの作業が必要になるので、まだまだ、無駄が多い。
そこで、アルゴリズムを次のように変更する。
do i=2, 3, ・・・, n
t=a(i)
do j=i, i−1, ・・・, 2
a(j−1)>tならば、a(j)をa(j−1)に代入 （a(j−1)を１つ後ろにずらす）
そうでなければ、ループを抜ける
end do j
tをa(j)に代入
end do i
このように変更すると、
w=a(j); a(j)=a(j-1); a(j-1)=w
を
a(j)=a(j−1)
と１つの作業にすることができる。
これで、より、高速に並び替えを行うことができる。
parameter(n=100)
integer a(n)
integer t
do i=1, n
a(i)=nrandom(n) ! 乱数を使って1〜nまでのデータの作成
end do
do i=2,n
t=a(i) ! a(i)をtにコピー
do j=i,2,-1
if(a(j-1).gt.t) then ! a(j-1)とtの比較
a(j)=a(j-1) ! a(j-1)を後方に１つずらす
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
a(j)=t ! tを挿入
end do
write(*,100) (a(i), i=1,n)
100 format (10(i8))
end
function nrandom(n)
call random_number(x)
nrandom = n*x+1
end
