Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

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