1
$\begingroup$

Full disclosure: I am a computer science student, so I am not exactly a math academic, but I started to think about this question yesterday and since I am stuck I can't think of a better place to go for help to.

The problem is as follows:

We start with some set $A$ which has $n$-elements. Then we consider a set $B$ - of all $n$-length permutations of $A$. Then we draw $x$ samples from the set $A$ (with replacement!). Then we consider only first $y$-elements of every sample we have drawn. What is the probability that in the sum of all our $y$-length samples there are all elements of the initial set $A$?

Example: $A = \{a,b,c\}, x = 3, y = 2, B = \{abc,acb,bca,bac,cab,cba\}$. Now we draw $3$ times from $B$. Let's say I got $abc, bca, acb$. I look at first two elements $(ab,bc,ac)$ and this time I got every element of $A$. But of course, I easily could not.

What would be the general formula $f(n,x,y)$ for calculating this probability?

I can't wrap my head around counting all satisfying combinations within $n^x$ space...

I sincerely hope this will not be considered as spam ;)

$\endgroup$

migrated from mathoverflow.net Oct 18 '16 at 17:00

This question came from our site for professional mathematicians.

0
$\begingroup$

I'd consider this an inclusion/exclusion question- we want to find the probability that our set of first $y$ elements is missing some element, then the chance that it is missing two elements and so on. Say, for example, that our set of first $2$ elements is missing $a$. Each of the permutations we pick then must start with either $bc$ or $cb$. There is one permutation starting with $bc$ (namely $bca$) and one starting with $cb$ (namely $cba$). So everytime we pick something from $B$, it must be one of those $2$. $|B|=6$ ($B$ has $6$ elements, if you're not familiar with the notation), so there is a $1/3$ chance we pick one of those permutations. Since $x=3$, we must do this $3$ times, so there is a $1/27$ chance that our set of first $2$ elements does not contain $a$. This same process holds for $b$ and $c$, so for each element, there is a $1/27$ chance of not getting it.

Now, in most cases of inclusion exclusion, we would need to subtract the probability of missing elements $a$ and $b$, since the two could overlap, and the same for every other two element combination, then add back the probability of missing all $3$. However, it is impossible in this case to miss more than one element, since the first two elements of a permutation are always different. So $3/27=1/9$ is the probability of not getting every element in this case, so you have an $8/9$ chance to get every element.

In general, let $f(n,x,y)$ denote the number of ways to not have every element with $n,x,y$ as before. If we're missing $i$ different elements, then the number of permutations we can choose from is ${n-i\choose y}y!(n-y)!$. This is because there are $n-i$ elements we can use for the first $y$ elements, $y!$ ways to organize them (note that we can simplify this to the number of permutations of $y$ elements chosen from $n-i$ elements, or $(n-i)_{y}$, called $n-i$ falling factorial $y$. We then must organize the remaining $n-y$ elements, which can be done $(n-y)!$ ways. Then, we must pick one of these ${n-i\choose y}y!(n-y)!$ permutations $x$ times, so the number of ways of doing that is found by its $x$-th power.

Then $f(n,x,y)=\sum_{i=1}^{n} (-1)^{i-1}{n\choose i}({n-i \choose y}y!(n-y)!)^x$. The part about summation and $(-1)^{i-1}$ are just parts of inclusion-exclusion, but the idea is that we could be missing any single element. The number of ways we miss $a$ also includes the number of ways we miss $a$ and $b$. The number of ways we miss $b$ also includes the number of ways we miss $a$ and $b$, so we double count, and we have to subtract it out. However, this leads to more double counting- again, you really need inclusion exclusion to get this. $i$ refers to how many elements we miss, and $n\choose i$ counts how many ways to miss $i$ elements. We can miss any from $1$ to $n$ elements (though the case where $i=n$ can only make sense if $y=0$. When it doesn't "make sense", we'll get $y>n-i$ and ${n\choose n-i}=0$ by the convention that when $k>n$, ${n\choose k}=0$).

To find the probability, we can then just divide this by the total number of ways to pick permutations from $B$, which is $|B|^x$. But $|B|=n!$ so this is $(n!)^x$.

EDIT: You can also say that $f(n,x,y)$ finds the probability by changing the equation to $f(n,x,y)=\sum_{i=1}^{n} (-1)^{i-1}{n\choose i}(\frac{{n-i \choose y}y!(n-y)!}{(n!)})^x$. This is obviously the same as just dividing the whole sum by $(n!)^x$, but you can interpret $(\frac{{n-i \choose y}y!(n-y)!}{n!})^x$ as the probability of picking a word missing $i$ elements.

$\endgroup$
  • $\begingroup$ Whoa! Thank you very much! I still have to go carefully through your answer, but after first read I see one inconsistency that looks like a typo but maybe is not. In the last sentence of fourth paragraph you refer to {y}\choose{n-i} when in your proposed formula it's the other way around... And either way -- wouldn't the convention of x!=0 for x<0 caused a division by zero in calculating the binomial coefficient? $\endgroup$ – tadek Oct 19 '16 at 20:46
  • $\begingroup$ Follow up: I've implemented your formula (taking 1-f(n,x,y) as a probability of finding all elements and ignoring the factorial of negative number by implementing binomial coefficient to return 0 when any of multipliers is negative); run it against my testing function which is a brute force implementation of the problem (it simply generates all possibilities and then counts them, which of course makes it runnable only on small n,x,y) and it works brilliantly! chapeau bas! $\endgroup$ – tadek Oct 19 '16 at 21:42
  • $\begingroup$ @tadek Sure, no problem. And thanks for pointing out those inconsistencies- there's no $y\choose n-i$, only $n-i\choose y$, and you're right about the binomial coefficient. I always get tripped up by the details the convention is just that for $k>n, {n\choose k}=0$ as you said. $\endgroup$ – Kevin Long Oct 19 '16 at 22:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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