我怎么证明这个算法能正确地给出在办公桌抽屉里找到欧元的概率?

huangapple go评论66阅读模式
英文:

How do I proof, that this algorithm gives out the right probability for finding the euro in the desk drawers?

问题

作业
你的办公室里有一张桌子,有50%的几率放着一欧元。这张桌子有三个抽屉。如果这张桌子上有一欧元,它在三个抽屉中的任意一个里的可能性相等。如果你已经在第一个和第二个抽屉里徒劳地搜寻过了,那么欧元在第三个抽屉里的概率是多少?

解决方案:

int iterations = 10000;
int desk; // 0或1 - 50%的几率
int[] foundEuro = new int[5];

for (int i = 1; i <= iterations; i++) {
    desk = (int) (Math.random() * 2);

    if (desk == 0) { // 找到欧元
        int drawer = (int) (Math.random() * 3);

        if (drawer == 0) {
            foundEuro[drawer]++; // 欧元在第一个抽屉
        } else {
            foundEuro[drawer]++; // 欧元在第二个抽屉
            foundEuro[drawer + 1]++; // 欧元在第三个抽屉
        }
    } else {
        foundEuro[desk]++;
    }
}

showResult(foundEuro);
float probability = (((float) foundEuro[0]) / iterations) * 100;
System.out.printf("%.2f%%", probability);

输出
第一个抽屉中的欧元数量:1638
第二个抽屉中的欧元数量:6622
第三个抽屉中的欧元数量:3343
16.38%
注释
我认为我的代码没有错误,并且应该显示出正确的结果,但我不确定在前两个抽屉中没有找到欧元的情况下,在第三个抽屉中找到欧元的概率是否真的正确。

英文:

Assignment
There is a desk in your office that has a 50% chance of holding one euro. This desk has three drawers. If there is a euro in this desk, it is equally likely to be in one of the drawers. What is the probability that the euro is in the third drawer if you have already searched in vain for it in the in the first and second?

Solution:

int iterations = 10000;
int desk;// 0 or 1 - 50%        
int[] foundEuro = new int[5];

for (int i=1; i &lt;= iterations; i++){
    desk = (int) (Math.random() * 2);

    if ( desk == 0){ // found Euro              
        int drawer = (int) (Math.random() * 3);

        if ( drawer == 0){
            foundEuro[drawer]++; // euro in drawer1             
        } else {
            foundEuro[drawer]++; // euro in drawer2                 
            foundEuro[drawer+1]++; // euro in drawer3
        }
    } else {
        foundEuro[desk]++;
    }
}

showResult(foundEuro);
float probability = ( ((float) foundEuro[0]) / iterations) * 100;
System.out.printf(&quot;%.2f%%&quot;, probability);

Output
Euro in drawer 1: 1638
Euro in drawer 2: 6622
Euro in drawer 3: 3343
16,38%
Note
I think, my code has no errors and is supposed to show the right result, but idk if it is really the right probability for finding the euro in the third drawer, while in the other first two drawers it wasn't there.

答案1

得分: 2

你的算法和结果是错误的。你计算的基本上是硬币在给定抽屉中的概率,而这显然是1/2 * 1/3,即正确抽屉的概率 * 正确抽屉的概率 = 1/6,大约16.6%。

然而,正确答案是25%。你可以在纸上计算出来,或者你可以调整你的程序以正确反映“如果你在第一个和第二个抽屉中已经徒劳地搜寻过它”的限制条件。你基本上必须放弃那些违反这个约束条件的随机选择。代码如下:

int iterations = 100000;
int found = 0;
int violateThePrecondition = 0;
for (int i = 1; i <= iterations; i++) {
    int desk = (int) (Math.random() * 2);
    if (desk == 0) { // 找到欧元
        int drawer = (int) (Math.random() * 3);
        if (drawer == 2) { // 硬币在第2个抽屉中
            found++;
        } else { // 第0和第1个抽屉根据定义不能有硬币
            violateThePrecondition++;
        }
    }
}

float probability = (((float) found) / (iterations - violateThePrecondition)) * 100;
System.out.printf("%.2f%%", probability);

结果为> 25.05%。

对你的代码的最小更改应该是将概率计算更改为:

float probability = (((float) foundEuro[0]) / (iterations - foundEuro[2])) * 100;

所涉及的数学计算为(cNdM表示硬币在抽屉N中,桌子M中的概率 = 1/3 * 1/2 = 1/6,d0表示硬币在桌子0中的概率 = 1/2):

P(c2d0 | !c1d0 and !c0d0) = 
P(c2d0 and (!c1d0 and !c0d0)) / P(!c1d0 and !c0d0) = 
其中 (!c1d0 and !c0d0) = (!d0 or c2d0)
P(c2d0 and (!d0 or c2d0)) / P(!d0 or c2d0) =
P(c2d0) / (P(!d0) + P(c2d0)) =
1/6 / (1/2 + 1/6) =
1/6 / 4/6 =
1 / 4
英文:

