# Probability of two sum and alternating sum of two random variables being of opposite signs

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:

$$$$P(E_1 \cap E_2)=P(E_1 | E_2)P(E_2)=P(E_2 | E_1)P(E_1)$$$$

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,

$$$$P(E_2 | E_1) = P(A<0 | S>0).$$$$

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

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

$$$$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).$$$$

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

• Please check after posting whether the equations rendered correctly. I fixed some. And also, I have added the self-study; check its scopes. Commented Jul 11, 2023 at 6:10
• This is a truly interesting puzzle - does it have some practical background?
– Ute
Commented Jul 11, 2023 at 14:16
• Although your approach is good, your result is not correct, unfortunately. Your approach needs a lot of care when finding the number of "good" arrangements for the signs of $A$ and $S$ to be opposite. I've added some closer comments on the difficulties in my answer.
– Ute
Commented Jul 12, 2023 at 10:50
• I agree the approach is a good one and the idea is nearly correct. The details, though, are tricky: getting the right endpoints of the sums is crucial and it is helpful to do some analysis to reduce them from a double sum to something less computationally intensive -- ideally a closed form, but that appears elusive.
– whuber
Commented Jul 17, 2023 at 15:20
• Thank you all for taking time to post these wonderful answers and insights Commented Jul 18, 2023 at 4:47

Generalizing this problem simplifies it.

### Analysis and general solution

I will change the notation slightly for this generalization. Let there be $$m$$ variables $$X_i,$$ $$i=1,2,\ldots, m$$ (to play the roles of $$a_1, a_3, a_5, \ldots$$) and independently let there be $$n$$ variables $$Y_j,$$ $$j=1,2,\ldots, n$$ (playing the roles of $$a_2, a_4, \ldots$$). Let $$S_X$$ be the sum of the $$X_i$$ and let $$S_Y$$ be the sum of the $$Y_j.$$ Define

$$K = \frac{S_X-m}{2},\quad L = \frac{S_Y-n}{2}.$$

Thus, in the notation of the question,

$$S = S_X + S_Y = m + n - 2(K+L);\quad A = S_X - S_Y = m - n - 2(K-L).$$

Now, the event $$SA\lt 0$$ is equivalent to

$$(m-2K)^2 - (n-2L)^2 = S_X^2 - S_Y^2 = (S_X+S_Y)(S_X-S_Y) = SA \lt 0;$$

that is

$$SA \lt 0 \iff|m-2K| \lt |n-2L|.$$

Writing $$\mathrm dF$$ for the joint measure of the distribution of $$(K,L),$$ this gives

$$\Pr(SA \lt 0) = \iint_{|m-2K| \lt |n-2L|}\mathrm dF(k,l) = \int_{\mathbb R}\left\{\int^{-h(l)} \mathrm dF(k\mid l) + \int_{h(l)} \mathrm dF(k\mid l)\right\}\mathrm dF_L(l)$$

where $$h(l) = \min\left(\frac{m+n}{2} - l, \frac{n-m}{2} + l\right)$$ and, as usual, $$\mathrm dF(k\mid l)$$ denotes the conditional measure and $$\mathrm dF_L$$ the marginal measure.

### Specialization to the question

In the question the $$X_i$$ are independent of the $$Y_j,$$ whence $$K$$ and $$L$$ are independent, so there's no issue with computing joint and conditional and marginal densities. Moreover, because all the $$X_i$$ and $$Y_j$$ can only have the values $$\pm 1,$$ the distributions of $$K$$ and $$L$$ are discrete: $$K$$ counts the number of $$-1$$s among the $$X_i$$ while $$L$$ counts the number of $$-1$$s among the $$Y_j.$$ The double integral reduces to a double sum, suitable for computation with small $$m$$ and $$n,$$ while the repeated integral reduces to a single sum, practicable for large problems.

Writing $$l^* = \min(l, n-l),$$ $$F_K$$ for the CDF of $$K,$$ and $$f_L$$ is the probability function of $$L,$$ this can be expressed as

$$\Pr(SA \lt 0) = \sum_{l=0}^n f_L(l) \left\{F_K(\lfloor\frac{m-n+1}{2}+ l^*\rfloor-1) + 1 - F_K(\lfloor\frac{n+m}{2} - l^*\rfloor)\right\}.$$

Finally, because the $$X_i$$ are independent and so are the $$Y_j$$ in the question, $$K$$ has a Binomial$$(m,1/2)$$ distribution and $$L$$ has a Binomial$$(n,1/2)$$ distribution. Thus, $$f_L(l) = 2^{-n}\binom{n}{l}$$ and $$F_K$$ is given by a regularized Beta function. Their symmetries permit the formula to be evaluated over only half the sum (and doubled). There is, in general, no further savings: as far as I can tell, there is no closed form expression for this sum, even when -- as in the question -- either $$m=n$$ or $$m=n+1.$$ Thus, I haven't attempted to go any further.

