離散的ディリクレ問題とは

簡単に言えば数字を埋めるゲームです。 (自然数であれば何次元でも構いませんが)2次元の場合について説明すると、無限に広がる碁盤の上に、碁石ではなく数字によって地が作られています。これに対して、地のすべての目に対して、その数字が上下左右の目の数字の平均値になるように数字を埋めることができれば、問題が解けたことになります。

…という説明で理解することは非常に難しいため、具体例を出します。

f:id:interprism:20161211012714j:plain

色々とクォリティの低い図で恐縮ですが、この図は離散的ディリクレ問題の具体例の1つを表しています。ご覧の通り、数字に囲まれた目が2つあるということがわかります。では、このディリクレ問題を解いてみましょう。

f:id:interprism:20161211013510j:plain

左の目に2、右の目に3を入れるのが正解。実際、0,1,3,4の平均値は2であり、2,0,6,4の平均値は3です。これ以外に正解がないことは数学的に保証されています。詳しくは Principles of Random Walk - Springer あたりに書いてあります。先ほど検索をかけてみましたところ、電子版だと70ドルくらいで購入できるみたいですね。高い。

近似値を計算する

はじめ、数字を埋めるゲームと、紹介しましたが、実際に問題を解こうとすると非常に苦労します。下の図の問題は単純そうに見えますが、私は解答を見つけるのに1時間以上かかりました。

f:id:interprism:20161211223913j:plain

お気づきの方も多いとは思いますが、これは結局のところ連立一次方程式ですので、式を立てて、解けば、終わりです。ただの線形代数の具体的な計算問題とみなすことができます。一方で、確率論的な考え方として、Spiter(1964)では、それぞれの目の値は、そこからランダムに動く点が最初に接触する数字の期待値に等しいという事実が紹介してあります。したがって、(元々のゲームのコンセプトが崩壊しますが)完全な解答を出すことをあきらめて、近似値を求めようとすれば、javaの力を借りて実現できると考え、やってみました。方法は以下の通り:

数字を埋めたい目から、上下左右に等確率で動く動点を出発させる
地を取り囲む数字の場所に移動するするのを待つ。移動したら、その場所数字を記録する。
1,2の手順を適当な回数、繰り返し、数字の平均値を計算する。

実際に動かしたコードの一部を恥を忍んで公開したいと思います。

package randomWalk;

class D2MovingPoint {
    int x;
    int y;

    D2MovingPoint(int x, int y){
        this.x = x;
        this.y = y;
    }

    void moveUpward(){
        this.x++;
    }

    void moveDownward(){
        this.x--;
    }

    void moveRight(){
        this.y++;
    }

    void moveLeft(){
        this.y--;
    }

    int getXCoodinate(){
        return this.x;
    }

    int getYCoodinate(){
        return this.y;
    }

    void step(int direction){
        switch(direction){
            case 0:
                this.moveRight();
                break;
            case 1:
                this.moveLeft();
                break;
            case 2:
                this.moveUpward();
                break;
         default:
                this.moveDownward();
        }
    }
}

package randomWalk;

public class D2Inner {

    public static boolean isInbounds(int x, int y){
        if(x < -1 || x > 1){
            return false;
        }

        if(y < -1 || y > 1){
            return false;
        }

        return true;
    }

    public static boolean isInbounds(D2MovingPoint point){
        return isInbounds(point.getXCoodinate(), point.getYCoodinate());
    }

    public static double getScore(D2MovingPoint point){
        if(point.getYCoodinate() >1){
            return 5;
        }

        return 0;
    }
}

package randomWalk;

import java.util.Random;

public class WalkingController {
    private final long numberOfTrials = 10000;

    public double getAverageScore(int x, int y){
        double score = 0;

        for(int round = 0; round<numberOfTrials; round++){
             score += walk(x, y);
        }

        return score/numberOfTrials;
    }

    private double walk(int x, int y){
        Random random = new Random();
        D2MovingPoint point = new D2MovingPoint(x, y);
        int direction;

        while(D2Inner.isInbounds(point)){
            direction = random.nextInt(4);
            point.step(direction);
        }

        return D2Inner.getScore(point);
    }

    public long getNumberOfTrials(){
        return numberOfTrials;
    }
}