Drawing previously undrawn cards from a deck

Question

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.

Answer 1

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*}