It is instructive to plot $$\Pr(SA\lt 0)$$ as a function of the variable $$n$$ in the question.

N <- 2:100
p <- sapply(N, \(N) f(N - N %/% 2, N %/% 2))
cols <- hsv(seq(0.02, .6, length.out = 4), .9, .8)
plot(N, p, col = cols, xlab = expression(italic(N)),
main = expression(Pr(italic(SA) < 0)))


With a little patience (ten seconds or so), we can explore the asymptotic behavior with a line plot out to, say, $$n=10\,000:$$

Of course the result converges to $$1/2,$$ so interest lies in how quickly.

As you would expect, the convergence is $$O(n^{-1/2})$$ -- but it depends on the residue of $$n$$ modulo $$4.$$ When the remainder is $$3,$$ the value is always exactly $$1/2,$$ as a symmetry argument will show. Otherwise, the convergence is quadratic, albeit with slightly different coefficients.

All plot the absolute differences between the values and their common limit of $$1/2.$$ The first three plots are on log-log axes (which works because all the differences are nonzero). The near-linear graphs document the $$O(n^{-1/2})$$ behavior (although the slight curvature apparent in the first one, for multiples of $$4,$$ is intriguing). The last plot, for $$n\equiv3 \mod 4,$$ uses a linear vertical scale because many of the differences are zero. Clearly all those probabilities are trying to equal $$1/2$$ but fail only because of floating point imprecision.

Here, to be explicit, is an R implementation of the general solution. It requires both $$m$$ and $$n$$ to be positive.

f <- function(m, n, F.K = \(k) pbinom(k, m, 1/2), p.L = \(l) dbinom(l, n, 1/2)) {
l <- seq(0, n)
lstar <- pmin(l, n - l)
F. <- F.K(floor(lstar + (m-n+1)/2) - 1)
S. <- 1 - F.K((n+m)/2 - lstar)
sum(p.L(l) * (F. + S.))
}


To serve as a check, here is a brute-force implementation of the double integral.

f2 <- function(m, n, p.K = \(k) dbinom(k, m, 1/2), p.L = \(l) dbinom(l, n, 1/2)) {
joint <- outer(dbinom(0:m, m, 1/2), dbinom(l, n, 1/2))
nn <- outer(0:m, 0:n, \(k,l) abs(m - 2*k) < abs(n - 2*l))
joint[!nn] <- 0
sum(joint[nn])
}


And, as another check, these probabilities can be estimated through simulation. This solution is specific to the Binomial probabilities in the question. The first argument is the length of the simulation.

fsim <- function(N, m, n) {
X <- matrix(sample(c(-1,1), m * N, replace = TRUE), m)
Y <- matrix(sample(c(-1,1), n * N, replace = TRUE), n)
S.X <- colSums(X)
S.Y <- colSums(Y)
S <- S.X + S.Y
A <- S.X - S.Y
mean(S * A < 0)
}


Because the correctness of the formula rests on niggling details related to the parities of $$m$$ and $$n$$ and which is larger, here is a quick (one-second) study using simulated datasets of size N = 1e5 (intended to yield close to three decimal digits of precision) covering a range of values of $$m$$ and $$n$$.

N <- 1e5; i <- 1:4; j <- 1:4
set.seed(17)
matrix(sapply(i, \(m) sapply(j, \(n)  {
round(c(Double sum = f2(m, n), Sum = f(n,m), Simulation = fsim(N, m, n)), 3)
})), 3, dimnames = list(Statistic = c("Double sum", "Sum", "Simulation"),
m,n = t(outer(i, j, paste, sep = ","))))

            m,n
Statistic    1,1   1,2  1,3   1,4   2,1  2,2   2,3   2,4 3,1   3,2   3,3   3,4   4,1   4,2   4,3   4,4
Double sum   0 0.500 0.25 0.625 0.500 0.25 0.625 0.375   0 0.375 0.188 0.500 0.375 0.188 0.500 0.297
Sum          0 0.500 0.25 0.625 0.500 0.25 0.625 0.375   0 0.375 0.188 0.500 0.375 0.188 0.500 0.297
Simulation   0 0.501 0.25 0.624 0.498 0.25 0.622 0.373   0 0.374 0.188 0.501 0.374 0.185 0.498 0.300


You can see all three solutions agree.

The single sum, though, is the most practicable:

system.time(f2(1000, 10001))

  user  system elapsed
2.47    0.27    2.92

system.time(f(1000, 10001))

   user  system elapsed
0       0       0

• thank you a lot for explaining it so nicely and taking it to next level Commented Jul 18, 2023 at 4:48

## tl; dr: Correct result?

