Interesting variant of binomial distribution.

Question

Suppose i had $n$ Bernoulli trials with $X_{i}=1$ if the $i$th trial is a success and $X_{i}=-1$ if it is a failure each with probability $\frac{1}{2}$.

Then the difference between the number of successes and failures can be represented by the random variable $Y=|\sum_{i=1}^{n} X_{i}|$ what is the best way to calculate $\mathbb{E}(Y)$?

One thing i was thinking is $|\# \mathrm{Successes}-\# \mathrm{Failures}|=n-2\#\mathrm{successes}$ and so $\mathbb{E}(Y)=\mathbb{E}(2|\frac{n}{2}-\#\mathrm{Successes}|)$ which we could relate to the variance of $X=\sum_{i=1}^{n} X_{i}'$? where $X_{i}'$ is an indicator random variable equal to $1$ if $X_{i}$ is a success and $0$ otherwise. Am i along the right lines?

Answer 1

Let $S_{2n}$ be the number of successes in $2n$ trials. Then there are $2n - S_{2n}$ failures, with a difference of $|S_{2n} - (2n - S_{2n})| = |2S_{2n} - 2n|$. Now let $0 <k \leq 2n$ be an even number. Then

\begin{align*} \mathbb{P}(|2S_{2n} - 2n| = k) &= \mathbb{P}(2S_{2n} - 2n = k) + \mathbb{P}(2S_{2n} - 2n = -k) \\ &= \mathbb{P}\left(S_{2n} = n + \frac{k}{2}\right) + \mathbb{P}\left(S_{2n} = n - \frac{k}{2}\right) \\ &= \frac{1}{2^{2n}} \left(\binom{2n}{n + \frac{k}{2}} + \binom{2n}{n - \frac{k}{2}}\right) \\ &= \frac{1}{2^{2n-1}}\binom{2n}{n + \frac{k}{2}}. \end{align*}

If $k$ is odd, then it is easy to check that $\mathbb{P}(|2S_{2n} - 2n| = k) = 0$. We have

\begin{align*} \mathbb{E}(Y_{2n}) &= \sum_{k=2}^{2n}k\,\mathbb{P}(|2S_{2n} - 2n| = k)\\ &= \frac{1}{2^{2n-2}}\sum_{k=1}^n k \, \binom{2n}{n + k} \\ &= \frac{n+1}{2^{2n-1}}\binom{2n}{n+1} \\ &= \frac{n+1}{2^{2n-1}} \cdot \frac{(2n)!}{(n+1)!(n-1)!} \\ &= \frac{n+1}{2^{2n-1}} \cdot \frac{(2n)!}{n!n!} \cdot \frac{n}{n+1} \\ &= \boxed{\frac{2n}{2^{2n}} \binom{2n}{n}}. \end{align*}

Similarly, let $S_{2n+1}$ be the number of successes in $2n+1$ trials, for a difference of $|S_{2n+1} - (2n+1 - S_{2n+1})| = |2S_{2n+1} - 2n - 1|$. Let $1 \leq k \leq 2n+1$ be an odd number in the form $k = 2k' + 1$. Then

\begin{align*} \mathbb{P}(|2S_{2n+1} - 2n - 1| = k) &= \mathbb{P}(2S_{2n+1} - 2n - 1 = k) + \mathbb{P}(2S_{2n+1} - 2n - 1 = -k) \\ &= \mathbb{P}\left(S_{2n+1} = n + \frac{k+1}{2}\right) + \mathbb{P}\left(S_{2n+1} = n + \frac{1-k}{2}\right) \\ &= \frac{1}{2^{2n+1}} \left(\binom{2n+1}{n + \frac{k+1}{2}} + \binom{2n+1}{n + \frac{1-k}{2}}\right) \\ &= \frac{1}{2^{2n}}\binom{2n+1}{n + \frac{k+1}{2}}. \end{align*} Writing $k = 2k' + 1$, the probability becomes $$\mathbb{P}(|2S_{2n} - 2n - 1| = k) = \frac{1}{2^{2n}}\binom{2n+1}{n + k' + 1}.$$

Even differences are not possible, so we have \begin{align*} E(Y_{2n+1}) &= \sum_{k=1}^{2n+1} k \, \mathbb{P} (|2S_{2n+1} - 2n - 1| = k) \\ &= \frac{1}{2^{2n}}\sum_{k'=0}^n (2k'+1) \,\binom{2n+1}{n + k' + 1} \\ &= \frac{n+1}{2^{2n}}\binom{2n+1}{n+1} \\ &= \frac{n+1}{2^{2n}}\cdot \frac{2n+1}{n+1} \cdot \frac{2n!}{n!n!} \\ &= \boxed{\frac{2n+1}{2^{2n}} \binom{2n}{n}}. \end{align*}

Stirling's approximation states that $$n! \sim \sqrt{2\pi n}n^n e^{-n},$$ so $$\binom{2n}{n} \sim \frac{2^{2n}}{\sqrt{\pi n}}.$$ This gives us $$E(Y_{2n}) \sim \frac{2n}{\sqrt{\pi n}} = \frac{2}{\sqrt{\pi}} \sqrt{n}.$$ Thus the expected difference is $\boxed{\mathcal{O}(\sqrt{n})}.$

EDIT 1: My previous answer didn't have the right conditional expectation, so I just computed general probabilities and used the definition of expectation.

EDIT 2: Added asymptotics.

Answer 2

Define $S_n=\sum_{k=1}^n X_i$. $S_n$ is a simple symmetric random walk starting at $0$. Let $n^+$ ($n^-$) be the number of steps taken up (down) s.t. $n^++n^-=n$. Then $S_n=n^+-n^-$ and the number of paths leading from $0$ to $k$ in $n$ steps ($k\le n$) is

$$p_{k,n}=\binom{n}{\frac{n+k}{2}}\cdot 1\{(n-k)\mod 2=0\}$$

because when $n$ is even $k$ cannot be odd and vice versa and $k=n^+-n^-=2n^+-n$. Consequently,

$$P\{S_n=k\}=\frac{p_{k,n}}{2^n}$$

and

$$\mathbb{E}|S_n|=\frac{1}{2^n}\sum_{k=-n}^n|k|p_{k,n}=\frac{1}{2^n}\sum_{k \in [-n,-n-2,\dots,n-2,n]}|k|\binom{n}{\frac{n+k}{2}}=\frac{1}{2^{n-1}}\Big\lceil \frac{n}{2}\Big\rceil\binom{n}{\lceil n/2\rceil}$$

The last step is pretty tedious and can be found in many texts on RW. Also for large $n$

$$\mathbb{E}|S_n|\approx\sqrt{\frac{2n}{\pi}}$$