已知18洞x次birdies+，求k+连续birdies+的精确概率及高效解法

问题描述 #

需要计算18洞高尔夫回合中，当出现x次Birdies+（记为1，其余洞为0）时，存在连续k杆及以上Birdies+的概率。当前使用模拟方法效率低下，只能获取近似值，需实现精确解。

原模拟代码依赖随机抽样生成序列，再用rle检测连续段，模拟次数越多耗时越长，结果仅为近似值：

golf_streak <- function(x,k){
  test <- lapply(x, function(i) {sample(c(rep(1, i), rep(0, 18 - i))) })
  t <- lapply(test, rle)
  as.numeric(sapply(t, function(rl) any(rl$lengths[rl$values == 1] >= k)))
}

精确解思路 #

采用补集思想：先计算「没有连续k个Birdies+」的序列数，再用1减去该数占总可能序列数的比例，得到目标概率。

1. 总可能序列数：从18洞中选x个作为Birdies+，即组合数C(18, x)。
2. 有效序列数（无连续k个1）：用动态规划递推计算，核心逻辑是：
   • 若当前洞是0，则前17洞需满足x个1且无连续k个；
   • 若当前洞是1，则往前最多k-1个连续1，排除掉最后k个全是1的非法情况。

R语言精确实现代码 #

# 计算无连续k个1的序列数
count_valid_sequences <- function(n, m, k) {
  if (m == 0) return(1)
  if (m > n) return(0)
  if (m < k) return(choose(n, m))
  
  # 动态规划矩阵：dp[i,j]表示i个洞放j个1，无连续k个1的序列数
  dp <- matrix(0, nrow = n + 1, ncol = m + 1)
  dp[, 1] <- 1  # 0个1的情况，所有洞数都只有1种序列
  
  for (i in 1:n) {
    for (j in 1:min(i, m)) {
      if (j < k) {
        dp[i+1, j+1] <- choose(i, j)
      } else {
        # 递推：当前洞放0 + 当前洞放1，减去最后k个全是1的非法情况
        val <- dp[i, j+1] + dp[i, j]
        if (i - k >= 0 && j - k >= 0) {
          val <- val - dp[i - k, j - k + 1]
        }
        dp[i+1, j+1] <- val
      }
    }
  }
  dp[n+1, m+1]
}

# 计算目标精确概率
golf_streak_exact <- function(x, k) {
  total <- choose(18, x)
  if (total == 0) return(0)  # x超出0-18范围时返回0
  valid <- count_valid_sequences(18, x, k)
  1 - valid / total
}

使用示例 #

比如计算18洞有6次Birdies+，出现连续3杆及以上的概率：

golf_streak_exact(6, 3)

内容的提问来源于stack exchange，提问作者jdsdog10