Taking two passes at sampling from urns: probability of repetition My urn is filled with balls of K different colors. I draw N samples with replacement, and note the sampled colors.
I now draw another N samples with replacement (from the same urn). What is the probability that my second sample repeats any color from the first sample?
You can assume that N>1, and that N is much smaller than K. We know the number of balls of each color in the urn.
I'm lost trying to solve this puzzle, any pointers would be much appreciated.
I've tried it brute-force, but I'm tripping over the various interdependencies. For example, I can't just sum up the probability that a color is drawn in the first pass (sampling of N), and sum up the probabilities that a color is also drawn in the second pass.
I'd be happy with pointers to additional reading, solution approaches, and ideas for upper bounds on the probability.
 A: The basic approach is to calculate the probability P that each draw from the second trial set is a different color from any of the balls in the first trial set.  Since you are replacing the balls, and the drawings are independent, then $P=P_0^N$, where $P_0$= the probability that one draw will not give a matching color.  To get $P_0$ you need to know which colors (repeats don't matter) have been chosen the first trial, and how many of each of these ($m_i$) are in the collection as well as the total (M) in the collection.  $P_0=1-\frac{\sum_i m_i}{M}$, where the summation is over all the balls which appeared in the first trial.  Your final answer is 1-P.
A: Allow me to replace your $K$ with $m$ and $N$ with $n$, in order to use $k$ as an index and keep the notation in following answer more clean.  
Since the extractions are with replacement,  the probability of each color to be extracted remains constant
along the extraction sequence.
The correct representation is that of a sequence of events, characterized by random variable $X$, which can assume values in
the set $\{1,\, 2,\, \cdots,\,m\}$ with corresponding probabilities $ p_1,\, p_2,\, \cdots,\, p_m$.
The interpretation of  " .. second sample repeats  any color of the first ..", can take two different meanings:
 a) the second sample contains some (at least one) color in common with the first, indipendently of their position in the sequence ;
 b) the second sample contains some (at least one) matchings with the first, where color and position coincide.   
The case a) can also be restated as:
 - Prob. of finding a couple of words, of length $n$, with characters  from alphabet $\{1,\cdots ,m\}$, picked with probability $\{ p_1, \cdots, p_m\}$, having at least one character in common;
 - Randomly throwing $n$ white and $n$ black balls into $m$ bins, having prob. to be hit of  $\{ p_1, \cdots, p_m\}$, the Prob. of having  any bin with mixed colors;   
and case b) as
 - Prob. of finding a couple of words, of length $n$, with characters  from alphabet $\{1,\cdots ,m\}$, picked with probability $\{ p_1, \cdots, p_m\}$, having some coincident character (same character in same position);
 - Prob. of having a twin result, upon launching $n$ times a couple of $m$-faced identically biased dice, each face having prob. $\{ p_1, \cdots, p_m\}$ to appear.   
The problem is very interesting so I will attempt and concisely delineate the approach in both cases.
In the following I will use the "words" scheme (which seems to me better to handle) and  of course focus on the complementary probability of not having ..
1) Premise
Consider the homogeneous polynomial in $m$ variables
$$
p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m}  = 1
$$
When you multiply that polynomial $n$ times by itself you get
$$ \bbox[lightyellow] {  
\eqalign{
  & 1 = \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)^{\,n}  =   \cr 
  &  = \sum\limits_{\left( {t_{\,1} ,\, \cdots ,\,t_{\,n} } \right)\, \in \;{}_{n\,}T_{\,m} } {\;\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,t_{\,l} } } }  =   \cr 
  &  = \sum\limits_{\left( {k_{\,1} ,\, \cdots ,\,k_{\,m} } \right)\, \in \;{}_{m\,}W_{\,0,\,n} }
  {\left( \matrix{ n \cr  \,k_{\,1} ,k_{\,2} , \cdots ,k_{\,m} \, \cr}  \right)p_{\,1} ^{k_{\,1} } p_{\,2} ^{k_{\,2} }  \cdots p_{\,m} ^{k_{\,m} } }  \cr} 
} \tag{1}$$
where:
 - each product (monomial of degree $n$) inside the sum in the second line represents a  different possible sequence;
 - ${}_{n\,}T_{\,m} $ represents the set of all n-tuples with components in $\{1,2,\cdots ,m\}$, i.e.
