Suppose you have a deck of $y$ cards. First, randomly select $y-x$ distinct cards and sign the face of each, then shuffle all the cards back in to the deck. Proceed as follows:

Draw a card. If it is already signed, replace the card and shuffle the deck. If it is not yet signed, sign it, then replace the card and shuffle the deck. My question is what is the probability that you will draw an unsigned card as a function of time? For instance, when $t=1$, the probability is $x/y$. When $t=2$, the probability is $\frac{x(x-1)}{y^2}+\frac{(y-x)(x)}{y^2}$ and so on. I have written a Python program that will compute the probabilities for small values of $t$, but the run time is $O(2^t)$ and was wondering if there is a simpler way to solve this problem

My solution:

The number of summands for time $t$ is $2^{t-1}$, and each is of the form $\frac{a_1a_2\dots a_t}{y^t}$. The set of $t$-tuples $a_1a_2\dots a_t$ appearing in the sum can be put in bijection with the set of odd binary strings of length $t$ as follows: If the $i$-th digit of the string is 1, then $a_i$ is $x$ minus the sum of the previous digits of the string; otherwise, $a_i$ is equal to $y-x$ plus the sum of the previous digits. For instance, $1101$ corresponds with $x(x-1)(y-x+2)(x-2)$ and $1011$ corresponds with $x(y-x+1)(x-1)(x-2)$. It is pretty simple to write an algorithm that will loop over all such binary strings to find the probability.

  • $\begingroup$ Create a floating point array of $y$ entries, initialized to 0 except for the $y-x$th entry which is $1$. Then you can update the $y$ entries of the array $t$ times for an algorithm that runs in $\mathrm{O}(ty)$ time. $\endgroup$ – NovaDenizen Jun 26 '14 at 1:13

From the description of the problem, we can set up the following recurrence:

\begin{align*} p(n,x) &= \left(1-\frac{x}{y}\right)p(n-1,x)+\frac{x}{y}q(n-1,x-1) \\ q(n,x) &= \left(1-\frac{x}{y}\right)p(n-1,x)+\frac{x}{y}q(n-1,x-1) \\ p(0,x) &= 0 \\ q(0,x) &= 1 \\ p(n,0) &= q(n,0) = 0 \end{align*}

and the required answer is $p(n,x)$ where $x$ is the number of unsigned cards. The functions $p$ and $q$ are to know whether the last pick is a signed card or not.

$p(2,x)$ matches with your answer.

Expanding and simplifying the recurrence gives

\begin{align*} p(n,x) &= \frac{x}{y}\left(\frac{y-1}{y}\right)^{n-1} \end{align*}

  • 1
    $\begingroup$ Once I saw that you used recursion, I came up with the following: $$p(n,x)=\left(1-\frac{x}{y}\right)p(n-1,x)+\frac{x}{y}p(n-1,x-1)$$ with initial conditions $p(1,x)=x/y$ and $p(n,0)=0$ and got the same solution. Could you clarify your choices for the recurrence? $\endgroup$ – ngenisis Jun 26 '14 at 17:09
  • $\begingroup$ It may simplify to your initial conditions. May be I did some mistake when trying with a single function and got wrong values, so I made it more explicit. Good job! $\endgroup$ – gar Jun 26 '14 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.