【专题】概率期望

meteor2008 / 2024-11-11 / 原文

前言

期望的计算公式：

\[E(X) = \sum_i{i\times P(x=i)} \]

期望的线性性：

\[E(X+Y) = E(X)+E(Y), E(kX) = kE(X) \]

百事世界杯之旅

[SHOI2002]百事世界杯之旅

题目描述

假设有 $n$ 个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

解：

令$f(i)$表示现在收集了$i$个球星名字的情况下，还需要购买饮料的期望次数。

\[f(i)=1+\frac{i}{n}f(i)+\frac{n-i}{n}f(i+1) \]

显然$f(n)=0$，于是倒推出$f(0)$就得到答案了。

然后进行一个自己推自己，就得到了：

\[f(i)=f(i+1)+\frac{n-i}{n} \]

这题的输出格式有点谔谔

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int get(int x){
	int ret = 0;
	while(x){
		ret++;
		x /= 10;
	} return ret;
}

int gcd(int x, int y){
	if(!x) return y;
	return gcd(y%x, x);
}

// f(x) = f(x+1)(n-x)/n + f(x)x/n + 1
signed main(){
	int n; scanf("%lld", &n);
	int ans1 = 0, ans2 = 1;
	for(int i = 0; i < n; i++){
		ans1 = ans2*n+ans1*(n-i);
		ans2 *= n-i;
		int qwq = gcd(ans1, ans2);
		ans1 /= qwq, ans2 /= qwq;
	}
	if(ans1 % ans2 == 0){
		printf("%lld\n", ans1/ans2);
		return 0;
	}
	int ans3 = ans1/ans2;
	ans1 = ans1%ans2;
	for(int i = 1; i <= get(ans3); i++)
		putchar(' ');
	printf("%lld\n", ans1);
	if(ans3) printf("%lld", ans3);
	for(int i = 1; i <= get(ans2); i++)
		putchar('-'); putchar('\n');
	for(int i = 1; i <= get(ans3); i++)
		putchar(' ');
	printf("%lld\n", ans2);
	return 0;
}

收集邮票

题目描述

有$n$种邮票，每次买一张，买到每种邮票的概率是相同的（$\frac{1}{n}$），但是每次购买邮票的费用不同，第$k$次购买需要支付$k$元钱。

问收集所有种类的邮票的期望花费。（输出保留二位小数）

解：

如果买了$m$次邮票，则花费为$c=\frac{(m+1)m}{2}$。
根据期望的线性性，$E(c) = \frac{1}{2}[E(m^2)+E(m)]$

根据上一题的结论，对于购买次数的期望有$f(i)=f(i+1)+\frac{n}{n-i}$

设$g(i)$表示现在收集了$i$种邮票的情况下，还需要购买邮票的期望花费。

\[g(i)=\frac{i}{n}{[g(i)+f(i)+1]} + \frac{n-i}{i}{[g(i+1)+f(i+1)+1]} \]

再进行一个自己推自己，简化为：

\[g(i) = \frac{i}{n-i}\times f(i) + g(i+1) + f(i+1) + \frac{n}{n-i} \]

点击查看代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+5;
double f[N],g[N];
int n;

int main() {
	scanf("%d", &n);
	for(int i = n-1; i >= 0; --i){
		f[i] = f[i+1]+(1.0*n)/(1.0*(n-i));
		g[i] = (1.0*i)/(1.0*(n-i))*(f[i]+1);
        g[i] += g[i+1]+f[i+1]+1;
	}
	printf("%.2lf\n", g[0]);
	return 0;
}