where XiXi is the number of balls in the ith box, and X¯X¯ is the average number of balls in a box.
Your task is to find out the expected value of V.
InputThe input contains multiple test cases. Each case contains two integers n and m (1 <= n, m <= 1000 000 000) in a line.
The input is terminated by n = m = 0.
OutputFor each case, output the result as A/B in a line, where A/B should be an irreducible fraction. Let B=1 if the result is an integer.Sample Input
2 1
2 2
0 0
Sample Output
0/1
1/2
Hint
In the second sample, there are four possible outcomes, two outcomes with V = 0 and two outcomes with V = 1. 概率期望问题,启发博客:http://blog.csdn.net/xzxxzx401/article/details/52167534 以下
首先这是一个二项分布。对于一个盒子来说,n次实验是扔n个球,每次进入盒子概率是1/m。样本方差的期望等于总体的方差!证明爱看不看。直接的结果:E(V)=n∗(m−1)m2
-
有不用这个性质直接推出公式的。膜大神。
E(V)=E(∑ni=0(Xi−X¯)2)m=E(x2)−2∗nm∗E(x)+n2m2
E(x)=nm
E(x2)=D(x)+[Ex]2
二项分布,D(x)=n∗(m−1)m2
所以带到上面的式子中就变成了E(V)=n∗(m−1)m2 -
官方题解我是看不懂。
E[V]=E[∑mi=1(Xi−X¯)2m]=E[(Xi−X¯)2]=E[X2i−2XiX¯+X¯2]
=E[X2i]−2X¯E[Xi]+E[X¯2]=E[X2i]−2X¯2+X¯2=E[X2i]−n2m2
所以关键是要求出E[X2i]. 我们用随机变量Yj来表示第j个球是否在第i个盒子中,如果在则Yj=1,否则Yj=0. 于是
E[X2i]=E[(∑nj=1Yj)2]=E[∑nj=1Y2j]+2E[∑nj=1∑nk=1,k≠jYjYk]=nE[Y2j]+n(n−1)E[YjYk]
=nm+n(n−1)m2
因此,
E[V]=nm+n(n−1)m2−n2m2=n(m−1)m2
#include<iostream>
#include<cstdio>
using namespace std; long long gcd(long long b,long long c)//计算最大公约数
{
return c==?b:gcd(c,b%c);
} int main()
{
long long n,m;
long long a,b;
while(~scanf("%lld%lld",&n,&m)&&(n+m))
{
a=n*(m-);
if(a==)
printf("0/1\n");
else
{
b=m*m;
long long g=gcd(a,b);
printf("%lld/%lld\n",a/g,b/g);
}
}
return ;
}