Hatena::ブログ(Diary)

kouri128まとめ このページをアンテナに追加 RSSフィード

2012-05-18

[] シンプル 01:52  シンプルを含むブックマーク

よくある期待値を求める問題で、簡単に考えることって難しいと感じた。

その問題は、表になる確率が p 、裏になる確率が q (p + q = 1) のコインを n 回投げたとき、表になる回数の期待値を求めるというもの。

ここで、確率変数 X を n 回コインを投げて表になる回数としてしまうと

E¥[X¥]¥¥=¥sum_{k=0}^n k {n ¥choose k} p^k q^{n-k}¥¥=¥sum_{k=1}^n k {n ¥choose k} p^k q^{n-k}¥¥=¥sum_{k=1}^n k ¥frac{n!}{k!(n - k)!} p^k q^{n-k}¥¥=¥sum_{k=1}^n ¥frac{n!}{(k-1)!(n - k)!} p^k q^{n-k}¥¥=¥sum_{k=0}^{n-1} ¥frac{n!}{k!(n-k-1)!} p^{k+1} q^{n-k-1}¥¥=np¥sum_{k=0}^{n-1} ¥frac{(n-1)!}{k!(n-k-1)!} p^k q^{n-k-1}¥¥=np¥sum_{k=0}^{n-1} {n - 1 ¥choose k} p^k q^{(n-1)-k}¥¥=np(p+q)^{n-1}¥¥=np

という長い旅になってしまう(数式かくの疲れた・・・)。

ところが、X_i を i 回目にコインが表になるとき 1、裏になるとき 0 をとる確率変数とすると X=X_1+X_2+¥dots+X_n になって、期待値の線形性とすべての確率変数の期待値が等しくなることを利用して

E¥[X¥]¥¥=E¥[X_1+X_2+¥dots+X_n¥]¥¥=E¥[X_1¥]+E¥[X_2¥]+¥dots+E¥[X_n¥]¥¥=nE¥[X_1¥]¥¥=np

と簡単に求められる。

どうやったら後者のような考え方がすぐできるようになるんだろう。やっぱり訓練の賜物なのかな。

問題を簡単にして考えることって数学以外でもいろいろな場面で役立つと思うので、ちゃんと身につけたい。

daimatzdaimatz 2012/05/19 10:25 たぶん問題の文脈を無視してるからこんな発想出ちゃうんですが、期待値を求めるだけであれば確率変数の話を出さずに
E[1] = p, E[n+1] = E[n] + p の漸化式でいいのでは?と思ってしまいます。
でもこれは後者の考え方と同じか・・

kouri128kouri128 2012/05/19 14:47 ちょっと問題が簡単すぎたかも。計算しなくてもnpって自然に分かるしな…
そういう漸化式で解くっていう発想も含めて、ストレートに問題に取り組む以外のやり方を思いつく人ってどう考えているのかなって思って書きました。

トラックバック - http://d.hatena.ne.jp/kouri128/20120518

2010-09-25

[] privateの勘違い 04:34  privateの勘違いを含むブックマーク

最近まで勘違いしていて,JavaC++のprivateでは

class A {
    private int val;
    public void copy(A a) {
        val = a.val;
    }
}

とできないと思っていました.できるのね.

外部に隠蔽すればいいわけだから,同じクラスの他のオブジェクトについてはprivateフィールドにアクセスしてもOK.考えてみればそうであってほしいですね.今までどんなときでもgetter,setterでアクセスしていました.

トラックバック - http://d.hatena.ne.jp/kouri128/20100925

2010-09-09

[] JavaC++の違い 01:39  JavaとC++の違いを含むブックマーク

最近やっとEffective C++を読めるようになりました.読み進める中で,同じような機能でもJavaC++にいろいろと違いがあることに驚いています.今日はそんな一例.