Your algorithm and result is simply wrong. What you calculated is basically the probability of the coin being in a given drawer in the desk and that is obviously 1/2 * 1/3, probability of correct desk * probability of correct drawer = 1/6 roughly 16.6

The correct answer however is 25%. You can work that out on paper or you can adjust your program to properly reflect the 'if you have already searched in vain for it in the in the first and second' constraint. You basically have to discard those random coin choices that violate this constraint. The code then becomes:

int iterations = 100000;
int found = 0;
int violateThePrecondition = 0;
for (int i = 1; i &lt;= iterations; i++) {
    int desk = (int) (Math.random() * 2);
    if (desk == 0) { // found Euro
        int drawer = (int) (Math.random() * 3);
        if (drawer == 2) { // coin in drawer 2
            found++;
        } else { // drawers 0 and 1 can by definition not have the coin
            violateThePrecondition++;
        }
    }
}

float probability = (((float) found) / (iterations - violateThePrecondition)) * 100;
System.out.printf(&quot;%.2f%%&quot;, probability);

>25.05%

The minimal change to your code would have been to change the probability calculation to

float probability = ( ((float) foundEuro[0]) / (iterations - foundEuro[2])) * 100;

The math involved is (cNdM is the coin being in drawer N in desk M = 1/3 * 1/2 = 1/6, d0 is the coin being in desk0 = 1/2):

P(c2d0 | !c1d0 and !c0d0) = 
P(c2d0 and (!c1d0 and !c0d0)) / P(!c1d0 and !c0d0) = 
    with (!c1d0 and !c0d0) = (!d0 or c2d0)
P(c2d0 and (!d0 or c2d0)) / P(!d0 or c2d0) =
P(c2d0) / (P(!d0) + P(c2d0)) =
1/6 / (1/2 + 1/6) =
1/6 / 4/6 =
1 / 4

答案2

得分: 0

首先,您决定欧元是否在桌子上。如果我理解正确,一旦没有在桌子上,您会增加foundEuro[1]中的计数器,因为您处于else子句中,其中desk的值为1。当抽屉2中有欧元时,也会增加此完全相同的数组元素,因此66.22%的机会实际上是指欧元在其他地方或抽屉2中,而不仅仅是在抽屉2中。此外,我不明白为什么在drawer != 0时您总是同时增加抽屉2和抽屉3的计数器,您可能应该使用switch case语句。

其次,我认为您可能要查阅一下蒙提霍尔问题,这可能与您的问题有关,并能为您提供如何解决此类统计问题的提示,因为我认为您的假设已经存在问题。您的问题与代码关系较小,更多涉及如何解决概率问题,因此您可以查阅https://stats.stackexchange.com以获取更多帮助。

英文:

First, you decide, whether the Euro is in the desk at all or not. If I interpret this correctly, once it is NOT, you increase the counter in foundEuro[1], as you are in the else clause, where desk holds value 1. This exact same array element gets also increased, when there is a Euro in drawer 2, so the 66,22% chance is actually for the Euro being somewhere else OR in drawer 2 and not only for being in drawer 2. Additionally, I don't get why you always increase both counters for drawer 2 and drawer 3, when drawer != 0, you should probably make use of a switch case statement.

Second, I think you might check out the Monty Hall problem, which may be related and give you a hint towards how to approach this kind of statistics problem, as I think your assumptions are already flawed. Your question is less about the code and more about how to solve a probability problem, so maybe take a look at https://stats.stackexchange.com

答案3

得分: 0

找到桌子里一欧元的机会是50%,即1/2。
如果你找到一个,它在任何一个抽屉中的可能性都是相等的。
即在任何给定的抽屉中找到它的机会是(1/3)*(1/2)=1/6。

特殊情况是你在两个抽屉中都没有找到欧元的机会是4/6。它有可能在第三个抽屉中,在1/6的情况下是这样,在这个桌子里根本没有,在1/2=3/6的情况下是这样。这些机会不重叠,因此可以相加,1/6+3/6=4/6。

在这种特殊情况下,你在第三个抽屉中找到欧元的机会是(1/6)/(4/6)=1/4,因为该情况的机会乘以该情况的机会必须得出总机会,即(1/4)*(4/6)=1/6。

英文:

The chance for finding a Euro in the desk is 50%, 1/2.
If you find one, it is equally likely in any of the three drawers.
I.e. the chance to find it in any given drawer is (1/3)*(1/2)=1/6.

The special situation that you do not find the Euro in two of the drawers has a chance of 4/6. It could be in the third drawer in 1/6 cases and is not at all in this desk in 1/2=3/6. These chances do not overlap and can hence be added, 1/6+3/6=4/6.

The chance that you find the Euro in the third drawer, specially in that situation is (1/6)/(4/6)=1/4, because the chance of the situation, multiplied by the chance for that situation must yield the total chance, i.e. (1/4)*(4/6)=1/6.

huangapple
  • 本文由 发表于 2020年8月19日 18:03:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/63484607.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定