Intereting Posts

Proving and deriving a Gamma function
WolframAlpha says limit exists when it doesn't?
$\frac{1}{e^x-1}$, $\Gamma(s)$, $\zeta(s)$, and $x^{s-1}$
Prove by induction $\frac{n^n}{3^n}<n!<\frac{n^n}{2^n}$
Irreducible in $\mathbb{Z}$
Roots of the incomplete gamma function
A categorical first isomorphism theorem
Finding the Laurent series of $f(z)=\frac{1}{(z-1)^2}+\frac{1}{z-2}$?
If $f(0)=f(1)=f(2)=0$, $\forall x, \exists c, f(x)=\frac{1}{6}x(x-1)(x-2)f'''(c)$
Mapping CDF's to each other
Every minimal normal subgroup of a finite solvable group is elementary abelian
If $\int_0^1 f(x)x^n \ dx=0$ for every $n$, then $f=0$.
Isolated zeros on closure of a domain
Can an ideal in a commutative integral domain be its own square?
Introductory text for calculus of variations

I recently came up with and tried to solve the following problem: **If you are randomly picking integers in the range $[1,30]$ out of a hat without replacement, on average, how many integers will you have to pick until you have picked all of the multiples of $4$?**

There are $7$ multiples of $4$ that can be chosen. I know that the expected value of picks until you pick a multiple of 4 is the smallest value of $n$ such that $1-\displaystyle\prod_{i=0}^{n-1}\dfrac{23-i}{30-i}>0.5$, which is $3$. However, I don’t know how to figure out how many picks are needed until *all* multiples of $4$ have been chosen. Can I please have some assistance?

- How many ways to distribute $k$ indistinguishable balls over $m$ of $n$ distinguishable bins of finite capacity $l$?
- Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem
- Distribute $N$ objects to $K$ boxes such that no box has more than $c$ objects in it
- Probabilistic method Kraft-McMillan inequality
- Simplification of $\binom{50}{0}\binom{50}{1}+\binom{50}{1}\binom{50}{2}+\cdots+\binom{50}{49}\binom{50}{50}$
- Largest set of perpendicular vectors

- What is the distribution of gaps?
- Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$
- How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?
- Shooting bullets
- Number of permutations that strictly contain two consecutive vowels
- What is the probability that the hand will contain the A K Q J 10 of spades.
- Combinatorial identity's algebraic proof without induction.
- The $5n+1$ Problem
- Tricky (extremal?) combinatorics problem
- Probability of 2 Cards being adjacent

To begin, you correctly note that there are seven multiples of four to be chosen.

Let us choose a convenient sample space to work with. In this case, I find it convenient to let the sample space be *all permutations of* $[30]$. We know the samplespace size is $30!$. This is done because we could choose to simply pick more numbers out of the hat until the hat is empty and the probabilities of success in $k$ rounds will remain the same. In addition, each outcome in the sample space is equally likely to occur.

Let us count how many permutations satisfy the following properties for each value of $k$:

- The $k^{th}$ number is a multiple of four
- The remaining six multiples of four all appear before the $k^{th}$ number

To do so,

- Pick the spaces occupied by the multiples of $4$: $\binom{k-1}{6}$ choices.
- Pick the order in which the multiples of four appear: $7!$ choices
- Pick the order in which the rest of the numbers appear: $23!$ choices

Letting $X=\text{number of rounds until all multiples of four are drawn}$, we have $Pr(X=k)=\dfrac{\binom{k-1}{6}7!23!}{30!}$. Note that this formula makes sense even in the situation that $k<7$ since it is impossible to have drawn all multiples of four in that time and the formula gives the probability of occurrence as zero.

Now, we can apply the definition of Expected Value.

$\mathbb{E}[X] = \sum\limits_{k\in \Delta} kPr(X=k)$

which in this case yields

$$\mathbb{E}[X]=\sum\limits_{k=7}^{30} \dfrac{k\binom{k-1}{6}7!23!}{30!}=27.125$$

wolfram calculation

Through similar methods, one could also calculate the estimated time before the *first* occurrence of a multiple of four to be $3.875$ as in @lulu’s comment above.

That answer yields the same result as ours above by recognizing that via interpreting this as selecting occurrences of numbers in our permutation *in reverse order* and an appropriate shifting of indices, that the first occurrence of a multiple of four being $3.875$ *from the end* corresponds exactly with the last occurrence of $27.125$ from the *start*.

Another approach would be to think of a permutation of $\{1, 2, …, 30\}$. We can think of the seven multiples of $4$ as separating runs (some possibly empty) of the $23$ nonmultiples of $4$. Since there are seven separators, there are $8$ runs, with the average run length being $\frac{23}{8}$. Thus the average number of nonmultiples of $4$ after the last (seventh) multiple of $4$ is $\frac{23}{8}=2.875$. Thus the average position of the last multiple of $4$ is position $30-2.875=27.125$.

The probability of getting all multiples of $4$ precisely on draw $k$ is

$$

\frac{\binom{k-1}{6}}{\binom{30}{7}}

$$

Thus, the expected number of draws would be

$$

\begin{align}

\frac1{\binom{30}{7}}\sum_{k=7}^{30}k\binom{k-1}{6}

&=\frac7{\binom{30}{7}}\sum_{k=7}^{30}\binom{k}{7}\\

&=\frac7{\binom{30}{7}}\binom{31}{8}\\

&=\frac{217}{8}\\[9pt]

&=27.125

\end{align}

$$

Colour the $23$ numbers not divisible by $4$ blue, and call them $b_1$ to $b_{23}$. Colour the $7$ multiples of $4$ red. For $i=1$ to $23$, let indicator random variable $X_i$ be defined by $X_i=1$ if there is a red number which is chosen later than $b_i$, and by $X_i=0$ otherwise.

Then the total number $W$ of trials until we get all the red numbers is given by $W=7+\sum_1^{23}X_i$.

By the linearity of expectation,

$$E(W)=7+\sum_1^{23}E(X_i).$$

The probability that $X_i=1$ is $\frac{7}{8}$, for the blue integer $b_i$ is equally likely to be first, second, and so on up to eighth among the $8$ numbers consisting of the red numbers and $b_i$. It follows that

$$E(W)=7+23\cdot\frac{7}{8}.$$

This simplifies to $\frac{217}{8}$.

*Remark:* The indicator random variable technique bypasses finding the distribution of $W$. That distribution is in this case not difficult to find, but the technique can be valuable when the distribution is less accessible.

- Is $\sqrt{2}$ contained in $\mathbb{Q}(\zeta_n)$?
- What is $\limsup\limits_{n\to\infty} \cos (n)$, when $n$ is a natural number?
- Improper integral and hypergeometric function
- Prove $\int_0^{\pi/2} J_0 (\cos x) dx=\frac{\pi}{2} \left(J_0 \left(\frac{1}{2} \right)\right)^2$
- What is an Isomorphism: Linear algebra
- Polarization: etymology question
- Tricky contour integral resulting from the integration of $\sin ax / (x^2+b^2)$ over the positive halfline
- Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $
- The Determinant of an Operator Equals the Product of Determinants of its Restrictions
- Particular solution of recurrence equations
- Series RLC Circuit Step Response
- Examples of dense sets in the complex plane
- Partitioning Integers into Equal Sets to Guarantee Arithmetic Progression
- Is there an integral for $\pi^4-\frac{2143}{22}$?
- Constructing a HoTT proof term of 1≠0