返回题库

游程数

Number of Runs

专题
Statistics / 统计
难度
L5

第 1 小问

题目详情

想象一下，你有一副标准的 52 张牌（一半是红色，另一半是黑色）。连续被定义为连续抽出的一组卡片，并且所有卡片都具有相同的颜色。例如，BBRRBBB 有 3 次运行。

第 1 部分

求出一副洗过的牌的预期运行次数。

Imagine you are given a standard deck of 52 cards (half of the cards are red and the other half are black). A run is defined as a block of cards that are drawn consecutively and all have the same color. As an example, BBRRBBB has 3 runs.

Part 1

Find the expected number of runs in a shuffled deck of cards.

解析

假设我们有一系列卡片 X1,X2,...,XnX_1, X_2 , ..., X_n。每个XiX_i对应一张黑牌或一张红牌。

现在，假设我们有另一个变量 YY，它检查 XiX_i 和 Xi−1X_{i-1} 是否是相同的色卡。具体来说，如果是 Xi≠Xi−1X_i \neq X_{i-1}，则 Yi=1Y_i=1，否则 Yi=0Y_i =0。我们将 Xi≠Xi−1X_i \neq X_{i-1} 的情况标记为 1，因为它代表一次运行的结束，而我们的目标是找到预期的运行次数。

接下来我们要找到E[Y1,...,Yn]=E[Y1]+E[Y2]+...+E[Yn]E[Y_1, ..., Y_{n} ]=E[Y_1]+E[Y_2]+ ... +E[Y_n]。由于Xi≠Xi−1X_i \neq X_{i-1}时E[Yi]E[Y_i]为1，我们可以表示E[Yi]=P(Xi≠Xi−1)E[Y_i] = P(X_i \neq X_{i-1})

预期运行次数为： E[N]=∑151P(Xi≠Xi−1)+1\begin{equation} E[N] = \sum_{1}^{51} P(X_i \neq X_{i-1})+1 \end{equation} 上面等式中的+1代表我们抽到的第一张牌。这张牌将始终被算作一局，因为在它之前没有抽过牌。 E[N]=∑151Number of ways Xi≠Xi−1Total number of combinations+1=51(2651)+1=27\begin{equation} E[N] = \sum_{1}^{51} \frac{\text{Number of ways} \space X_i \neq X_{i-1}}{\text{Total number of combinations}} +1 =51(\frac{26}{51})+1=27 \end{equation}

Original Explanation

Imagine we have a sequence of cards X1,X2,...,XnX_1, X_2 , ..., X_n . Each XiX_i corresponds to either a black card or a red card.

Now, let’s imagine that we have another variable YY which checks whether XiX_i and Xi−1X_{i-1} are the same color card. Specifically, if Xi≠Xi−1X_i \neq X_{i-1} then Yi=1Y_i=1 otherwise Yi=0Y_i =0. We mark the case of Xi≠Xi−1X_i \neq X_{i-1} as 1 because it represents the end of a run and our goal is to find the expected number of runs.

Next we want to find E[Y1,...,Yn]=E[Y1]+E[Y2]+...+E[Yn]E[Y_1, ..., Y_{n} ]=E[Y_1]+E[Y_2]+ ... +E[Y_n]. Since E[Yi]E[Y_i] is 1 when Xi≠Xi−1X_i \neq X_{i-1} we can express E[Yi]=P(Xi≠Xi−1)E[Y_i] = P(X_i \neq X_{i-1})

The expected number of runs is:

E[N]=∑151P(Xi≠Xi−1)+1\begin{equation} E[N] = \sum_{1}^{51} P(X_i \neq X_{i-1})+1 \end{equation}

The +1 in the equation above represents the first card that we draw. This card will always be counted as one run because there are no cards that were drawn before it.

E[N]=∑151Number of ways Xi≠Xi−1Total number of combinations+1=51(2651)+1=27\begin{equation} E[N] = \sum_{1}^{51} \frac{\text{Number of ways} \space X_i \neq X_{i-1}}{\text{Total number of combinations}} +1 =51(\frac{26}{51})+1=27 \end{equation}

第 2 小问

题目详情

想象一下，你有一副标准的 52 张牌（一半是红色，另一半是黑色）。连续被定义为连续抽出的一组卡片，并且所有卡片都具有相同的颜色。例如，BBRRBBB 有 3 次运行。

第 2 部分

编写一个程序，计算一副具有 YY 颜色的 XX 卡片的预期运行次数。

Imagine you are given a standard deck of 52 cards (half of the cards are red and the other half are black). A run is defined as a block of cards that are drawn consecutively and all have the same color. As an example, BBRRBBB has 3 runs.

Part 2

Write a program that calculates the expected number of runs in a deck of XX cards with YY colors.

解析 
import random
from typing import Callable

random.seed(42)

get_color: Callable[[int], int] = lambda x: random.randrange(1, x+1, 1)

def num_of_runs(cards: int, colors: int) -> int:
    """
    Finds the expected number of runs for a deck of X cards with K colors
    """
    runs, prev_color = 1, get_color(colors)

    for _ in range(1, cards+1):
        new_color = get_color(colors)
        runs = runs + 1 if prev_color != new_color else runs
        prev_color = new_color

    return runs

def simulate(iterations: int, cards: int, colors: int) -> float:
    """
    Simulate N iterations of the function num_of_runs to find expected value
    """
    return sum([num_of_runs(cards, colors) for _ in range(iterations)]) / iterations

print(simulate(1000, 52, 2))