Say we have $n$ blue balls numbered as $1,2,3,\dots,n$, and $n$ red balls numbered as $-1,-2,-3,\dots,-n$. In each round of this game, we draw any of these $2n$ balls at random with replacement. If we at any point draw a ball, say number $j$, and have drawn ball $-j$ in a previous round, we lose. What is the probability of surviving for $m$ rounds?
For my own attempts at this, I considered the problem as a sequence of i.i.d. random variables $(X_k)_{k=1}^\infty$, each uniformly distributed on $\{ 1,-1,2,-2,\dots,n,-n\}$. Then for each $k$ put $B_k=\{ -X_1,-X_2,\dots,-X_k\}$. I am trying to find \begin{align*} &P(X_{j+1}\notin B_j\text{ for all }j=1,2,\dots,m-1) \\ &=P(X_2\notin B_1)\prod_{j=2}^{m-1}P(X_{j+1}\notin B_j\mid X_2\notin B_1,X_3\notin B_2,\dots,X_j\notin B_{j-1}). \end{align*} It is clear that $P(X_2\notin B_1)=P(X_2\neq -X_1)=1-(1/2n)$. For the remaining factors, it would be nice to utilize that $$ P(X_{j+1}\in B_j\mid\# B_j=l)=\frac{l}{2n}. $$ If I could only show that $1(X_{j+1}\in B_j)$ and $(1(X_{k+1}\in B_k))_{k=1}^{j-1}$ are independent conditioned on $\# B_j$, which I believe to be the case, then we would have $$ P(X_{j+1}\notin B_j\mid X_2\notin B_1,X_3\notin B_2,\dots,X_j\notin B_{j-1})=\sum_{l=1}^j P(X_{j+1}\notin B_j\mid\# B_j=l)P(\# B_j=l)=\frac{1}{2n}\sum_{l=1}^j lP(\# B_j=l). $$ There is some hope to find $P(\# B_j=l)$, as $(\# B_k)_{k=1}^\infty$ is a Markov chain with fairly simple transition probabilities: $$ P(\# B_{k+1}=l\mid\# B_k=l)=\frac{l}{2n}=1-P(\# B_{k+1}=l+1\mid\# B_k=l). $$ I can see that $X_{j+1}$ is independent of $(1(X_{k+1}\in B_k))_{k=1}^{j-1}$, both unconditionally and conditioned on $\# B_j$, but I can't get the full independence that I need.
Any help would be greatly appreciated.
I’m not sure why you’re taking this hybrid approach – it may be that I don’t understand it properly. I’ll solve the problem in two ways in which I’d approach it, and I hope that will also throw some light on what you’re trying to do.
First, we can get the desired probability by inclusion–exclusion.
We’re only allowed to draw one of the two numbers from each pair. There are $2^n$ ways to pick a number from each pair, and then we have probability $\left(\frac12\right)^m$ to draw only those $n$ numbers.
But that double-counts the cases where we don’t actually draw from some pair. There are $\binom n{n-1}$ ways to choose $n-1$ pairs to draw from and $2^{n-1}$ ways to pick a number from each of them, and then we have probability $\left(\frac{n-1}{2n}\right)^m$ to draw only those $n-1$ numbers.
But if we subtract that probability, we’ve now undercounted the cases where we don’t actually draw from two pairs. Continuing with this inclusion–exclusion yields the probability
$$ \sum_{j=0}^n(-1)^{n-j}2^j\binom nj\left(\frac j{2n}\right)^m $$
to survive $m$ rounds.
Alternatively, we can use a Markov chain. There are $n+2$ different states: One absorbing state where we’ve lost, and $n+1$ transient states in which $k$ with $0\le k\le n$ different numbers have been drawn that don’t include any pairs of additive inverses.
In transient state $k$, the probability to lose is $\frac k{2n}$, the probability to stay in the state $k$ is also $\frac k{2n}$, and the probability to transition to the state $k+1$ is $1-\frac{2k}{2n}$. Thus the transition matrix is given by
$$ \vec p\to\pmatrix{ 0&0&0&0&0&\cdots&0\\ 1&\frac1{2n}&0&0&0&\cdots&0\\ 0&1-\frac2{2n}&\frac2{2n}&0&0&\cdots&0\\ 0&0&1-\frac4{2n}&\frac3{2n}&0&\cdots&0\\ \vdots&\vdots&&\ddots&\ddots\\ 0&0&\cdots&&\frac2{2n}&\frac n{2n}&0\\ 0&\frac1{2n}&\frac2{2n}&\frac3{2n}&\cdots&\frac n{2n}&1 }\vec p\;. $$
Since this is a lower triangular matrix, the eigenvalues are the diagonal elements, $1$ and $\lambda_k=\frac k{2n}$ for $0\le k\le n$. The corresponding eigenvectors are $\vec v_{n+1}=(0,\ldots,0,1)^\top$ for the eigenvalue $1$ and
$$ v_{kj}=\begin{cases} (-1)^{n-j}2^{j-k}\binom{n-k}{n-j}&0\le j\le n \\ -1&j=n+1 \end{cases} $$
for the eigenvalue $\lambda_k$. The initial distribution $\vec p=(1,0,\ldots,0)^\top$ decomposes into these eigenvectors according to
$$ \vec p=\sum_{k=0}^n(-1)^{n-k}2^k\binom nk\vec v_k+\vec v_{n+1}\;, $$
so the probability to survive $m$ rounds is
$$ 1-\left(\sum_{k=0}^n(-1)^{n-k}2^k\binom nk\lambda_k^m\vec v_k+\vec v_{n+1}\right)_{n+1}=\sum_{k=0}^n(-1)^{n-k}2^k\binom nk\left(\frac k{2n}\right)^m\;, $$
in agreement with the result from inclusion–exclusion.