Although the original post contains many correct ideas, it ends up with a formula for $$P(S>0, A>0)$$ that can yield probabilities larger than 1,

$$$$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).$$$$

So it cannot be correct, unfortunately.

Sections below:

1. Correct result, and checking by simulation (R)
2. A few comments on the derivation of $$P(SA<0)$$ in the original post
3. Derivation of the correct result (alternative solution)

## 1. Partial correct result, and checking results by simulation

For $$n=1$$, obviously it is not possible that $$S$$ and $$A$$ have opposite sign. Here, $$P(SA <0)=0$$.

For $$n>1$$, $$\color{red}{n \not\equiv1\mod 4}$$, it is $$P(SA < 0) = \frac{1}{2} - \frac{1}{2} P(SA=0).$$

The probability that $$SA=0$$ depends on $$n$$:

• for odd $$n$$, $$S$$ and $$A$$ have to be odd. Therefore, $$P(SA=0)=0.$$
• for even $$n$$, we need to distinguish between even and odd $$n/2$$:
• if $$n/2$$ is odd, $$P(SA=0)=\frac{1}{2^{n-1}}\sum_{k=0}^{n/2}\binom{n/2}{k}^2.$$
• if $$n/2$$ is even, $$P(SA=0)=\frac{1}{2^{n-1}}\sum_{k=0}^{n/2}\binom{n/2}{k}^2 - \frac{1}{2^n}\binom{n/2}{n/4}^2.$$

Here is a simple R code stump to simulate the variables $$A$$ and $$S$$, here for n=6, and a function pzero that implements the formula for $$P(SA=0)$$.

n <- 6
nsim <- 100000
A <- S <- numeric(nsim)
index1 <- seq(1, n, 2)

for (i in 1:nsim){
a <- sample(c(-1,1), n, replace = TRUE)
Y1 <- sum(a[index1])
Y2 <- sum(a[-index1])
S[i] <- Y1+Y2
A[i] <- Y1-Y2
}

# estimated probability that AS<0
mean(A*S < 0)

# estimated probability that AS=0
mean(A*S == 0)

# theoretical result
pzero <- function(n){
if (n%%2 == 1) pz = 0
else {
pz <- sum(dbinom(0:(n/2), n/2, 0.5)^2)*2
if (n%%4 ==0)  pz <- pz - dbinom(n/4, n/2, 0.5)^2
}
pz
}
# check with theory
pzero(6)


## 2. Some comments on the attempt in original post

