Alice in Wonderland -- Red Queen at the Mad Hatter’s house

Probability Level 3

This problem is inspired by the traditional coupon-collector-problem .

Because of the last experience , Red Queen was pissed off because she has no patience to check all of the teapots. This time, she decides to visit the Mad Hatter's house and cut off their heads. (Mad Hatter has run away)

Red Queen knows that there are 20 different kinds of girls with different traits available in the Mad Hatter's house. Assuming that the number of each kind of girl is sufficient so that cutting off their heads doesn't affect the probability of their appearance.

Red Queen surveys that, the probability of appearance of each kind of girl is (from lowest to highest):

{0.002, 0.004, 0.01, 0.016, 0.018, 0.02, 0.02, 0.031, 0.035, 0.038, 0.042, 0.042, 0.049, 0.052, 0.058, 0.069, 0.077, 0.078, 0.093, 0.099}.

Every time Red Queen visits the Mad Hatter's house, there is only one kind of girl available and maybe no one is available. If so, Red Queen will immediately cut her head and put it in her palace.

Notice that the sum of all the probabilities is 0.853, meaning that there is a probability of 0.147 that no one is available . For other cases, we choose one kind of girl available weighted by the probability of appearance .

Red Queen wants to cut off every 20 kinds of the girl's head and display each kind of them in her palace. As long as all kinds of heads are collected, the process is finished. Let $X$ be the total times of visits to the Mad Hatter's house in order to do that.

Find $E(X)$ .

Notes :

The numbers are generated randomly. So you'd better generalize the algorithm without loss of generality first and plug in the numbers later, instead of trying to find specific values.
You may make a program to implement the algorithm and calculate the answer.

The answer is 595.45168.

1 solution

Alice Smith
Jul 24, 2019

Let $f[x]$ denote that under the condition that certain kinds of head are collected, the expected value of the total visits in order to collect all kinds of heads.

Where $x$ is a binary number, each bit denotes that whether the corresponding kind of head is collected.

For instance, when $x=(00001000010000100001)_{2}$ , it means that the 1st, 6th, 11th, 16th kind of head is collected.

It is easy to show that $f[(1<<N)-1]=0$ , where $N$ is the number of kinds of heads.

Considering the recurrence equation:

${f[x]=p_{not \ getting \ the \ head}·f[x]+p_{getting \ the \ collected \ head}·f[x]+(∑_{where \ the \ state \ has \ no \ ith \ head} \ p_{i}·f[x|(1<<(i-1))])+1}$

( $1<<x$ denotes shifting the bit $x$ times to the left , $|$ denotes the bitor operation)

Since

${1-p_{not \ getting \ the \ head}-p_{getting \ the \ collected \ head}=p_{getting \ the \ uncollected \ head}}$ ,

Rearrange the terms gives us the final recurrence equation:

$\displaystyle{f[x]=\dfrac{(∑_{where \ the \ state \ has \ no \ ith \ head} \ p_{i}·f[x|(1<<(i-1))])+1}{p_{getting \ the \ uncollected \ head}}}$

And finally we need to find $f[0]$ .

This is the program that I used to calculate the answer:

#include<stdio.h>
int N,En;
double f[1048576+233],p[25];
int main()
{
    int i,j;
    double P,sum;

    scanf("%d",&N);
    for(i=1;i<=N;i++)scanf("%lf",&p[i]);

    En=(1<<N)-1;
    for(i=En-1;i>=0;i--)
    {
        sum=P=0;
        for(j=1;j<=N;j++)if(!(i&(1<<j-1)))sum+=p[j]*f[i|(1<<j-1)],P+=p[j];
        f[i]=(sum+1)/P;
    }

    printf("%.6lf",f[0]);
}

Plugging in the values gives us $\boxed{595.451680}$

Alice in Wonderland -- Red Queen at the Mad Hatter’s house

The answer is 595.45168.

1 solution

0 pending reports