Take the 2-minute tour ×

I am having trouble of calculating the following probability:

Let $\epsilon_i$, $i=1,\dotsc,N$ be Rademacher random variables. Let $n_i\in \{0, 1, 2, \dotsc, M\}$, $i=1,\dotsc,N$ such that $\sum_{i=1}^Nn_i=M$. I want to calculate $$ P\left(\left\{\prod_{i=1}^N\epsilon^{n_i}_i=1\right\}\bigcap\left\{\sum_{i=1}^N\epsilon_i=0\right\}\right). $$

Thank you.

share|improve this question
Are the $n_i$ constants or random variables? Note that $P\prod_{i=1}^n\epsilon^{n_i}_i=1$ iff the sum of those $n_i$ for which $\epsilon_i = -1$ is even, while $\sum_{i=1}^N\epsilon_i=0$ holds whenever exactly half of all $\epsilon_i$ are negative. Thus, the problem comes down to counting all combinations that satisfy both conditions (and dividing by $2^N$). In particular, for fixed $n_i$, only the evenness of the actual values matters. –  Ilmari Karonen Feb 11 '12 at 8:53
Ps. For other readers, it might help to note that, AAUI, a Rademacher r.v. $\epsilon$ is a discrete r.v. with $P(\epsilon = 1) = P(\epsilon = -1) = \frac12$. I also assume you meant for all the random variables to be independent. –  Ilmari Karonen Feb 11 '12 at 8:56
Thank you. Yes, $n_i$ are constants and $\epsilon_i$ are i.i.d. But it turns out that counting all combinations that satisfy both conditions is hard part for me... –  David Feb 11 '12 at 14:12

2 Answers 2

up vote 0 down vote accepted

I'll give you just my idea. Suppose you have ordered the $\epsilon_i$ such that the first $J$ have $n_i$ odd. This because, when $n_i$ is odd, $\epsilon_i^{n_i}=\epsilon_i$; when $n_i$ is even, $\epsilon_i^{n_i}=1$.

Then $\prod_{i=1}^N\epsilon_i^{n_i}=\prod_{i=1}^J\epsilon_i$.

Now what you want is that in the first $J$ there are an even number of r.v.'s with result -1, in all the N half and half.

So you can have 0 of -1 in the first J (so all +1) and in the N-J remaining N/2 are -1 (of course you need $2N\geq J$) and the number of such combination are $1\cdot C(N-J,N/2)$.

Then you can have 2 of -1 in the first J ($C(J,2)$) and you need N/2-2 of (-1) in the remaining N-J ($C(N-J,N/2-2)$)...

Hope it will help you and it is correct.

I am now reading from the original post that $\sum_{i=1}^Nn_i=M$. I havent read before: I dont think this change the solution; it will maybe open an easier way.

share|improve this answer
The statement $\sum_{i=1}^Nn_i=M$ seems to be a red herring. $M$ does not appear anywhere else in the problem, except as an upper bound for $n_i$, which is trivially true anyway: no member of a sequence of non-negative numbers can be greater than their sum. –  Ilmari Karonen Feb 13 '12 at 16:26
If $\sum_{i=1}^Nn_i=M$, isn't it mean that we can actually represent $J$ in terms of $M$? I mean one can calculate what and how many possibilities for $J$? –  David Feb 15 '12 at 3:00

To begin with, in order to satisfy

$$ \prod_{i=1}^{N}\epsilon_{i}^{n_{i}}=1 $$

we must have that, for $S=\left\{ i\backepsilon\epsilon_{i}=-1\right\} $, $$ \sum_{i\in S}n_{i} $$ is even. Since

$$ \sum_{i=1}^{N}n_{i}=M $$

we want to enumerate the partitions of M in N parts such that a sum of a subset S of its parts is even. The subset is selected at random, selecting a part if $\epsilon_{i}=-1$ and leaving a part out if $\epsilon_{i}=1$. We don't care about the $n_{i}$ for which $\epsilon_{i}=1$.

Furthermore, in order to satisfy

$$ \sum_{i=1}^{N}\epsilon_{i}=0 $$

there needs to be the same number of $\epsilon_{i}$ such that $\epsilon_{i}=1$ as there are $\epsilon_{i}$ such that $\epsilon_{i}=-1$, so that N has to be even.

Therefore, the partitions of M into N parts (where N is even) have to be such that a subset of its parts is the partition of an even number. If M is odd, this subset must be strict. And we select parts from the partition of M at random, with a coin toss.

The problem is not solved, but it is framed in terms that could lead to a solution.

share|improve this answer
You seem to be ignoring the exponents $n_i$ in the first formula. –  Ilmari Karonen Feb 12 '12 at 7:28
You are right. I will try to correct this. –  Jean-Victor Côté Feb 13 '12 at 1:34

Your Answer


