Suppose we have a lottery where the target consists $k$ ordered numbers each of which is drawn independently with uniformly randomly distribution from natural numbers from $1$ to $k$. When a guessing sequence, an ordered sequence of numbers, is presented, we count the numbers of the guessing sequence that match those of the target sequence. If the total count is no less than $\frac k2$, the guessing sequence wins the lottery. What is the probability of winning?
Let us put the problem in more formal terms.
Let $K=\{1,2,\cdots,k\}$. $s=(a_1,a_2,\cdots,a_k,b_1,b_2,\cdot,b_k)$ is an ordered sequence where each element is drawn i.i.d. from $K,\ \forall i\in K$. Given $s$ and $p\in K$, let $m_p:=|\{a_i|a_i=p,i\in K\}|$ and $n_p:=|\{b_i|b_i=p,i\in K\}|$ where $|\cdot|$ is the cardinality of the set $\cdot$. Of course we have $\sum_{p=1}^k m_p=\sum_{p=1}^k n_p=k$. The winning set is $S:=\big\{s\ \big|\sum_{i=1}^k\min(m_i,n_i)\ge \frac k2\big\}$. What is the probability $P(S)$ of $S$?
It is obvious that
$$P(S)=\frac1{k^{2k}} \sum_{\sum_{i=1}^k\min(m_i,n_i)\ge \frac k2} {k\choose m_1,m_2,\cdots,m_k}{k\choose n_1,n_2,\cdots,n_k}.$$ Is there a simpler form of the summation?
I have a recursion relation I will present below. But it is still not satisfactory in terms of simplicity. Is there a generating function or a simpler representation?
We generalize the problem so that the length of the sequence is $l$. We will construct a recursion on the length of the sequence $l$. We distinguish $2$ cases.
We then need to look at the the set where $\sum_{p=1}^k m_p=\sum_{p=1}^k n_p=l-1$ and $\sum_{i=1}^k\min(m_i,n_i)= w-1\big\}$.
(To be continued)