This task is a simplified form of the problem of probability of finding a target hash with provision for collisions.

Printer prints $N$ cards with numbers $[1, 100]$. On each iteration there is a $1\%$ chance to print duplicate. While printing duplicates, the $1\%$ chance remains.

The deck is shuffled. What is the $P$ (probabiltiy) to take at least one card from $[1, 10]$ if we pull out $50$ cards?

I thought it might be solved by hypergeometric distribution but the problem is that $\Omega$ (probability space) depends on the duplicate print and seems nonconstant. What $\Omega$ should I form for this task?

Which section of mathematics should I dig into?

  • 1
    $\begingroup$ What does it mean to print a duplicate here? To print something that has already been printed? Does that scale up as the number of unique things that have been printed already go up, or is it always 1% and then there is some selection rule for which duplicate is printed? Or is it always adding a new card to the deck but sometimes it adds two copies of that card? Also, how does it pick which number to attempt to print in the first place? $\endgroup$ – Ian Aug 8 '18 at 15:59
  • $\begingroup$ It means to print a card with the last number. For example if it happens on the card #13, second #13 card will be printed. Note that the probability of printing duplicate always remains, so printer can print $3, 4, 5$ etc #13 cards. Print starts from #1 but it doesn't matter. $\endgroup$ – Yedige Davletgaliyev Aug 8 '18 at 16:20
  • $\begingroup$ So if the last card printed was $n$, then there is a 99% chance to print $n$ and a 1% chance to print $n+1$. Except in the very first step where there is a 100% chance to print $1$. Is that correct? Also, what's the desired thing to compute, the probability that out of 50 cards drawn without replacement, at least one is in $[1,10]$? $\endgroup$ – Ian Aug 8 '18 at 16:51
  • $\begingroup$ Vice versa. If last card printed was $n$, then there is a $1\%$ chance to print $n$ and $99\%$ chance to print $n+1$ ($n$ means card number). At the first step there is $100\%$ chance to print $1$. Yes, at least one is in $[1, 10]$ $\endgroup$ – Yedige Davletgaliyev Aug 8 '18 at 17:03
  • $\begingroup$ Ah yes, my mistake. OK, then what matters is how many cards in the deck are in [1,10]. This is 10 plus the number of duplicates that occur before doing the first print of an 11 card (which is the number of duplicates before printing a 2, plus the number of duplicates before printing a 3, etc.). Conditional on this number being $k$, you have just a hypergeometric distribution. $\endgroup$ – Ian Aug 8 '18 at 17:40

Sample space: $\Omega$ here is the set of all non-decreasing sequences of integers, of finite length, starting at $1 $, ending with $\ldots, 99, 100.$ and incrementing by at most $1 $ at each step.

Probability measure: The probability of a given sequence is $\frac {99^{99}}{100^{N-1}} $ where $ N $ is the length of the sequence. [Proof: each increment comes with probability $\frac{99}{100}$ and there are $99$ of them, and each duplicate comes with probability $\frac{1}{100}$ and there are $N-100$ of them.]

Q: how many sequences of length $N$ contain $n$ elements in the interval $[1,10]$?

  • the number of ways for such a sequence to start is given by the stars and bars formula (there has to be at least one integer of each kind (from $1$ to $10$) and a total of $n$ integers. Answer: $$n-1\choose 9$$
  • the number of ways for such a sequence to end is similarly determined: there has to be at least one integer of each kind (from $11$ to $99$) and a total of $N-n-1$ integers ($100$ is special, there is only one of it). Answer: $$N-n-2\choose 88$$

A: there are ${N-n-2\choose 88}{n-1\choose 9}$such sequences.

Each of them has probability $\frac {99^{99}}{100^{N-1}}$, so $$P(n\text{ elements in }[1,10]\text{ and }N\text{ elements in total})=\frac {99^{99}}{100^{N-1}}{N-n-2\choose 88}{n-1\choose 9}$$

Now given that there are $n$ elements in $[1,10]$ and $N$ elements in total, the probability that a random sample of $50$ cards does not contain any numbers in $[1,10]$ is $$\frac{N-n}{N}\ldots\frac{N-n-49}{N-49}=\frac{{N-n\choose 50}}{{N\choose 50}}$$

So the probability to have at least one card in $[1,10]$ by picking $50$ arbitrarily is $$\sum_{N=100}^{\infty}\sum_{n=10}^{N-90}\frac {99^{99}}{100^{N-1}}{N-n-2\choose 88}{n-1\choose 9}\left[1-\frac{{N-n\choose 50}}{{N\choose 50}}\right]$$

  • $\begingroup$ Am I right that $P(S)=\begin{cases} \sum_{n=0}^\infty P\cdot q^n = \frac{P}{1-q} \\ q = P \end{cases}$ is a probability to get any amount of duplicates is equal a sum of infinitely-decreasing geometric progression, so there is $P(A) = \frac{10\cdot S}{100\cdot S}= 0,1$ probability of favorable output $A$ for 1 try? $\endgroup$ – Yedige Davletgaliyev Aug 8 '18 at 22:39
  • $\begingroup$ @YedigeDavletgaliyev I still don't understand your comment above but I have edited into a full answer. $\endgroup$ – Arnaud Mortier Aug 9 '18 at 14:56
  • $\begingroup$ I was wrong in my reasoning, there is a sum of chains of dependent events and, accordingly, another formula. But this is finally not important because I finally comprehended your solution, although it took time. Thank you! $\endgroup$ – Yedige Davletgaliyev Aug 10 '18 at 23:27
  • $\begingroup$ @Yedige well, you're welcome! $\endgroup$ – Arnaud Mortier Aug 11 '18 at 8:31

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.