the words of length $n$ from the alphabet $\{1,2,\cdots ,m\}$, i.e. 
the integer points in the n-D cube with edges on the segment $[1,\cdots,m]$;
 - ${}_{m\,\,}W_{\,0,\,n} $ represents the set of all m-tuples with components in $\{0,1,\cdots ,n\}$ summing to $n$, i.e.
the set of all  weak compositions of $n$ into $m$ parts;
 - each summand in the third line gives the probability of finding (in any order) $k_1$ characters $1$, .., $k_m$ characters $m$;
 - the multinomial gives the number of ways of disposing $k_1+k_2+\cdots+k_m=n$ copies of the $m$ characters.
2) General solution
In the interpretation a) it means that, among all the monomials resulting from  the expansion of
$$
\eqalign{
  & 1 = \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)^{\,2\,n}  =   \cr 
  &  = \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)^{\,\,n} \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)^{\,\,n}  \cr} 
$$
to get the probability $Q_a(m,n)$ of not having common characters,
we shall account only for those which are obtained by different indices of $p$ between the first and the second block.
So, if from the left block we take a n-tuple with indices in a subset $A$ of $\{1,\cdots , m\}$, then from the right block
we shall take a n-tuple with indices in the complement of $A$, indicated by $\overline A $.
However, if the indices of both n-tuples do not "fully cover" the respective set, we will have a overcounting when summing up the 
two contributes, and on the contrary an undercounting if both  cover  fully the respective set.
So, indicating with:
 - ${}_{n\,}T_{\,A}$ , the set of n-tuples with components in any subset of the set $A$;
 - ${}_{n\,}R_{\,A}$ , the set of n-tuples with at least one component for each element in the set $A$.
we have 
$$ \bbox[lightyellow] {  
Q_{\,a} (m,n) = \sum\limits_{A\,\, \subset \,\,\left\{ {1,2, \cdots ,m} \right\}} {\;\left( {\sum\limits_{\left( {t_{\,1} ,\, \cdots ,\,t_{\,n} } \right)\, \in \;{}_{n\,}R_{\,A} } {\;\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,t_{\,l} } } } } \right)\left( {\sum\limits_{\left( {s_{\,1} ,\, \cdots ,\,s_{\,n} } \right)\, \in \;{}_{n\,}T_{\,\,\overline A \,} } {\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,s_{\,l} } } } } \right)} 
} \tag{2.a}$$
and the formulation with multinomial descending from that.
In the interpretation b) instead, we will have that among all the monomials resulting from  the expansion of
$$
\eqalign{
  & 1 = \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)^{\,2\,n}  =   \cr 
  &  = \left( {\left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)\left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)} \right)^{\,\,n}  =   \cr 
  &  = \left( {\sum\limits_{1\, \le \,k\, \le \,m} {p_{\,k} } \left( {p_{\,1}  + p_{\,2}  +  \cdots  + p_{\,m} } \right)} \right)^{\,\,n}  \cr} 
