Sum and alternating sum of a series of Bernoullian variates

Question

Consider the random variables
$a_i,i=0,1,\ldots,n$ be random variables which take values from $\{-1,1\}$ independently and randomly with equal probability. Let \begin{align} S &= a_1+\cdots+a_n , \\ A &= a_1-a_2+a_3+\cdots . \end{align} I want to compute the probability that $S. A<0$.

Here is my attempt:

Attempt Let $E_1$ be the event that $S>0$ and $E_2$ be the event that $A>0.$ To simplify things assume $n$ is even, to begin with.

We observe that $S>0$ if more than half of $a_i$'s are +1. Next, for the alternating sum $A$, we have $A<0$ when $S>0$, if more of the $a_i$'s that contribute to $S$ have an odd index than an even index. Precisely, we want $ 2P(E_1 \cap E_2)$. We have:

\begin{equation} P(E_1 \cap E_2)=P(E_1 | E_2)P(E_2)=P(E_2 | E_1)P(E_1) \end{equation}

Now, \begin{align} P(E_1) &= P(S>0) \\ & =\sum_{k=\frac{n}{2}+1}^n \binom{n}{k} \cdot \frac{1}{2^n}. \end{align}

So,

\begin{equation} P(E_2 | E_1) = P(A<0 | S>0). \end{equation}

If $k \geq \frac{n}{2}+1$ are $+1$'s, then for $A$ to be negative, at least $\left\lfloor\frac{k}{2}\right\rfloor+1$ have to have odd indices. That means,

$$ P(E_1 \cap E_2)=\frac{\displaystyle\sum_{k=\frac{n}{2}+1}^n \sum_{\ell=\left\lfloor\frac{k}{2}\right\rfloor+1}^k \binom{k}{\ell}}{2^k} $$

Therefore, we have: \begin{equation} P(E_1 \cap E_2) = \displaystyle\sum_{k=\frac{n}{2}+1}^n \sum_{\ell=\left\lfloor\frac{k}{2}\right\rfloor+1}^k \binom{k}{\ell} \frac{1}{2^k} \cdot \displaystyle\sum_{k=\frac{n}{2}+1}^n \binom{n}{k} \frac{1}{2^n}. \end{equation}

Since we have $S A$, even when $S<0$ and $A>0$, by symmetry, we conclude that the probability $S A<0$ is twice the probability given above. Hence the probability

\begin{equation} P(E_1 \cap E_2) = \displaystyle\sum_{k=\frac{n}{2}+1}^n \sum_{\ell=\left\lfloor\frac{k}{2}\right\rfloor+1}^k \binom{k}{\ell} \frac{1}{2^k} \cdot \displaystyle \left(\sum_{k=\frac{n}{2}+1}^n \binom{n}{k} \frac{1}{2^{n-1}} \right). \end{equation}

However, I am not sure whether this approach or my solution is correct. Kindly correct me and point out the mistakes, if any.

Answer 1

We have $S=U+V$ and $A=U-V$, where \begin{equation} U:=a_1+a_3+\cdots+a_{2k-1},\quad V:=a_2+a_4+\cdots+a_{2l}, \end{equation} $k:=\lfloor(n+1)/2\rfloor$, $l:=\lfloor n/2\rfloor$. Then $k+l=n$; $U$ and $V$ are independent random variables (r.v.'s); the r.v. $B:=(U+k)/2$ has the binomial distribution with parameters $k,1/2$; the r.v. $C:=(V+l)/2$ has the binomial distribution with parameters $l,1/2$. So, \begin{equation} \begin{aligned} p_n:=&P(SA<0) \\ &=P((U+V)(U-V)<0) \\ &=P(U^2<V^2) \\ &=P(|U|<|V|) \\ &=\sum_{v=-l}^l P(V=v)\sum_{u=1-|v|}^{|v|-1}P(U=u) \\ &=2\sum_{v=1}^l P(V=v)\sum_{u=1-v}^{v-1}P(U=u) \\ &=2\sum_{v=1}^l P(C=(v+l)/2)\sum_{u=1-v}^{v-1}P(B=(u+k)/2) \\ &=2\sum_{v=1}^l 2^{-l}\binom l{(v+l)/2}1(v\equiv l) \sum_{u=1-v}^{v-1}2^{-k}\binom k{(u+k)/2}1(u\equiv k) \\ &=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l) \sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \end{aligned} \end{equation} where $a\equiv b$ means that $a-b$ is even.

The latter expression for $p_n$ has now been greatly simplified, and that result has been checked for $n=1,\dots,10$.

Answer 2

I realised that my attempted solution in the question is incorrect.,here is a my new attempt to answer the question using the approach suggested in the original (incorrect ) solution.It would have been too long for a comment .However the answer is not some elegant expression.\begin{align} S &= a_1+\cdots+a_n , \\ A &= a_1-a_2+a_3+\cdots . \end{align} I want to compute the probability that $S. A<0$.

Here is my attempt:

Let $E_1$ be the event that $S>0$ and $E_2$ be the event that $A>0.$ To simplify things assume $n$ is even, to begin with.

We observe that $S>0$ if more than half of $a_i$'s are +1. . We have:

\begin{equation} P(E_1 \cap E_2)=P(E_1 | E_2)P(E_2)=P(E_2 | E_1)P(E_1) \end{equation}

Now, \begin{align} P(E_1) &= P(S>0) \\ & =\sum_{k=\frac{n}{2}+1}^n \binom{n}{k} \cdot \frac{1}{2^n}. \end{align}. Now to compute $P(E_2 | E_1)$ we make the following simple observation:

Every +1 at an even place will contribute negatively and every -1 will contribute to positively in the alternating sum $A$
So given $S>0,$ we would wish to enumerate the ways in which the alternating sum $A$ can be negative .Let the number of +1's and the number of -1's that go to even places be respectively $l$ and $m.$ Since the total number of even places is $ \frac n2 ,$ we have the following constraints : $$ 0 \leq l \leq \min\{ n/2,k\}$$ and
$$ 0 \leq m \leq \min\{ n/2-l,n-k\}$$ With this arrangement and assuming $E_1$ ,the value the alternating sum will become:$$ (k-l)-l-(n-k-m)+m=2k-2l+2m-n$$ and this we need to be less than zero. so the number of ways of arranging $k>n/2$ +1's and $n-k$ -1's so that $A<0$ can be expressed as $$ \displaystyle \sum_{k=n/2+1}^{n-1} \binom{k}{l} \binom{n-k}{m} \binom{n-l-m}{k-l} $$ subject to the constraints : \begin{align} & 0 \leq l \leq \min\{ n/2,k\} \\ & 0 \leq m \leq \min\{ n/2-l,n-k\}\\ &2k-2l+2m-n<0 \end{align} This will give us us $P(E_2|E_1),$ after we take the probability of this arrangement into account.However ,I am stuck at this which is to be multiplied by \begin{align} P(E_1) &= P(S>0) \\ & =\sum_{k=\frac{n}{2}+1}^n \binom{n}{k} \cdot \frac{1}{2^n} \end{align}.to get the requisite probability.Again ,it is my humble request to that mistakes ,if any be pointed out and kindly tell me whether solution using this approach is even possible.