Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Some fellow students ran a contest this past summer. I had stopped following it by the time this problem came out. I looked back through some of the older problems, saw this and thought I'd try to solve it.

Let $S$ be an infinite sequence of random variables, all $0$ or $1$, such that the probability of $S_n$ being $0$ is $1/n^2$. Let $p$ be the expected value of the probability that the product of the elements of a randomly chosen subsequence of $S$ is nonzero.

Regarding how subsequences are chosen, keep in mind this problem was written by high schoolers like me (so no measure theory or the like). I don't know much about infinite discrete probability spaces, so I just approached the problem as if it were asking for the limit of the value for the finite case with a uniform distribution. They seem to have interpreted it the same way. If another interpretation makes sense and is interesting, by all means, use it.

The value I obtained for $p$ was $$ \frac{1}{\Gamma\left(1 + \frac{1}{\sqrt{2}} \right) \Gamma\left( 1 - \frac{1}{\sqrt{2}} \right)} = \frac{\sqrt{2} \sin\left( \frac{\pi}{\sqrt{2}} \right)}{\pi} $$ which the problem writer agreed with. My solution is not very insightful, however, and the problem writer only remembered the answer, not the apparently quite slick solution. Another one of the problem writers mentioned the Borel–Cantelli lemma, but while the given example is very similar (and probably the inspiration for the problem), it doesn't seem close enough to really help. I'd like to know if anyone can come up with an easier solution than the following (which is not very slick).

Write $$ p_n = \frac{\sum_a \prod_i \left( 1 - \frac{1}{a_i^2} \right)}{2^n} $$ where the sum is over all subsequences of the first $n$ random variables, and $$ p = \lim_{n\to\infty} p_n $$

Then the numerator can be rewritten as $$ \prod_i \left( 1 + \left(1 - \frac{1}{i^2} \right) \right) = \prod_i \left( 2 - \frac{1}{i^2} \right) = 2^n \prod_i \left( 1 - \frac{1}{\sqrt{2} i} \right) \left( 1 + \frac{1}{\sqrt{2} i} \right) $$

Using the same manipulations as those discussed here, we get $$ \frac{2^n \Gamma\left( n + 1 - \frac{1}{\sqrt{2}} \right) \Gamma\left( n + 1 + \frac{1}{\sqrt{2}} \right)}{\Gamma\left( 1 + \frac{1}{\sqrt{2}} \right) \Gamma\left( 1 - \frac{1}{\sqrt{2}} \right) \Gamma(1 + n)^2} $$ Dividing by $2^n$ and taking the limit as $n \to \infty$ gives the desired result.

So, is there a better, less algebraic and more probabilistic solution to this problem?

share|improve this question
    
Could you make the question self-contained, instead of referring to some content outside of the site? –  Did Jan 16 '12 at 6:32
    
What does *a randomly chosen subset of $S$* mean? First, $S$ is a sequence, not a set. Second, if we interpret this as the set of values $S_n$ for $n$ in a randomly chosen subset $K\subseteq\mathbb N$, how does one choose randomly $K$? // Likewise: what is $a_i$? –  Did Jan 16 '12 at 6:57
    
$a$ refers to a sequence of indices of the random variables, e. g., $(1, 2, 3)$ corresponds to the subsequence $(S_1, S_2, S_3)$. –  dysonsfrog Jan 16 '12 at 7:22
    
A full new paragraph in the edited version explains how to choose $K$. (Note that the request to avoid infinite discrete probability spaces may seem odd regarding a problem about almost surely infinite subsets of $\mathbb N$.) –  Did Jan 16 '12 at 7:38
    
I said I don't know much about them. If that approach is simpler, than feel free to use it, even if it yields a different answer for some reason. If there's a better, more formal way of defining this problem, I'd love to hear it. –  dysonsfrog Jan 16 '12 at 7:51

1 Answer 1

up vote 2 down vote accepted

One should add the hypothesis that the random variables $S_n$ are independent and that the choice of a random subset is independent on them.

Formal setting

One is given on the one hand an infinite sequence $(A_n)_{n\geqslant1}$ of independent events such that $\mathrm P(A_n)=p_n$ with $p_n=1-\frac1{n^2}$, and on the other hand an infinite sequence $(Y_n)_{n\geqslant1}$ of independent Bernoulli random variables such that $\mathrm P(Y_n=0)=\mathrm P(Y_n=1)=\frac12$. The sequences $(A_n)_{n\geqslant1}$ and $(Y_n)_{n\geqslant1}$ are independent.

Here is why this models the situation you have in mind. The sequence $(A_n)_{n\geqslant1}$ models the random variables $(X_n)_{n\geqslant1}$ through the relation $A_n=[X_n=1]$. The sequence $(Y_n)_{n\geqslant1}$ defines a random subset $N=\{n\in\mathbb N\mid Y_n=1\}\subseteq\mathbb N$ and yields at once all the finitary representations used in your post because, for every fixed $n\geqslant1$, the random set $N\cap\{1,2,\ldots,n\}$ is uniformly distributed on the $2^n$ subsets of $\{1,2,\ldots,n\}$. To see this, note that for every $B\subseteq\{1,2,\ldots,n\}$, $$ \mathrm P(N\cap\{1,2,\ldots,n\}=B)=\prod\limits_{k\in B}\mathrm P(k\in N)\cdot\prod\limits_{k\leqslant n,\ k\notin B}\mathrm P(k\notin N), $$ which is $$ \mathrm P(N\cap\{1,2,\ldots,n\}=B)=\prod\limits_{k\in B}\mathrm P(Y_k=1)\cdot\prod\limits_{k\leqslant n,\ k\notin B}\mathrm P(Y_k=0)=\frac1{2^n}. $$ Now, one asks for the probability of the event $$ A=\bigcap\limits_{n\in N}A_n. $$ Solution of the problem

For a given $N$, the independence hypothesis on the random variables $(X_n)_{n\geqslant1}$ implies that $$ \mathrm P(A\mid N)=\prod\limits_{n\in N}\mathrm P(A_n)=\prod\limits_{n\in N}p_n=\prod\limits_{n\geqslant1}(1-(1-p_n)\mathbf 1_{n\in N}). $$ The independence hypothesis on the random variables $(Y_n)_{n\geqslant1}$ implies that $$ \mathrm P(A)=\mathrm E(\mathrm P(A\mid N))=\prod\limits_{n\geqslant1}(1-(1-p_n)\mathrm P(n\in N)), $$ that is, $$ \mathrm P(A)=\prod\limits_{n\geqslant1}(1-\tfrac12(1-p_n))=\prod\limits_{n\geqslant1}\frac{1+p_n}2=\prod\limits_{n\geqslant1}\left(1-\frac1{2n^2}\right). $$ Finally, the representation of the sine function as an infinite product for $z=\frac1{\sqrt2}$ indicates that the infinite product in the RHS above is indeed $\frac{\sin z}{z}=\frac{\sqrt2}{\pi}\sin\left(\frac{\pi}{\sqrt2}\right)$.

share|improve this answer
    
I like the use of the infinite product representation for sine. I'd seen it before but it didn't even cross my mind for some reason. –  dysonsfrog Jan 16 '12 at 14:52
    
Infinite product representations for the gamma function can also explain the answer: en.wikipedia.org/wiki/Gamma_function#Alternative_definitions. Interesting. –  dysonsfrog Jan 16 '12 at 15:14

Your Answer

 
discard

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.