0
$\begingroup$

I was watching a lecture in Coursera. And there, they used this result that
the probability of two random numbers to have the same oddity is $\mathit{\frac12}$.

I understood that "oddity" means the number of $2$s in the both random number.
That is,

Let $ a = 2^md$, and $ b = 2^nf$, where $d, f$ are odd numbers and $m,n, d, f \in \mathbb Z^+$. What is the probability that $m$ and $n$ are the same?

If anyone wants to check the original source then here is the link to the video (at time $19:07$).

Here are the weekly notes provided by the course. Turn to page $4$, first paragraph, lines $9-10$

Edit:
$a,b \in \{1,2,..N\}$ whrere $N\in \mathbb Z^+$

$\endgroup$
11
  • 6
    $\begingroup$ Do you mean "parity" ? $\endgroup$ – Peter Dec 29 '19 at 20:07
  • $\begingroup$ @Peter are they same? I mean Parity is whether a number is odd or even. But here mementioned Oddity is number of twos in the number. $\endgroup$ – Saptarshi Sahoo Dec 29 '19 at 20:13
  • 1
    $\begingroup$ OK, sorry, but I still do not understand : Do you mean the number of digits $2$ in both the random numbers ? Also : Which range do you assume ? If there is no bound, the number of digits $2$ is not bounded either. Not sure whether in this case, the question makes sense. $\endgroup$ – Peter Dec 29 '19 at 20:15
  • $\begingroup$ Yes number of digit two in both random number. Like lets take two random number n=2^as and m = 2^bq, s,q are odd numbers . what is the probability that a=b. $\endgroup$ – Saptarshi Sahoo Dec 29 '19 at 20:21
  • $\begingroup$ Direct quote. do not paraphrase and give context. This needs to be fixed if wrong. and which course, I can barely find a thing it could be. $\endgroup$ – user645636 Dec 29 '19 at 20:24
2
$\begingroup$

I think you're misunderstanding the video. (I'm not surprised; it's a bit hard to understand.)

He's talking about the “worst case” $k=l=1$, in which we have $mr_1=2s$ and $nr_2=2s_1$ (with $s$, $s_1$ odd). So there's only one factor of $2$ in either $m$ or $r_1$, and only one factor of $2$ in either $n$ or $r_2$. He then asks, for this worst case, not in general, what the probability is that $r_1$ and $r_2$ have the same number of factors of $2$. He talks about these numbers as “random” without specifying a distribution for them. This is rather questionable. But on the assumption that $m$, $r_1$, $n$ and $r_2$ are a priori all equally and independently likely to contain a factor of $2$, there are $4$ equally likely possibilities given that either $m$ or $r_1$ and either $n$ or $r_2$ contains a factor of $2$. In $2$ of these $4$ possibilities, $r_1$ and $r_2$ have the same number of factors of $2$ (either $0$ or $1$), and in the other two they don't (one has one factor of two and the other has none). Thus, in this worst case, the probability for $r_1$ and $r_2$ to have the same number of factors of $2$ is $\frac12$.

URL has shown in another answer that if the question were posed in general, not in this particular case, the answer (again under reasonable assumptions about the distribution) would be $\frac13$.

$\endgroup$
1
  • $\begingroup$ see my edited question. I missed the range of $a$ and $b$ before. $\endgroup$ – Saptarshi Sahoo Dec 30 '19 at 6:56
1
$\begingroup$

We don’t really use the term “oddity” to refer to what you’re talking about. A more formal term might be the “$2$-adic valuation”, denoted $\nu_2(n)$: this is the exponent of the greatest power of $2$ that divides $n$.

Furthermore, talking about a “random integer” doesn’t actually makes sense without further specification, as there’s no uniform distribution on the natural numbers. Nevertheless, we can talk about the behavior of random numbers from $1$ to $N$, as $N$ gets large.

Your result is wrong by the way, and this is quite easy to verify: two numbers having the same $\nu_2$ is a stronger condition than having the same parity, which occurs with limiting probability $\frac12$. But it doesn’t take too much work to fix it. Let $$P(N,k)= \frac{\lfloor\frac Nk\rfloor}N$$ be the probability of a number from $1$ to $N$ being a multiple of $k$. The probability of two numbers from $1$ to $N$ having the same $\nu_2$ will therefore be $$\sum_{k=0}^\infty \left(P\left(N,2^k\right)-P\left(N,2^{k+1}\right)\right)^2,$$ that is, the probability of both numbers having a $\nu_2$ of $0$, plus the probability of both numbers having a $\nu_2$ of $1$, and so on.

Notice also that $$\lim_{N\to\infty}P(N,k)=\frac1k.$$ This allows us to calculate our limiting probability, as $$\lim_{N\to\infty}\sum_{k=0}^\infty \left(P\left(N,2^k\right)-P\left(N,2^{k+1}\right)\right)^2=\sum_{k=0}^\infty \frac1{4^{k+1}}=\boxed{\frac13}.$$

$\endgroup$
4
  • $\begingroup$ But they have given answer 1/2 $\endgroup$ – Saptarshi Sahoo Dec 29 '19 at 21:29
  • $\begingroup$ @UzumakiSaptarshi $\frac12$ can’t possibly be the answer to the problem you describe: see my remark. $\endgroup$ – URL Dec 29 '19 at 21:31
  • $\begingroup$ see my edited question. I missed it before. $\endgroup$ – Saptarshi Sahoo Dec 30 '19 at 6:55
  • $\begingroup$ @UzumakiSaptarshi I think my answer still holds. If you want to talk about a specific $N$, you can simply not consider the last step, and plug the formula for $P\left(N,2^k\right)$ directly. $\endgroup$ – URL Dec 30 '19 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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