Monte Carlo 模拟

Question

我是 Java 编程专业 class 的学生。我的问题涉及对 Monte Carlo 模拟的解释。我应该找出从一个有 3 个 25 分 3 便士的钱包中取出四分之三或三个便士的概率。一旦一枚硬币被挑选出来，它就不会被更换。概率应为 0.1XXXXXXX。我的回答总是得到 0 或 1。这是我目前所拥有的。

public class CoinPurse {
    public static void main(String[] args) {
        System.out.print("Probability of Drawing 3 coins of the Same Type - ");
        System.out.println(coinPurseSimulation(100));
    }

    /**
     Runs numTrials trials of a Monte Carlo simulation of drawing 
     3 coins out of a purse containing 3 pennies and 3 quarters. 
     Coins are not replaced once drawn.
     @param numTrials - the number of times the method will attempt to draw 3 coins
     @returns a double - the fraction of times 3 coins of the same type were drawn.
     */

    public static double coinPurseSimulation(int numTrials) {
        final int P = 1;
        final int Q = 2;
        int [] purse = {Q, Q, Q, P, P, P};
        int [] drawCoins = new int[3];
        for (int draw = 0; draw < 3; draw ++) {
            int index = (int)(Math.random() * purse.length);
            drawCoins[draw] = purse[index];
            int [] newPurse = new int[purse.length-1];
            int j = 0;
            for (int i =0; i < purse.length; i++) {
                if (i == index) {
                    continue;
                }
                newPurse[j] = purse[i];
                j++;
            }
            purse = newPurse;
        }
        double number = 0.0;
        double result = 0.0;
        for (int i = 0; i < numTrials; i++) {
            result++;
            for (int j = 0; j < numTrials;j++) {
                if(drawCoins[0] == drawCoins [1] && drawCoins[1] == drawCoins[2]) {
                    number++;
                }
            }
        }
        return number/result;
    }
}

Answer 1

您需要将生成绘图的循环向下移动到 numTrials 循环中。按照您编写的方式，您进行一次抽奖，然后检查一次结果 numTrials 次。

我没有仔细检查您的绘制逻辑，但那是因为我推荐一种不同的（并且更简单的）方法。在你的 25 美分和 1 分硬币上使用 Collections.shuffle()，并在每次洗牌后检查前三个元素。

如果答对了，答案应该是2 * (3/6) * (2/5) * (1/4)，也就是0.1。

Answer 2

你只得到 0 或 1 的原因是你只 draw （或 pick ) 一次从钱包中取出硬币，但您随后 test 抽取 numTrials * numTrials 次。你有两个循环（索引 i 和 j）迭代 numTrials 时间 - 你的逻辑在那里有点混乱。

您可以将第一个循环（用于绘制个硬币）放在第二个循环（用于运行试验）中，您的代码将起作用。我在下面做了一个最小的重构（尽可能使用你的代码），后面有两条评论可能对你有更多帮助。

public class CoinPurse
{
    public static void main(String[] args)
    {
        System.out.print("Probability of Drawing 3 coins of the Same Type - ");
        System.out.println(coinPurseSimulation(100));
    }

    /**
     * Runs numTrials trials of a Monte Carlo simulation of drawing 3 coins out
     * of a purse containing 3 pennies and 3 quarters. Coins are not replaced
     * once drawn.
     * 
     * @param numTrials
     *            - the number of times the method will attempt to draw 3 coins
     * @returns a double - the fraction of times 3 coins of the same type were
     *          drawn.
     */

