蒙特卡罗模拟

Question

我是 Java 编程课程的学生。我的问题涉及对蒙特卡罗模拟的解释。我应该找出从一个有 3 个四分之三和 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

你只得到0或者1是你只从钱包中抽取（或挑选）硬币一次的原因，然后你测试抽取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;
    }
}

捡硬币代码

我对您绘制硬币的路线有一些评论：

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

我将先解决 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);

采样算法

@pjs 的回答建议使用Collections.shuffle()然后取出您收藏中的前 3 个硬币（例如ArrayList）。这是一个很好的建议，但我猜你还没有被介绍过Collections，并且可能不被“允许”使用它们。如果您是 - 请使用它们。如果不是（正如我所假设的），您可能需要考虑更好的方法来从 r 长度数组中随机抽取 n 个项目而无需替换。

一种（广为接受的）方式是Fisher-Yates shuffle及其衍生物。实际上它包括从随机挑选取消拾取的阵列的子集。

在 Java 中——一个工作示例如下——它的工作原理是将捡到的硬币移动到钱包的“末端”，然后只从第一个未捡起的硬币中捡取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。在学习蒙特卡罗模拟时，您可能需要多考虑一下。预期结果取决于您进行了多少次试验。

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

1. 你掏出你的第一枚硬币——它是哪个并不重要
2. 无论是哪枚硬币，袋子里还剩下 2 个相同的硬币 - 选择其中一个的概率是 2 / 5
3. 如果您在第 2 步中选择了其中一枚匹配的硬币，则袋子中现在还剩下 1 个匹配的硬币。被选中的概率是1 / 4
4. 因此，获得 3 个匹配硬币（任一面额）的概率为 2 / 5 * 1 / 4 == 2 / 20 == 0.1

您的蒙特卡罗程序正在尝试估计该概率。如果有足够的估计（即足够高），您会期望它收敛于 0.1 numTrials。它不会总是给出等于或什至以 开头的值0.1。通过足够数量的试验，它可能会给出一些开始0.09或0.1. 但是，如果numTrials == 1，它将给出0或1，因为它将绘制一次并且绘制将匹配或不匹配。如果numTrials == 2，结果只能是0，0.5或1等等。

进行蒙特卡罗模拟来估计概率的教训之一是具有足够高的样本数以获得良好的估计。这反过来又取决于您想要的准确性 - 一旦它工作，您就可以使用您的代码进行调查。