Javaで次のようなソースコードを考えます.Aではコンストラクタ初期化用メソッドinit()を呼び出すようになっていて,Bもinit()をオーバーライドすることで初期化をおこなうというもの.メソッドf()はコンストラクタとメソッドでの振舞いの違いを調べるためにinit()を呼び出します.

class A {
    public A() {
        init();
    }
    public void f() {
        init();
    }
    protected void init() {
        System.out.println("A");
    }
}

class B extends A {
    protected void init() {
        System.out.println("B");
    }
}

public class Test {
    public static void main(String[] args) {
        B b = new B();
        b.f();
    }
}

このコードの出力は

B
B

となります.サブクラスBのオブジェクトが生成されるときBのinit()が呼び出されました.もちろん,b.f()の結果もBのinit()が呼び出されます.

Aのコンストラクタで呼び出されるinit()がBのinit()になるなんてとんでもない!!という意見もあると思います.その場合,どうぞ初期化用メソッドをオーバーライドしてくださいと言わんばかりにinit()をprotectedで定義していることが問題で,実際にprotectedをprivateに変更すると出力結果は

A
B

となります.このような挙動はアクセス修飾子の意図に沿っているように思います.

それに対してC++では,上記のJavaコードをまねたソースコードで・・・

#include <iostream>
using namespace std;

class A {
public:
    A();
    void f();
protected:
    virtual void init();
};
A::A() {
    init();
}
void A::f() {
    init();
}
void A::init() {
    cout<<"A"<<endl;
}

class B: public A {
protected:
    virtual void init();
};
void B::init() {
    cout<<"B"<<endl;
}

int main(void) {
    B b;
    b.f();
}

もう分かる方には分かると思いますが,このコードの出力は

A
B

となります.

C++ではスーパークラスコンストラクタの中でinit()のような仮想関数を呼び出す場合,そのスーパークラスの仮想関数が呼び出されます.これは,アクセス指定子をどれにしても同じです.もちろん,A::init()を純粋仮想関数にするとコンパイラに怒られます.

このような落とし穴にはまることは少ないかもしれませんが,ありえるコードのような気がするので,JavaC++を扱うプログラマさんは心の隅に留めておきましょう.

JavaプログラマC++もやる人はぜひEffective C++読んでみてください!比較して読むと,よりおもしろいと思います.

トラックバック - http://d.hatena.ne.jp/kouri128/20100909

2010-08-20

[] 大域変数初期化は誰がする? 01:18  大域変数の初期化は誰がする?を含むブックマーク

最近,研究で小規模なOSを構築しています.C言語の仕様で未初期化の大域変数はゼロで初期化されることになっているので,OS自身で.bssセクションをゼロで初期化しています.が,この初期化ってふつう誰がおこなっているんだっけ?と気になって調べてみました.間違いなどあれば指摘してもらえると嬉しいです.

初期化してない変数と.bssセクションを覗くと

ということで,C言語の大域変数は.bssセクションに配置されることが多いようです.(ただし,PEの仕様では.bssセクションの初期化を要求していないようです.)

他にもサイトを巡ってみましたが,WindowsLinuxなどOSがある場合はプログラムローダが.bssセクションを初期化し,組込みではプログラム自身が.bssセクションを初期化することが多いみたいです.(ここらへん自信ない)

また,組込みでは起動時間に直結するため,必要になってから初期化をしたり,そもそも初期化をしなかったりするようです.OSASK計画 - osaskwiki : x [design002]なんかでは,OSに.bssセクションを初期化する責任がないことを強調しています.

調べてみると,分からないことだらけだと痛感してしまいます.もっとがんばらなくては!!

トラックバック - http://d.hatena.ne.jp/kouri128/20100820

2010-05-04

[][]任天堂 “驚き”を生む方程式 12:01 任天堂 “驚き”を生む方程式を含むブックマーク

任天堂 “驚き”を生む方程式

任天堂 “驚き”を生む方程式

トラックバック - http://d.hatena.ne.jp/kouri128/20100504