    public static double coinPurseSimulation(int numTrials)
    {
        final int P = 1;
        final int Q = 2;

        double number = 0.0;
        double result = 0.0;

        // Changed your loop index to t to avoid conflict with i in your draw
        // loop
        for (int t = 0; t < numTrials; t++)
        {
            result++;

            // Moved your draw without replacement code here
            int[] purse =
            { Q, Q, Q, P, P, P };
            int[] drawCoins = new int[3];

            for (int draw = 0; draw < 3; draw++)
            {
                int index = (int) (Math.random() * purse.length);
                drawCoins[draw] = purse[index];
                int[] newPurse = new int[purse.length - 1];
                int j = 0;
                for (int i = 0; i < purse.length; i++)
                {
                    if (i == index)
                    {
                        continue;
                    }
                    newPurse[j] = purse[i];
                    j++;
                }
                purse = newPurse;
            }

            // Deleted the loop with index j - you don't need to test the same
            // combination numTrials times...
            if (drawCoins[0] == drawCoins[1] && drawCoins[1] == drawCoins[2])
            {
                number++;
            }
        }

        return number / result;
    }
}

选币代码

我对你的拉币路线有一些意见：

它工作正常
比较麻烦
如果您将这段代码分解成一个单独的方法，您会更容易发现问题。

我先讲 3，然后讲 2。

将绘图代码分解为一个方法

private static int[] pickCoins(int[] purse, int numPicks)
{
    //A little error check
    if (numPicks > purse.length)
    {
        System.err.println("Can't pick " + numPicks + 
                           " coins from a purse with only " + purse.length + " coins!");
    }

    int[] samples = new int[numPicks];

    // Your sampling code here

    return samples;
}

您现在可以简单地从第二个循环内调用，即

drawCoins = pickCoins(purse, 3);

采样算法

recommends using Collections.shuffle() and then taking the first 3 coins in your collection (e.g. an ArrayList)。这是一个很好的建议，但我猜您还没有被介绍 Collections，并且可能不会 'allowed' 使用它们。如果你是 - 请使用它们。如果不是（正如我假设的那样），您可能需要考虑更好的方法来从 r 长度数组中随机抽取 n 项而不进行替换。

一种（广为接受的）方法是 Fisher-Yates shuffle 及其派生物。实际上，它涉及从数组的 unpicked 子集中随机选取。

在 Java - 一个工作示例如下 - 它通过将 picked 硬币移动到钱包的 "end" 并仅从第 maxInd 个未拾取的硬币。

    private static int[] pickCoins(int[] purse, int numCoins)
    {
        int[] samples = new int[numCoins];
        int maxInd = purse.length - 1;

        for (int i = 0; i < numCoins; i++)
        {
            int index = (int) (Math.random() * maxInd);
            int draw = purse[index];
            samples[i] = draw;
            // swap the already drawn sample with the one at maxInd and decrement maxInd
            purse[index] = purse[maxInd];
            purse[maxInd] = draw;
            maxInd -= 1;
        }

        return samples;
    }

预期结果

您说您的预期结果是 0.1XXXXXXX。在您学习 Monte Carlo 模拟时 - 您可能需要多考虑一下。预期结果取决于您进行了多少次试验。

首先，在这个简单的示例中，您可以考虑解析（或在某种意义上 exact）结果。考虑程序：

您抽取了您的第一枚硬币 - 无论是哪一枚都没有关系
无论是哪一枚硬币，袋子里还有 2 枚相同的硬币 - 捡到其中一枚的概率是 2 / 5
如果您在第 2 步中挑选了一枚匹配的硬币，现在包中还剩下 1 枚匹配的硬币。选择的概率是 1 / 4
因此，获得 3 个匹配硬币（任何面额）的概率是 2 / 5 * 1 / 4 == 2 / 20 == 0.1

您的 Monte Carlo 程序正在尝试估计该概率。如果有足够的估计（即 numTrials 足够高），您会期望它收敛在 0.1 上。它不会总是给出等于 0.1 甚至以 0.1 开头的值。如果试验次数足够多，它可能会给出以 0.09 或 0.1 开头的内容。但是，如果 numTrials == 1，它会给出 0 或 1，因为它会绘制一次并且绘制会匹配或不匹配。如果numTrials == 2，结果只能是0、0.5或1等。

进行 Monte Carlo 模拟以估计概率的教训之一是要有足够多的样本数以获得良好的估计。这又取决于您想要的准确性 - 您可以使用您的代码在它工作后进行调查。

Monte Carlo 模拟

Monte Carlo Simulation

java

simulation

probability

montecarlo

选币代码

预期结果