5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Please check after posting whether the equations rendered correctly. I fixed some. And also, I have added the self-study; check its scopes. $\endgroup$ Commented Jul 11, 2023 at 6:10
  • $\begingroup$ This is a truly interesting puzzle - does it have some practical background? $\endgroup$
    – Ute
    Commented Jul 11, 2023 at 14:16
  • $\begingroup$ 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. $\endgroup$
    – Ute
    Commented Jul 12, 2023 at 10:50
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented Jul 17, 2023 at 15:20
  • $\begingroup$ Thank you all for taking time to post these wonderful answers and insights $\endgroup$ Commented Jul 18, 2023 at 4:47

3 Answers 3

2
$\begingroup$

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.

Comments

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

plot of probabilities for n = 2, 3, ..., 100

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

enter image description here

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.

enter image description here

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
$\endgroup$
1
  • $\begingroup$ thank you a lot for explaining it so nicely and taking it to next level $\endgroup$ Commented Jul 18, 2023 at 4:48
1
$\begingroup$

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,

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

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

$\endgroup$
4
  • $\begingroup$ ,thank you for your wonderful explanation and detailed solution $\endgroup$ Commented Jul 12, 2023 at 11:29
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented Jul 17, 2023 at 15:14
  • $\begingroup$ @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 :-) $\endgroup$
    – Ute
    Commented Jul 17, 2023 at 15:52
  • $\begingroup$ @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...) $\endgroup$
    – Ute
    Commented Jul 17, 2023 at 17:04
0
$\begingroup$

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:

\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 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

$\endgroup$
1
  • $\begingroup$ Please compare your formulas to those I developed in my post in this thread and to the simulated results. All of them contradict your solution, unfortunately. $\endgroup$
    – whuber
    Commented Jul 17, 2023 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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