0

Given $N$ Bernoulli random variables $X_i$ that take on value 1 with probability $p = 0.4$ and $0$ otherwise, what is the probability that $Y = 1$, where $$\begin{align} Y &=\lim_{N\to\infty} Y_N\\ &= \lim_{N \to \infty} X_1 \oplus X_2 \oplus \cdots \oplus X_N \end{align}$$

The answer is apparently 0.5, but I am having trouble figuring out why. I think the approach must be to derive some equation for $Y_N$ and then take the limit, and this expression, would be recursive in nature as $Y_N$ can be obtained from $Y_{N+1}$. Is this the idea, or is there something really simple that I'm missing?

Michael Hardy
  • 1
user5965026
  • 677
  • Here is the same question, phrased differently: https://math.stackexchange.com/questions/1149270/probability-that-a-random-variable-is-even (note that $\frac{1}{2}\left(1+(1-2\cdot 0.4)^N\right)\xrightarrow[N\to\infty]{} \frac{1}{2}$). – Clement C. Mar 02 '21 at 03:51
  • In this article, see the portions about showing your work and then asking follow-up questions. – user2661923 Mar 02 '21 at 03:51
  • @ClementC. I think so. I didn't think about how this question could be phrased in terms of "Given $N$ bernoulli trials, what is the probability of having an odd number of success." – user5965026 Mar 02 '21 at 03:59
  • 1
    Actually, I kind of like this phrasing of the question. This makes it clear that when you jumble (which is the intuition of XOR in a cryptographic sense) many (i.i.d.) random things together, you get no information (answer = ½) at all about each individual random thing, even if the original random thing carries some information (p = 0.4, biased -- it can be something extreme as p=0.01). Both interpretations of the question are useful. – Benjamin Wang Mar 02 '21 at 04:02
  • @BenjaminWang The $p=0.4$ seems to be sort of a red herring. I just derived the recursion, $p_{k+1} = p + (1-p) p_{k+1}$, and it seems to always approach 0.5 as long as $p \leq 0.5$. Though I haven't figured out a way to actually prove this formally. – user5965026 Mar 02 '21 at 04:12
  • @user5965026 The linked answer does provide the recursion; but yes, it'll work for any $p\in(0,1)$. (There is obviously a problem for $p\in{0,1}$.) – Clement C. Mar 02 '21 at 04:15
  • @ClementC. Do you mean $p\in (0, 0.5]$? Oh never mind, it does work for $p > 0.5$. – user5965026 Mar 02 '21 at 04:21
  • @user5965026 No, $p\geq 1/2$ is possible too. Let me see if there is any issue with the linked post... – Clement C. Mar 02 '21 at 04:22
  • @ClementC. I looked at the top rated answer for that question. The author makes an initial claim that the answer is what he purported and then used induction to prove that it's true. But it's not intuitive how one can just come up with that expression. – user5965026 Mar 02 '21 at 04:33
  • 1
    @user5965026 Here is a way. Let $a_n$ (for $n\geq 0$) be the probability to have an odd number of successes. Then $a_0=0$, and $$a_{n+1} = (1-p)a_n + p (1-a_{n}$$ since if you had an odd number of successes in the first $n$, then you want the $(n+1)$th to be a failure; and if you had an even number among the first $n$, then you want a success to get an odd number. You can solve this system and get $a_n = \frac{1}{2}\left(1-(1-2p)^n\right)$, then check it makes sense for $n=0,1,2$ (arbitrary $p$) and also for $p\in{0,1/2,1}$ (arbitrary $n$), just to be safe.. – Clement C. Mar 02 '21 at 04:39
  • @ClementC. Thanks, so I understand how to get the recursion expression. When you say solve the system to get your expression for $a_n$, do you mean solving the recursion? I haven't done much work with solving recursions analytically, but I understand there's some known solutions to recursive equations of certain structure. – user5965026 Mar 02 '21 at 19:56
  • @user5965026 yes, solve the recursion. For this particular form, it's not too hard (define $b_n$ by shifting $a_n$ by 1/2 and you get a geometric sequence). – Clement C. Mar 02 '21 at 20:03

0 Answers0