TITLE: Probability that logarithm expression of $500$ values between $(0,1]$ is even
QUESTION [3 upvotes]: Let $a_1, a_2, a_3, \ldots, a_{500}$ be uniformly and independently chosen from the interval $(0,1]$ at random. Find the probability that $$\lceil \log_2 (a_1) \rceil + \lceil \log_4(a_2)\rceil + \ldots + \lceil \log_{1000} (a_{500})\rceil$$ is even.

I have noticed that for some $\lceil \log_m (a_n) \rceil =0,$ than $a_n \in (\tfrac{1}{m}, 1].$ Then for $\lceil \log_m (a_n) \rceil = -1, -2, \ldots,$ we get intervals $(\tfrac{1}{m^2}, \tfrac{1}{m}], (\tfrac{1}{m^3}, \tfrac{1}{m^2}],$ and so on. Therefore, it is easy to see the probability that some $\lceil \log_m (a_n) \rceil$ is even will be $1-\tfrac{1}{m}+\tfrac{1}{m^2}-\tfrac{1}{m^3}+\ldots$ and the probability it will be odd is $\tfrac{1}{m}-\tfrac{1}{m^2}+\tfrac{1}{m^3}-\tfrac{1}{m^4}+\ldots.$ I know that the expected probability that the sum of all of the $\log$ expressions is even is equal to the expected probability that we have an even amount of odd $\log$ expressions. We do not need to consider when there are an odd amount of $\log$ expressions because if we do, the expression will never be even since there are an even number of $\log$ expressions. However, I'm not very sure how to find the probability that we have an odd amount of $\log$ expressions. May I have some help? Thanks in advance.

REPLY [3 votes]: Let $$A = \lceil \log_2 (a_1) \rceil + \lceil \log_4(a_2)\rceil + \ldots + \lceil \log_{1000} (a_{500})\rceil$$
Note that
$$-A =  \lfloor-\log_2 (a_1) \rfloor + \lfloor -\log_4(a_2)\rfloor + \ldots + \lfloor -\log_{1000} (a_{500})\rfloor$$
which does not change the parity, so we'll work with $-A$ instead. For $a_i \sim \text{Unif}(0, 1)$, we have
$$Y_{ij} := -\log_j(a_i) \sim \text{Exp}(\log(j))$$
and therefore
$$Z_{ij} := \lfloor Y_{ij}\rfloor \sim \text{Geometric}\left(1 - \frac{1}{j}\right)$$
Therefore the probability generating function of $-A$ is
\begin{align*}
G_{-A}(t) = \prod_{i=1}^{500}G_{Z_{i, 2i}}(t) = \prod_{i=1}^{500}\left(\frac{1 - \frac{1}{2i}}{1 - \frac{1}{2i}t}\right)
\end{align*}
The probability of $-A$ being even is
\begin{align*}
\mathbb{P}(-A \text{ is even}) = \frac{G_{-A}(1) + G_{-A}(-1)}{2} = \frac{1 + \frac{1}{1001}}{2} = \frac{501}{1001}
\end{align*}
{"set_name": "stack_exchange", "score": 3, "question_id": 4423264}