Probability involving Binomial Summation

Question

The problem statement is :

$A$ has $n$ coins and $B$ has $n+1$ coins. They toss their coins simultaneously.

If $p$ be the probability that $B$ will have more heads than $A$ the find $p=?$

One way I did this is by this argument :

Since $B$ cannot have the number of heads and tails both greater than $A$.

But since one of those cases is always true. (either more heads($p$) or more tails(=$q$ (let))

So by symmetry both should have equal probabilities. Since $p+q=1$.

Then $p=0.5$

One more way of doing it is by binomial summation i.e. Lets say $A$ has $x$ heads and $B$ has $y$ heads then we add up The product $$ \binom{n}{x} *  \binom{n+1}{y} $$for all $y>x$.

But I am not able to evaluate that...

So how to do I go about summing this?

Answer 1

The following answer is based upon induction on $n$.

We show the following is valid \begin{align*} \sum_{x=0}^{n}\binom{n}{x}\sum_{y=x+1}^{n+1}\binom{n+1}{y+1}=4^n\qquad\qquad n\geq 1\tag{1} \end{align*}

$$ $$

Base step: $n=1$

\begin{align*} \sum_{x=0}^{1}\binom{1}{x}\sum_{y=x+1}^{2}\binom{2}{y+1}&=\binom{1}{0}\left[\binom{2}{1}+\binom{2}{2}\right]+\binom{1}{1}\binom{2}{2}\\ &=1(2+1)+1\\ &=4 \end{align*}

Let's assume the claim (1) is valid for $n$ (induction hypothesis).

Inductive step: $n \rightarrow n+1$ \begin{align*} \sum_{x=0}^{n+1}&\binom{n+1}{x}\sum_{y=x+1}^{n+2}\binom{n+2}{y} =\binom{n+1}{0}\sum_{y=1}^{n+2}\binom{n+2}{y}\\ &+\sum_{x=1}^{n+1}\left[\binom{n}{x}+\binom{n}{x-1}\right] \sum_{y=x+1}^{n+2}\left[\binom{n+1}{y}+\binom{n+1}{y-1}\right]\tag{2}\\ &=1\left(2^{n+2}-1\right)+\sum_{x=1}^{n+1}\binom{n}{x}\sum_{y=x+1}^{n+2}\binom{n+1}{y} +\sum_{x=1}^{n+1}\binom{n}{x-1}\sum_{y=x+1}^{n+2}\binom{n+1}{y}\\ &\qquad\qquad\qquad\quad+\sum_{x=1}^{n+1}\binom{n}{x}\sum_{y=x+1}^{n+2}\binom{n+1}{y-1} +\sum_{x=1}^{n+1}\binom{n}{x-1}\sum_{y=x+1}^{n+2}\binom{n+1}{y-1}\tag{3}\\ &=2^{n+2}-1+\sum_{x=1}^{n+1}\binom{n}{x}\sum_{y=x+1}^{n+2}\binom{n+1}{y} +\sum_{x=0}^{n}\binom{n}{x}\sum_{y=x+2}^{n+2}\binom{n+1}{y}\\ &\qquad\qquad\qquad\quad+\sum_{x=1}^{n+1}\binom{n}{x}\sum_{y=x}^{n+1}\binom{n+1}{y} +\sum_{x=0}^{n}\binom{n}{x}\sum_{y=x+1}^{n+1}\binom{n+1}{y}\tag{4}\\ &=2^{n+2}-1+\sum_{x=1}^{n}\binom{n}{x}\sum_{y=x+1}^{n+1}\binom{n+1}{y} +\sum_{x=0}^{n}\binom{n}{x}\sum_{y=x+2}^{n+1}\binom{n+1}{y}\\ &\qquad\qquad\qquad\quad+\sum_{x=1}^{n}\binom{n}{x}\sum_{y=x}^{n+1}\binom{n+1}{y} +\sum_{x=0}^{n}\binom{n}{x}\sum_{y=x+1}^{n+1}\binom{n+1}{y}\tag{5}\\ &=2^{n+2}-1+\left[4^n-\binom{n}{0}\sum_{y=1}^{n+1}\binom{n+1}{y}\right] +\left[4^n-\sum_{x=0}^n\binom{n}{x}\binom{n+1}{x+1}\right]\\ &\qquad\qquad\qquad\quad+\left[4^n-\binom{n}{0}\sum_{y=1}^{n+1}\binom{n+1}{y}+\sum_{x=1}^n\binom{n}{x}\binom{n+1}{x}\right]+4^n\tag{6}\\ &=2^{n+2}-1+\left[4^n-2^{n+1}+1\right] +\left[4^n-\sum_{x=0}^n\binom{n}{x}\binom{n+1}{x+1}\right]\\ &\qquad\qquad\qquad\quad+\left[4^n-2^{n+1}+1+\sum_{x=0}^n\binom{n}{x}\binom{n+1}{x}-1\right]+4^n\tag{7}\\ &=4^{n+1}+\sum_{x=0}^{n}\binom{n}{x}\left[\binom{n+1}{x}-\binom{n+1}{x+1}\right]\tag{8}\\ &=4^{n+1} \end{align*} and the claim (1) follows.

Comment:

• In (2) we separate the first summand with $x=0$ from the double sum and use $\sum_{k=0}^n\binom{n}{k}=2^n$. We also apply $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$ on both factors of the double sum.

• In (3) we multiply the factors of the double sum and obtain four parts.

• In (4) we rearrange three of the four double sums to get equal factors $\binom{n}{x}$ and $\binom{n+1}{y}$. To do so we shift the index $x$ by $1$ resp. the index $y$ by $1$. In the rightmost double sum we shift both indices.

• In (5) we note that $\binom{n}{k}=0$ if $k>n$ and set upper limits e.g. from $n+1$ to $n$ accordingly.

• In (6) we use the induction hypothesis on each of the four double sums and add/subtract corrective terms.

• In (7) we do some further simplifications.

• In (8) we use the identity $\sum_{x=0}^na_x=\frac{1}{2}\sum_{x=0}^na_x+\frac{1}{2}\sum_{x=0}^na_{n-x}$ and obtain \begin{align*} \sum_{x=0}^{n}&\binom{n}{x}\left[\binom{n+1}{x}-\binom{n+1}{x+1}\right]\\ &=\frac{1}{2}\sum_{x=0}^{n}\binom{n}{x}\left[\binom{n+1}{x}-\binom{n+1}{x+1}\right]\\ &\qquad+\frac{1}{2}\sum_{x=0}^{n}\binom{n}{n-x}\left[\binom{n+1}{n-x}-\binom{n+1}{n-x+1}\right]\\ &=\frac{1}{2}\sum_{x=0}^{n}\binom{n}{x}\left[\binom{n+1}{x}-\binom{n+1}{x+1}\right]\\ &\qquad+\frac{1}{2}\sum_{x=0}^{n}\binom{n}{x}\left[\binom{n+1}{x+1}-\binom{n+1}{x}\right]\\ &=0 \end{align*}

Answer 2

Instead of introducing two variables, let us just use $y$ to represent the number of heads Person $B$ gets. We wish to calculate the combinations such that Person $A$ gets less than $y$ heads, and sum these from $y = 1$ to $y = n + 1.$ This can be written as $$\sum_{y = 1}^{n + 1}\sum_{k = 0}^{y - 1}\dbinom{n + 1}{y}\dbinom{n}{k}.$$

Notice that this is an extremely unwieldy count. Instead of counting that way, we can take advantage of that symmetry you noticed. In fact, this situation can be addressed with what is known as a $1-1$ correspondence. Say Person $A$ flips $x$ heads and Person $B$ gets $y > x$ heads. Then to make Person $B$ lose, all we have to do is switch all of each person's coins from $T$ to $H$ or from $H$ to $T.$ Since we have proven that the winning and losing counts are the same, the probability must be $\frac{1}{2}.$

Answer 3

$$\sum_{x=0}^n\sum_{y=x+1}^{n+1}{n\choose x}{n+1\choose y}=4^n$$

Answer 4

We have by inspection that the desired probability is

$$\frac{1}{2^{2n+1}} \sum_{k=1}^{n+1} {n+1\choose k} \sum_{m=0}^{k-1} {n\choose m}.$$

Now introducing $${n\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{m+1}} \; dz$$

we obtain for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \frac{1/z^{k}-1}{1/z-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^n \frac{1/z^{k}-1}{1-z} \; dz$$

The second term vanishes and we get

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^k} \frac{1}{1-z} (1+z)^n \; dz$$

which could have been obtained by inspection. Note that this is zero when $k=0$ so we may extend the outer sum to include $k=0$, getting

$$\frac{1}{2^{2n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} (1+z)^n \sum_{k=0}^{n+1} {n+1\choose k} \frac{1}{z^k} \; dz \\ = \frac{1}{2^{2n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} (1+z)^n \left(1+\frac{1}{z}\right)^{n+1} \; dz \\ = \frac{1}{2^{2n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} (1+z)^{2n+1} \; dz.$$

Extracting the residue now yields $$\frac{1}{2^{2n+1}} \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2^{2n+1}} \times \frac{1}{2} 2^{2n+1} = \frac{1}{2}.$$

Answer 5

However, it was not stated that the coins were the same independent or identically distributed, I presume that the question in the textbook specified this:Or that both outcomes were possible on each coin for each person?

Person $B$ might have a deterministic coin which always lands heads, and Person $A$ may have a coin which always lands tails,

As this satisfies the hypothesis that person B cannot both have more heads and more tails then $A$ simultaneously, $p+q=1$ but $p=1 \neq q=0$

Buts its clearly that its not the case that the probability 'that person $B$ has more heads than A'=s $0.5$, rather its $1$

and its not the case that the probability that person $B$ has more tails then $A$ is $0.5$. In this counter-example its $0$. $p+q=1$ is satisfied nonetheless. Perhaps something further was specified in the question.?

So I presume that something else must have been specified. One generally cannot expect a probability distribution to fall out of the calculus alone.

I presume the question was phrased in terms of both outcomes being possible, and based on proportion counts?

But without a measure of some sort being specified its unclear what one deduce. Almost all binary sequences have relative frequency=$0.5$, but that does not mean that this always translates into 'almost surely' and that 'necessarily all two outcome processes have probability =$0.5$'

So long as you specify symmetry requirement further (I presume Rud-in specified the question further?); that presumably needs to be mentioned. Or that the trials are at least independently distributed with both outcomes possible (even if identical distribution is not required, although it presumably is) .