A problem on probability theory There are two boxes,one containing $r$ black balls,and the other containing $r$ white balls.
Each time take one ball from each box,exchange them and put in the box.
The problem is: after $n$ times, what's the probability of the balls in one box being the same color?
In my opinion, I think there are two situations: complete exchange or no change(just from the results).
But I don't know how to solve this.
 
 A: I'll just do the first few $n$ and hope I (or someone else) can find a pattern. Assuming $r>1$:
$n=1$: the probability is obviously 0 since the balls have to swap, or if $r=1$, then the probability is 1.
$n=2$: There are $r-1$ of each (original) color ball in each urn. The only way this succeeds is if I pick out the 'wrong' colored ball from each urn, with probability $\frac{1}{r^2}$ since there's a $\frac{1}{r}$ chance for each urn. There is then a $\left(\frac{r-1}{r}\right)^2$ probability that there will be two wrong colored balls in each urn after this step, and a $2\cdot \frac{r-1}{r^2}$ probability that there will only be a single 'wrong' colored ball in each urn.
$n=3$ (and $n$ larger) now you have to condition on the preceding probabilities, which, to be frank, isn't very fun. I'm clearly missing something, but I'm working on this during my lunch break so I can't give it more attention.

Another lunch break, more insights.
As @monoRed declared in the comments, this can be modeled with a Markov chain. I will answer the question assuming the OP has some familiarity with linear algebra and can read through https://en.wikipedia.org/wiki/Markov_chain#Discrete-time_Markov_chain and/or https://en.wikipedia.org/wiki/Examples_of_Markov_chains to come to a minimal understanding.
for $r=2$, the transition matrix is
$M_2=\left[
\begin{matrix} 0 & \frac{1}{4} & 0\\
 1 & \frac{1}{2} & 1\\
0 &\frac{1}{4} & 0
 \end{matrix}
\right]$
We additionally know the starting state, $v=\left[ \begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right]$. Then the probability of the urns having all one color of ball after $n$ moves is simply the sum of the first and last entries of $M_2^n v$.
For example: after 1 move, $M_2 v=\left[\begin{matrix}0 \\ \frac{1}{2} \\ 0 \end{matrix}\right]$ so there is a $0+0=0$ probability, as I said above.
After 2 moves, $M_2^2 v=\left[\begin{matrix}\frac{1}{8} \\ \frac{1}{4} \\ \frac{1}{8} \end{matrix}\right]$ so there is a $\frac{1}{8}+\frac{1}{8}=\frac{1}{4}$ probability of ending after two moves, again in accordance with my answer above.
However, this makes it obscenely easy to calculate for $n>2$ without having to go through a big branching tree, and for larger $r$, it simply boils down to properly constructing the state diagram, which can be done with elementary probability.
A: Don't think of it in terms of boxes. Think of it in terms of the balls.
Each ball has a $1/r$ chance of being picked every "turn", because there's always $r$ balls in each box and you take one from each box. If every ball is picked an even number of times, they all end up back in their original box.
However, also note that if every ball is picked exactly once, they swap (the black balls are in the box formerlly occupied by the white ones, and vice versa), which returns the problem to its original state. What's the net result of this?
If every ball is picked an even number of times, then every ball ended up back in its original box. If every ball is picked an odd number of times, then every ball ended up in the opposite box. In any other case, some balls are in their original box and some are in the opposite box.
If every ball was picked an even number of times, or if every ball was picked an odd number of times, the boxes will each only have one colour of ball. Otherwise, they will not.
I'm still working on the crunchy mathematics side of it, but for now this line of thinking should be helpful (I hope!).
EDIT: One more thing before I go back to brooding: it is impossible for there to be a box full of balls with only even/odd swaps if the other box does not also only have even/odd swaps. This is easy to intuit, as if every ball in the original white box has an even "count", then they must all be white, leaving only black balls in the original black box. Same logic applies for an odd "count".