$$
in the bracket following $p_k$ we shall count only the indices different from $k$, which means that their sum
is just $1-p_k$. So we get the much simpler expression
$$ \bbox[lightyellow] {  
Q_{\,a} (m,n) = \sum\limits_{A\,\, \subset \,\,\left\{ {1,2, \cdots ,m} \right\}} {\;\left( {\sum\limits_{\left( {t_{\,1} ,\, \cdots ,\,t_{\,n} } \right)\, \in \;{}_{n\,}R_{\,A} } {\;\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,t_{\,l} } } } } \right)\left( {\sum\limits_{\left( {s_{\,1} ,\, \cdots ,\,s_{\,n} } \right)\, \in \;{}_{n\,}T_{\,\,\overline A \,} } {\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,s_{\,l} } } } } \right)} 
} \tag{2.a}$$
And for general values of the probabilities involved we cannot go much further than that.
3) Equal probabilities
When the probabilities are all equal, $p_1=p_2= \cdots =p_m=1/m$, then of course the formulas above simplify a lot.
So
$$
\eqalign{
  & Q_{\,a} (m,n) = {1 \over {m^{\,2n} }}\sum\limits_{A\,\, \subset \,\,\left\{ {1,2, \cdots ,m} \right\}} {\;\left( {\sum\limits_{\left( {t_{\,1} ,\, \cdots ,\,t_{\,n} } \right)\, \in \;{}_{n\,}R_{\,A} } {\;1} } \right)\left( {\sum\limits_{\left( {s_{\,1} ,\, \cdots ,\,s_{\,n} } \right)\, \in \;{}_{n\,}T_{\,\,\overline A \,} } 1 } \right)}  =   \cr 
  &  = {1 \over {m^{\,2n} }}\sum\limits_{A\,\, \subset \,\,\left\{ {1,2, \cdots ,m} \right\}} {\;\left( {\left| {{}_{n\,}R_{\,A} } \right|\;\left| {{}_{n\,}T_{\,\,\overline A \,} } \right|} \right)}  \cr} 
$$
Now, clearly we have that
$$
\left| {{}_{n\,}T_{\,\,\overline A \,} } \right| = \left| {{}_{n\,}T_{\,\left| {\,\overline {A\,} \,} \right|\,} } \right|
 = \,\,\left| {\,\overline {A\,} \,} \right|^{\,n}  = \,\left( {\,m - \left| {\,A\,} \right|} \right)^{\,n} 
$$
while for $\left| {{}_{n\,}R_{\,A} } \right|$ it is not difficult to find that it obeys the following recurrence relation 
$$
\left\{ \matrix{
  \left| {{}_{n\,}R_{\,A} } \right| = \left| {{}_{n\,}R_{\,\left| A \right|} } \right| = \left| A \right|\left( {\left| {{}_{n - 1\,}R_{\,\left| A \right|} } \right| 
 + \left| {{}_{n - 1\,}R_{\,\left| A \right| - 1} } \right|} \right) \hfill \cr   \left| {{}_{n\,}R_{\,1} } \right|
 = 1\quad \left| {\,1 \le n} \right. \hfill \cr}  \right.\quad  \Rightarrow \quad \left| {{}_{n\,}R_{\,\left| A \right|} } \right|
  = \left| A \right|!\left\{ \matrix{ n \hfill \cr  \left| A \right| \hfill \cr}  \right\}
$$
and thus is equal to the Stirling number of the 2nd kind multiplied by the factorial of the lower parameter. 
The number of  subsets of cardinality $k$ of the set $\{1,2,\cdots,m\}$ is known to be $\binom{m}{k}$, thus
$$ \bbox[lightyellow] {  
Q_{\,a} (m,n) = \sum\limits_{A\,\, \subset \,\,\left\{ {1,2, \cdots ,m} \right\}} {\;\left( {\sum\limits_{\left( {t_{\,1} ,\, \cdots ,\,t_{\,n} } \right)\, \in \;{}_{n\,}R_{\,A} } {\;\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,t_{\,l} } } } } \right)\left( {\sum\limits_{\left( {s_{\,1} ,\, \cdots ,\,s_{\,n} } \right)\, \in \;{}_{n\,}T_{\,\,\overline A \,} } {\prod\limits_{1\, \le \,l\, \le \,n} {p_{\,s_{\,l} } } } } \right)} 
} \tag{2.a}$$
And for interpretation b) we simply get
$$ \bbox[lightyellow] {  
\eqalign{
  & Q_{\,b} (m,n) = \left( {1 - \sum\limits_{1\, \le \,k\, \le \,m} {p_{\,k} ^{\,2} } } \right)^{\,\,n}
  = \left( {1 - \sum\limits_{1\, \le \,k\, \le \,m} {{1 \over {m^{\,2} }}} } \right)^{\,\,n}  =   \cr 
  &  = \left( {{{m - 1} \over m}} \right)^{\,\,n}  = {{\left( {m\left( {m - 1} \right)} \right)^{\,\,n} } \over {m^{\,\,2n} }} \cr} 
} \tag{3.b}$$
