2
$\begingroup$

A random function $rand()$ return a integer between $1$ and $k$ with the probability $\frac{1}{k}$. After $n$ times we obtain a sequence $\{b_i\}_{i=1}^n$, where $1\leq b_i\leq k$. Set $\mathbb{M}=\{b_1\}\cup\{b_2\}\cdots \cup\{b_n\}$. I want to known the probability $\mathbb{M}\neq \{1, 2\cdots, k\}$.

$\endgroup$
  • $\begingroup$ @Arnaud There is any argue in this problem discription? $\mathbb{M}\neq \{1,2,\cdots,k\}$. Because the random function cann't return a integer $>k$. $\endgroup$ – Yuansheng liu Apr 21 '13 at 9:59
  • $\begingroup$ There are two possible questions, depending on whether $n>k$ or $n<k$ is interesting. The question is about the $n>k$ case. $\endgroup$ – Sharkos Apr 21 '13 at 10:10
1
$\begingroup$

The probability that $j$ of the $k$ numbers is excluded is $(1-j/k)^n$ and there are $\binom{k}{j}$ ways to choose those $j$ to be excluded. The inclusion-exclusion principle says that the probability that at least one of the $k$ numbers is excluded is $$ \sum_{j=1}^k(-1)^{j-1}\binom{k}{j}\left(1-\frac{j}{k}\right)^n $$

$\endgroup$
0
$\begingroup$

Principle of inclusion and exclusion? That will do, I think, because probability that you didn't get $j$, $1\leq j \leq k $, $\quad$ is $\quad$ $( \frac{k-1}{k} )^n$ and so on ...

$\endgroup$
  • $\begingroup$ To clarify - as I note in my answer, there isn't a closed form for the resulting sum. You certainly can write a sum down using PIE though. $\endgroup$ – Sharkos Apr 21 '13 at 10:37
0
$\begingroup$

Hint: Obviously $n<k$ is trivial. Thereafter, the question becomes equivalent to solving

What fraction of $n$-tuples with the digits $1,\ldots,k$ are in fact $n$-tuples formed from a strict subset of these numbers?

or a surjection-counting problem.

You can find a recursive solution by letting $p_{n,k}$ be the probability that a set of $n$ digits up to $k$ contains all distinct digits, and then considering the last digit of a sequence leading to $(n+1)$-tuples.

Edit: I should make clear that a recursive 'solution' essentially is the best you can do, which is why I called it that! The numbers don't have a closed form. (See e.g. https://mathoverflow.net/questions/27071/counting-sequences-a-recurrence-relation for a discussion, once you've worked out the recursive form yourself.)

$\endgroup$
  • $\begingroup$ Tks very much. I will complete it. $\endgroup$ – Yuansheng liu Apr 21 '13 at 11:09

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.