[The original post denotes by $$k$$ the number of $$+1$$s, and later, $$\ell$$ is used as summation index for the number of $$+1$$'s placed on even indices.]

• The formula for $$P(E_1)$$ is correct.
• It is not completely correct that,
If $$k>\frac{n}{2}+1$$ of the $$a_i$$ are $$+1$$s, then then for A to be negative, at least $$\left\lfloor\frac{k}{2}\right\rfloor+1$$ have to have odd indices
but this is probably just a typo, and you meant *even* indices that change the sign.
• If $$k=n$$ of the $$a_i$$ are $$+1$$s, it is not possible for $$A$$ to be negative. So the "good" values for $$k$$ lie between $$\lfloor\frac{n+1}{2}\rfloor$$ and $$n-1$$, not $$n$$.
• to find the number of good placements for the $$+1$$s that give negative $$A$$, you say that $$\ell$$ have to be on even places. Then, you would have to multiply the possibilities to choose the odd places with the number of possibilities to distribute the remaining $$+1$$s on the even places. If we call $$n_{\text{odd}}=\lfloor\frac{n+1}{2}\rfloor$$ the number of odd places, and $$n_{\text{even}}=n- n_{\text{odd}}$$ the number of even places, you get as possible good solutions $$\binom{n_\text{even}}{\ell}\binom{n_\text{odd}}{k-\ell}$$.

## 3. Alternative solution ($$n>1$$)

Instead of looking at the probabilities for $$S>0$$ and $$A>0$$, divide these sums up into the parts with odd and even indices, $$Y_1:=a_1+a_3+\ldots \quad\text{and}\quad Y_2:=a_2+a_4+\ldots .$$
Then $$S=Y_1+Y_2$$ and $$A=Y_1-Y_2$$, thus $$SA= Y_1^2-Y_2^2,$$ and $$SA < 0 \quad\Longleftrightarrow\quad |Y_1| < |Y_2|.$$

The $$a_i$$ being independent implies that $$Y_1$$ and $$Y_2$$ are independent.

Since $$\frac{1}{2} (a_i +1)$$ takes values in $$\{0,1\}$$ with equal probability, we can write $$Y_j = 2 X_j - n_j,\quad X_j\sim\text{Binom}(n_j,1/2),\quad j=1,2,$$ where $$n_j$$ is the number of summands in $$Y_j$$.

#### Case 1) $$n$$ is even

Here, $$Y_1$$ and $$Y_2$$ are i.i.d. with $$n_1=n_2=n/2$$. Therefore, \begin{aligned} &P (SA>0) = 1- P(SA <0) -P(SA=0) \\ \implies\quad& P(SA<0)=P(SA>0)=\frac{1}{2}-\frac{1}{2}P(SA=0) \end{aligned}

The probability $$P(SA=0)$$ can be obtained from the binomial probabilities for $$X_1$$ and $$X_2$$, since $$SA=0 \quad\Longleftrightarrow\quad |Y_1|=|Y_2|\quad\Longleftrightarrow\quad X_1=X_2\ \text{or}\ X_1+X_2=n/2.$$

To calculate $$P(SA=0)$$ through binomial probabilities, we use that $$P(X_1=k)=P(X_1=n/2-k)$$

• If $$n/2$$ is odd, the events "$$X_1=X_2$$" and "$$X_1+X_2=n/2$$" are disjoint. Then \begin{aligned} P(SA=0)&=P(X_1=X_2) + P(X_1=n/2-X_2) \\&\quad - P(X_1=X_2\ \wedge\ X_1+X_2=n/2) \\&= 2\sum_{k=0}^{n/2}\left(\binom{n/2}{k}\frac{1}{2^{n/2}}\right)^2 - 0 \\&= \frac{1}{2^{n-1}}\sum_{k=0}^{n/2}\binom{n/2}{k}^2. \end{aligned}

• If $$n/2$$ is even, conditions "$$X_1=X_2$$" and "$$X_1+X_2=n/2$$" are both satisfied for $$X_1=X_2=n/4$$. Therefore, \begin{aligned} P(SA=0)&=P(X_1=X_2) + P(X_1=n/2-X_2) \\&\quad - P(X_1=X_2=n/4) \\&=\frac{1}{2^{n-1}}\sum_{k=0}^{n/2}\binom{n/2}{k}^2 - \left(\binom{n/2}{n/4}\frac{1}{2^{n/2}}\right)^2. \end{aligned}

#### Case 2) $$n$$ is odd, and $$(n+1)/2$$ is even

Here $$Y_1$$ is odd and $$Y_2$$ is even. It is therefore not possible that $$|{Y_1}| = |{Y_2}|$$.

Now write $$Y_1^*=Y_1-a_n$$. Then again, $$Y_1^*$$ and $$Y_2$$ are i.i.d., and they only take even values. Since $$|a_n| = 1$$, we have the $$|Y_1^*|>|Y_2|\implies |Y_1|>|Y_2|\quad \text{and}\quad |Y_1^*|<|Y_2|\implies |Y_1|<|Y_2|$$ while $$(|Y_1|^*=|Y_2|) \ \wedge\ (\text{sign}(a_n)= \text{sign}(Y_1)) \implies |Y_1|>|Y_2|$$ and $$(|Y_1|^*=|Y_2|) \ \wedge\ (\text{sign}(a_n)= -\text{sign}(Y_1)) \implies |Y_1|<|Y_2|.$$ Thus, using symmetry, \begin{aligned} P(|Y_1|>|Y_2|)&=P(|Y_1^*|>|Y_2|) + P(\text{sign}(a_n)= \text{sign}(Y_1))\cdot P(|Y_1^*|=|Y_2|)\\ &=P(|Y_1^*|<|Y_2|) + P(\text{sign}(a_n)= -\text{sign}(Y_1))\cdot P(|Y_1^*|=|Y_2|) \\&=P(|Y_1|<|Y_2|)=\frac{1}{2}. \end{aligned}

So $$P(SA <0) = P(SA>0) = 1/2$$ for odd $$n$$.

• ,thank you for your wonderful explanation and detailed solution Commented Jul 12, 2023 at 11:29
• Close, but not quite right. This is a tricky problem, so it helps to perform checks by means of different solutions. See the three methods I posted.
– whuber
Commented Jul 17, 2023 at 15:14
• @whuber, you are right, great you came back to that one. It was too much of a shortcut in Case 2, and that one only works in half of the cases. I had cut down my solution too drastically at one point - I'll fix it :-)
– Ute
Commented Jul 17, 2023 at 15:52
• @whuber, agree that one should check with different solutions, why I also posted a rudimentary simulation (not wrapped in a formula, and with for loops, to keep it most transparent, but the drawback was that I apparently forgot to change n to 5 and got excited about simplifying the solution for odd n...)
– Ute
Commented Jul 17, 2023 at 17:04

Taking into account the few valuable rectifying comments ,here is a my 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:

$$$$P(E_1 \cap E_2)=P(E_1 | E_2)P(E_2)=P(E_2 | E_1)P(E_1)$$$$

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 observations:

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 gives us $$P(E_2|E_1),$$ after taking probability of this arrangement into account .That value 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 through this approach is possible