Consider a multinomial distribution with three outcomes. Let $x_i$ denote the number of occurences of the $i^{th}$ outcome, and the $i^{th}$ outcome occurs with probability $p_i$, $i=1,2,3$. Let $n$ be the number of total trials. Then we have
$$(X_1,X_2,X_3)\sim Multi(n;p_1,p_2,1-p_1-p_2).$$
I'm trying to find the difference of two probabilities, $P[X_1\geq X_2|n+1]$ and $P[X_1\geq X_2|n]$, i.e., $P[X_1\geq X_2|n+1]-P[X_1\geq X_2|n]$.
Intuitively, if $p_1\geq p_2$, the difference should be positive. On the other hand, if $p_1<p_2$, then it should be negative.
To show this, my approach is as follows.
\begin{align} P[X_1\geq X_2|n+1]=&P[X_1> X_2|n]*1+P[X_1=X_2|n]*(1-p_2)\\ =&P[X_1> X_2|n]+P[X_1=X_2|n]-p_2P[X_1= X_2|n]\\ =&P[X_1\geq X_2|n]-p_2P[X_1= X_2|n].\\ \end{align} In the first line, if $X_1>X_2$ with a sample size $n$, $X_1\geq X_2$ should always holds with one additional sample. However, if $X_1=X_2$ with $n$ samples, $X_1< X_2$ happens with probability $p_2$.
So, I have $$P[X_1\geq X_2|n+1]-P[X_1\geq X_2|n]=-p_2P[X_1= X_2|n]??$$
I can't belive the probability monotonically decreases in the sample size $n$.. Can anyone spot what are my mistakes in the reasoning?
You have missed including the case where after $n$ trials, $X_1=X_2-1$ and with probability $p_1$ after $n+1$ trails $X_1=X_2$.