骑士首战失利后NBA系列赛夺冠概率计算的重复计数问题优化求助
7场4胜制系列赛概率计算优化方案
问题背景
骑士与勇士进行7场4胜制总冠军系列赛,单场双方胜率各为50%,已知骑士输掉第一场,求骑士最终赢得系列赛的概率。
DataCamp给出了Monte Carlo模拟和全量枚举两种解法,但两种方法都默认打满剩余全部6场,生成了大量不符合赛事提前结束规则的重复组合,需要过滤无效组合或者使用更合理的计算逻辑。
注:原DataCamp方法虽然存在重复计数的逻辑问题,但最终计算的概率数值是正确的。因为每一组重复的无效序列对应的总概率权重,刚好等于对应真实赛事路径的概率,最终结果11/32≈0.34375是准确的。
优化方案
方案1:模拟/枚举时加入提前终止逻辑
不管是Monte Carlo模拟还是路径枚举,都可以实时累计两队当前胜场,任意一队达到4胜就直接终止流程,避免生成无效后续场次:
优化版Monte Carlo模拟代码
B <- 10000 set.seed(1) results <- replicate(B, { cav_win <- 0 opp_win <- 1 # 对手已赢下第一场 # 逐场模拟直到系列赛结束 while(cav_win < 4 && opp_win <4) { res <- sample(0:1, 1) # 1代表骑士赢,0代表对手赢 if(res == 1) { cav_win <- cav_win + 1 } else { opp_win <- opp_win + 1 } } cav_win == 4 }) mean(results)
优化版有效路径枚举代码
# 递归生成所有符合规则的完赛路径 generate_valid_paths <- function(cav_win=0, opp_win=1, current_path=c()) { # 终止条件:任意一方达到4胜 if(cav_win == 4) return(list(c(current_path, 1))) if(opp_win == 4) return(list(c(current_path, 0))) # 递归枚举下一场两种结果 c( generate_valid_paths(cav_win + 1, opp_win, c(current_path, 1)), generate_valid_paths(cav_win, opp_win + 1, c(current_path, 0)) ) } all_paths <- generate_valid_paths() # 计算夺冠概率:每条路径概率为1/(2^路径长度) win_prob <- sum( sapply(all_paths, function(p) { if(tail(p, 1) == 1) 1/(2^length(p)) else 0 }) )
方案2:组合数学直接计算(最高效)
不用模拟和枚举,直接用组合公式计算所有骑士夺冠的场景概率求和即可:
骑士要夺冠,需要在系列赛结束时累计拿到4胜,对手最多拿3胜(对手已拿1胜,剩余场次最多赢2胜),分三种情况:
- 骑士4-1夺冠:剩余4场全胜,组合数
C(3,0)=1,概率1 * (1/2)^4 = 1/16 - 骑士4-2夺冠:前5场(剩余场次的前5场)骑士赢3场,第5场必须赢,组合数
C(4,3)=4,概率4 * (1/2)^5 = 4/32 - 骑士4-3夺冠:前6场(剩余场次的前6场)骑士赢3场,第6场必须赢,组合数
C(5,3)=10,概率10 * (1/2)^6 =10/64
三种场景求和得总概率:1/16 + 4/32 + 10/64 = 22/64 = 11/32 = 0.34375
方案3:基于原全量枚举结果过滤无效组合
如果一定要在原先生成的6场全量组合基础上去重,只需要提取每条序列的提前终止前缀,按前缀去重后计算权重即可:
library(dplyr) # 原先生成的6场全量组合 outcomes <- c(0,1) l <- rep(list(outcomes), 6) possibilities <- expand.grid(l) # 为每条序列计算终止场和唯一路径前缀 possibilities <- possibilities %>% rowwise() %>% mutate( # 累计胜场 cav_cum = list(cumsum(c_across(Var1:Var6))), opp_cum = list(cumsum(1 - c_across(Var1:Var6)) + 1), # 系列赛终止场位置 end_idx = which(cav_cum ==4 | opp_cum ==4)[1], # 唯一路径标识:终止前的场次结果 path_key = paste(c_across(Var1:Var6)[1:end_idx], collapse = "-"), # 是否骑士夺冠 is_win = last(cav_cum) >=4, # 路径权重 weight = 1/(2^end_idx) ) %>% ungroup() # 按唯一路径去重后计算概率 valid_prob <- possibilities %>% distinct(path_key, .keep_all = T) %>% summarise(prob = sum(weight * is_win)) %>% pull(prob)
内容的提问来源于stack exchange,提问作者Pineapple
相关产品推荐
相关产品推荐

