山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

行と列の入れ替えに関する問題 その2

行列の列の入れ替えと行の入れ替えて得られる行列について

yamakasa3.hatenablog.com

上記の記事の行列の操作によって得られる行列の要素が元の行列の要素の位置と一致する期待値を考えていたんですが、良く分かりませんでした。

         
 1 2 \cdots n
 n+1 n+2 \cdots 2n
 \vdots \vdots \ddots \vdots
 n(n-1) + 1 n(n-1) +2 \cdots n^2

 1次元配列の場合

 1次元配列の場合、最大値を n とすると、配列 a

 a = [ 1, 2, \cdots , n]

となり、この配列の順列は、 n! 通りあります。また、元の位置に存在する番号の合計は n! となるので、求める期待値は E

 E = \dfrac{n!}{n!} = 1

となります。

また、ある要素が元の位置に存在する確率は、 \dfrac{1}{n} であり、全体で n 個の数字が存在するので、期待値の線形性から、

 E = n \times \dfrac{1}{n} = 1

となります。

行列の場合

先程の記事にあるとおり、行の入れ替えと列の入れ替えによって得られる行列は、 (n!)^2 通りあります。

操作によって得られる行列の要素が元の位置にあるものの個数を求めるコード
public class Test {
    static int [][]A;
    static int n;
    static int cnt = 0;
    static int [][]row;
    static int [][]col;
    public static void main(String[] args) {
        n = 3;
        A = new int[n][n];

        row = new int[n][n];
        col = new int[n][n];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                row[i - 1][j - 1] = i + n * (j - 1);
                col[i - 1][j - 1] = j + n * (i - 1);
            }
        }

        int cnt = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                A[i][j] = cnt;
                cnt ++;
            }
        }

        int l = factorial(n);
        int [][]ary = new  int[l][n];

        int []a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = i;
        }
        perm(0, a, new boolean [n + 1], ary);

        int sum = 0;
        for(int i = 0; i < l; i++) {
            swapR(ary[i]);
            copyCol();
            for(int j = 0; j < l; j++) {
                swapC(ary[j]);
                sum += count(A);
                //disp(A);
            }
        }
        System.out.println(sum);


    }
    static void copyCol() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                col[i][j] = A[i][j];
            }
        }
    }

    static void swapR(int []a) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j  <n; j++) {
                A[j][i] = row[a[i] - 1][j];
            }
        }
    }

    static void swapC(int []a) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j  < n; j++) {
                A[i][j] = col[a[i] - 1][j];
            }
        }
    }

    static  int factorial(int n) {
        if(n == 1) {
            return n;
        }else {
            return n * factorial(n - 1);
        }
    }
    static void disp(int [][]A) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(A[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static int count(int [][]A) {
        int cnt = 0;
        int k = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(A[i][j] == k) {
                    cnt ++;
                }
                k ++;
            }
        }
        return cnt;
    }
    static void perm(int n, int[] a, boolean[] flag, int[][] ary) {
        if(n == a.length) {
            for(int i = 0; i < ary[0].length; i++) {
                ary[cnt][i] = a[i];
            }
            cnt ++;
            return;
        }
        for(int i = 1; i <= a.length; i++) {
            if(flag[i]) continue;
            a[n] = i;
            flag[i] = true;
            perm(n + 1, a, flag, ary);
            flag[i] = false;
        }
    }
}

コードから得られた数字を元に類推する

次元が iの行列の要素が元の位置にある要素の個数を m_iとします。

実際にコードを動かすと、

 m_1 = 1

 m_2 = 4

 m_3 = 36

 m_4 = 576

 m_5 = 14400

となりました。

したがって、 m_n = (n!)^2

と推測できます。

よって、求める期待値は

 E = \dfrac{(n!)^2}{(n!)^2} = 1

となります。

期待値の線形性から求める方法

期待値の線形性は確率変数が独立でなくとも成り立ちます。

行列においてある要素がもとの位置に存在する確率は、

 \dfrac{1}{n^2}

です。また、数字の種類は n^2通りあるので、求める期待値は

 E = \dfrac{n^2}{n^2} = 1

となります。

ここで不思議に思ったことがあります。行の入れ替えや列の入れ替えでは、元の行列において同じ列や行にある数字は操作によって変化しないということです。つまり、列の要素の順番や行の要素の順番は変わりますが、要素の集合は変わらないということです。

この条件でも期待値の線形性から導けたということなんでしょうか。

うーん。良く分かりません。確率とか場合の数って苦手だったんですよね。