Conditional probability, balls, urns and a coin We are given $2010$ numbered balls and $2$ urns.
Firstly, we throw a symmetric coin $2010$ times.
If at the $i-$th throw we get heads, we place the $i$-th ball in the first urn.
If we get tails, we place it in the second urn.
Then we randomly pick a number $1 - 2010$ (in such a way that choosing each of the numbers is equally probable) and we place the ball with this number in the other urn. That is, if at the first stage the $i$-th ball was in the first urn and we have now picked number $i$, we take the out and place it in the second urn.
For what $k \in \{0, ..., 2010\}$ is the probability that before the transfer there are $k$ balls in the first urn bigger than after the transfer?
Could you explain to me, more or less step-by-step, how to deal with such problems?
Thank you!
 A: Well, since the placement process is precisely equivalent to that of choosing a uniform number $i$ from 1 to 2010, then placing all balls other than $i$ into urn A on heads and urn B on tails, but placing ball $i$ into urn A on tails and urn B on heads.  Since the probabilities of heads and tails are equal, we could notice that the before and after probabilities are equal for any $k$.  So the answer is, no values of $k$ give you higher after probability.
But let's say you didn't notice this semi-clever way of looking at it, and wanted to tackle the problem head-on.
For this sort of problem I always start by looking at an extreme case, to see if it gives me some insight.  Take $k = 0$ -- is the probability of $0$ balls in urn A before the transfer bigger or smaller than after the transfer?  Well, we know how to get $0$ balls before the transfer ( $P = 2^{-N} \binom{N}{0} = 2^{-2010})$; and to get $0$ balls after the transfer there needed to be $1$ ball before the transfer and we needed to get lucky, moving that ball out instead of one of the 2009 balls in ($P = 2^{-N} \binom{N}{1} \frac{1}{N} = 2^{-N} \frac{N}{N}$. 
So we see that for $k=0$ the probabilities are equal, but more importantly, we see how to express the "after" probability.  the next step is to generalize that:
$$
\begin{array}{c}
P_{\mbox{before}}(k) = 2^{-N} \binom{N}{k} \\
P_{\mbox{after}}(k) = P_{\mbox{before}}(k-1)\frac{N-(k-1)}{N} + P_{\mbox{before}}(k+1)\frac{k+1}{N} \\
P_{\mbox{after}}(k) = 2^{-N} \left[ \binom{N}{k-1} \frac{N-k+1}{N} 
+ \binom{N}{k+1} \frac{k+1}{N}
\right]
\end{array}
$$
The third step is to do the math for the comparison.  Taking out the common factor $2^{-n}$ we see that the after probability is greater if 
$$
\binom{N}{k-1} \frac{N-k+1)}{N} + \binom{N}{k+1} \frac{k+1)}{N} > \binom{N}{k}
$$
And we can factor out $\binom{N}{k}$ because it is easy to write the neighboring binomial coefficients in terms of $\binom{N}{k}$ (for example, $\binom{N}{k-1} = \frac{k}{N-k+1} \binom{N}{k}$ and $\binom{N}{k+1} = \frac{N-k}{k+1} \binom{N}{k}$ ). The condition becomes
$$
\frac{k}{N-k+1} \frac{N-k+1}{N} + \frac{N-k}{k+1} \frac{k+1}{N} >1
$$
which simplifies to $ 1 > 1$.  So the probability after is always, for any $k$, equal to the probability before.
