2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ $$\frac{E(Y_{2n})}{2n}=\frac{E(Y_{2n+1})}{2n+1}=\frac1{2^{2n}}{2n\choose n}$$ $\endgroup$
    – Did
    Jun 25, 2015 at 14:12
  • $\begingroup$ Can i ask how you arrived at that? $\endgroup$ Jun 25, 2015 at 14:43

2 Answers 2

1
$\begingroup$

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}}$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Ok thanks for the response this question is related to the following notes cs.berkeley.edu/~sinclair/cs271/n5.pdf. On the first page in the second paragraph starting with " Note first that, if we set all the switches independently and uniformly at random," it assumes that $\mathbb{E}(|\#\mathrm{Successes}-\#\mathrm{failures}|)=O(n)$. I'm wondering how they arrived at that if $\mathbb{E}(Y)=0$? $\endgroup$ Jun 25, 2015 at 16:55
  • $\begingroup$ @PavanSangha look at how switches work. It's not equivalent to turning each light on independently and uniformly at random. $\endgroup$
    – user217285
    Jun 25, 2015 at 17:23
  • $\begingroup$ I understand that in the general problem does not involve lights being turned on independently. Here is my initial question math.stackexchange.com/questions/1338149/unbalancing-lights with someones response, where it seems that they were using the case where all lights are turned on independently to gain some insight into the case they presented. If this is not the case can you explain what they mean by "Note first that, if we set all the the switches independently and uniformly at random," and how they get the result $\mathbb{E}(|\#\mathrm{Success}-\#\mathrm{failures})=O(n)$? $\endgroup$ Jun 25, 2015 at 18:23
  • 1
    $\begingroup$ Sorry but these computations are wrong. Actually it seems you found a way to "prove" that if E(Z)=0 then E(|Z|)=0... :-) $\endgroup$
    – Did
    Jun 25, 2015 at 18:34
  • $\begingroup$ Yes, if you take the case where we have two variables $X_{1}$ and $X_{2}$, it's easy to see that $\mathbb{E}(Y)=1$ $\endgroup$ Jun 25, 2015 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.