Wikipedia:Reference desk/Archives/Mathematics/2023 September 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 20

Random integer factors

What is the probability that one integer chosen at random is a factor of another integer chosen at random? Jack of Oz ^{[pleasantries]} 21:59, 20 September 2023 (UTC)

It depends on how you're choosing the integers. Since there are infinitely many integers, there's no way to uniformly choose an arbitrary integer, so you'll have to specify a probability distribution first. Let's just assume a generic distribution $P$ for now.

You only have the scenarios that X divides Y and X < Y, X equals Y, Y divides X and X > Y. Note that $x|y,y>x$ for $x\geq 1$ if and only if $y=nx$ for $n>1$. This means that you can write out the probability as:

$\sum _{x=1}^{\infty }\sum _{n=2}^{\infty }P(X=x)P(Y=nx)+\sum _{x=1}^{\infty }P(X=x)P(Y=x)+\sum _{y=1}^{\infty }\sum _{n=2}^{\infty }P(X=ny)P(Y=y)$

If we assume, rather reasonably, that you use the same probabilities for X as you do for Y, then the first and third term are equal, so you get:

$\sum _{x=1}^{\infty }P(x)^{2}+2\sum _{x=1}^{\infty }\sum _{n=2}^{\infty }P(x)P(nx)=\sum _{x=1}^{\infty }P(x)^{2}+2\sum _{x=1}^{\infty }P(x)(\sum _{n=2}^{\infty }P(nx))$

GalacticShoe (talk) 23:10, 20 September 2023 (UTC)

Unfortunately, the aforementioned equation doesn't lend itself very well to closed-form formulas. As an example, using a geometric distribution of parameter $p$ yields a probability of ${\frac {p}{2-p}}+{\frac {2p^{2}}{(1-p)^{2}}}\sum _{x=1}^{\infty }{\frac {1}{({\frac {1}{1-p}})^{3m}-({\frac {1}{1-p}})^{2m}}}$, which doesn't seem to have a nice closed-form equivalent. Probably purely by coincidence though, the sum for any given $0<p<1$ looks close to ${\sqrt {1-(p-1)^{2}}}$ (which yields a quarter circle.) When $p={\frac {1}{2}}$, the sum is equivalent to ${\frac {1}{3}}+2\sum _{x=1}^{\infty }{\frac {1}{8^{m}-4^{m}}}=\sum _{x=1}^{\infty }{\frac {1}{4^{m}}}(1+{\frac {2}{2^{m}-1}})$, which converges rapidly to a value around $0.880057$. Compare that to ${\sqrt {1-({\frac {1}{2}}-1)^{2}}}={\sqrt {\frac {3}{4}}}\approx 0.866025$. In any case, Poisson distribution does not fare any better; it doesn't seem that there is a closed-form expression for $\sum _{n=2}^{\infty }P(nx)$, let alone $\sum _{x=1}^{\infty }P(x)(\sum _{n=2}^{\infty }P(nx))$. At the end of it all though, there is one thing that does seem to be pretty consistent, and that is that as these distributions "approach" uniformity, the probability tends towards $0$. I imagine that, in the same way that the probability of any two positive integers being coprime is ${\frac {6}{\pi ^{2}}}$, one can make an analogous notion that the probability of one positive integer being a factor of another is $0$. GalacticShoe (talk) 02:16, 21 September 2023 (UTC)

Another distribution is the discrete uniform distribution on the range $1,...,n.$ One can study how the divisor probability behaves as $n\to \infty .$ Given $n,$ the probability equals $p(n)={\frac {a(n)}{n^{2}}},$ in which $a(n)$ (sequence A006218 in the OEIS) counts the number of pairs $i,j$ in the range such that $i$ divides $j$ evenly. It is known that $a(n)\sim n\log n,$ so $p(n)\sim {\frac {\log n}{n}}\to 0.$  --Lambiam 18:27, 21 September 2023 (UTC)

Why not look at it this way: the larger integer never divides the smaller integer. The smaller integer, call it n, divides every nth integer, so it has a 1/n chance of dividing the larger integer. Bubba73 ^{You talkin' to me?} 20:57, 21 September 2023 (UTC)

That makes a lot more sense to my post-mathematical mind than the previous explanations. Thanks. -- Jack of Oz ^{[pleasantries]} 21:40, 21 September 2023 (UTC)

It's just that ${\frac {1}{n}}$ changes depending on what the smaller integer $n$ is, and that's where you start getting into the probabilistic weeds. In general, if you already know what one of the integers is, then you don't have to go through all the rigmarole from earlier. GalacticShoe (talk) 22:49, 21 September 2023 (UTC)

Why is ${\frac {1}{n}}$ relevant? Apart from one case out of an infinity of cases, n is always going to be greater than 1. -- Jack of Oz ^{[pleasantries]} 23:46, 21 September 2023 (UTC)

$1/n$ is the probability that if you "randomly select an integer", $n$ will divide that integer. As mentioned earlier there's no actual way to "randomly select an integer" in a way that makes every integer equally likely to be selected, but you can think of it as being that the "density" of integers that $n$ divides is $1/n$.

For example, the density of numbers that $2$ divides, i.e. the density of the even numbers, is $1/2$. That isn't to say that there are half as many even integers as there are integers overall (rather famously, there are an equal number of even integers as there are integers), but in an intuitive way -- and a way that can be formalized, although I won't get into it -- there are clearly half as many even integers in any reasonable sample of integers as there are integers total. This of course is the case for all $n$.

The major problem is that the statement "the probability of $n$ dividing an arbitrary integer is $1/n$" is only helpful if you fix $n$. So if you say "what's the probability that an integer A chosen at random divides another integer B chosen at random", then it's going to change with whatever the value of A is. And unfortunately, unlike the $1/n$ density argument, there's no intuitive way of determining probabilities of how $A$ will be chosen. In other words, earlier, we didn't specify how we would choose B, but we made the reasonable assumption that the probability of choosing B to a multiple of $n$ would be $1/n$. Here, we're choosing A to be some arbitrary integer with no constraints, and there's no simple assumption or heuristic you can use here. That's where the probability distribution from earlier comes in. The probability distribution $P$ is a function that takes in the integer $A$ and spits out a probability, $P(A)$, that $A$ is chosen.

This is why it gets so complicated. When we jump from "what's the probability that a fixed integer $n$ divides some random integer we choose" to "what's the probability that some random integer A divides another random integer we choose", then we have to add in a brand new function to choose a value for A, and that confounds calculation.

Also, I'm just realizing now that I interpreted the original question as being "what's the probability that A divides the other random integer B or B divides A." I'm not sure if that's what the original question meant or not, but in any case it's largely a matter of semantics, and it doesn't actually change that much about the calculation, so let's not worry too much about it. GalacticShoe (talk) 00:56, 22 September 2023 (UTC)

Oh, yea. If you are talking about two arbitrary integers, that may not have a definite answer. On the other hand, the chance that two arbitrary integers have a common factor > 1 is relatively easy to calculate, so maybe something similar could be done. Bubba73 ^{You talkin' to me?} 23:49, 21 September 2023 (UTC)

Yeah for sure, based on my earlier examination of what happens where integers are selected with the geometric distribution and with the Poisson distribution, and based on Lambiam's examination of the discrete uniform distribution, I'm pretty sure the probability tends to $0$, which makes sense; as $n$ increases, the probability of selecting a multiple of $n$ tends to 0, and as distributions "flatten out", they allow for greater relative probabilities of selecting larger $n$. GalacticShoe (talk) 01:00, 22 September 2023 (UTC)

Yes, thinking about it with all integers equally likely, I think the probability would be infintessimally small, i.e. zero. Bubba73 ^{You talkin' to me?} 01:26, 22 September 2023 (UTC)

But that's not the same as saying it's impossible, is it - because it's clearly possible. Just so unlikely as to be zero for all practical purposes. Correct? -- Jack of Oz ^{[pleasantries]} 13:17, 22 September 2023 (UTC)

It all cruciously depends on what it means to choose an integer "at random". There is no way to do that in such a way that every number has an equal chance of being chosen, since you cannot divide 1 (100%) into infinitely many equal parts that sum up to 1. If all numbers are possible choices, some have necessarily a larger chance of being chosen than some others; it just ain't fair. So to answer the question, we need to come up with another interpretation. We examined a variety of methods to make the selection less and less unfair, and for each the probability gets arbitrarily close to 0 without ever getting there. Since total fairness is impossible, it is not correct to assert that 0 is the answer to the original question. Under some deviously non-uniform ways of reducing the unfairness the answer may even be some value greater than 0.  --Lambiam 16:36, 22 September 2023 (UTC)

I love the word "cruciously". May I borrow it? -- Jack of Oz ^{[pleasantries]} 22:01, 22 September 2023 (UTC)

Sure. Cruciously means crucially and curiously. Curiously is the same as strangely. It's like the word slithe – there are two meanings packed up into one word.  --Lambiam 06:19, 23 September 2023 (UTC)

Adding onto Lambiam's answer, I want to note that in asking this question you've gotten to something at the very heart of probability itself. In most undergrad or non-math major courses on probability, there are two scenarios which you can encounter: either you have a finite/discrete number of outcomes, which you can assign probabilities to (for example, there are 6 numbers that you can roll on a die), or you have an infinite/continuous number of outcomes (for example, the amount of time between events occurring.) Naturally, for the former, it's very easy to think of assigning a probability to a single event. You clearly have a very tangible 1/6 probability of rolling any given number on a die. For the latter though, single events rarely ever have a nonzero probability. You cannot say with any reasonable probability that some event will happen, say, exactly 6.527... seconds into the future. Yet, somehow, the event does have to eventually occur, even if no specific time has a nonzero probability. In some ways this does seem paradoxical, but, like you said, for any given value it's clearly possible, just so unlikely as to be zero for all practical purposes.

Mathematicians circumvent this paradox by assigning probabilities to ranges of possible values rather than individual values. For example, if an event is guaranteed to happen at some uniformly random time between 0 and 1 second, then even if no individual time has a nonzero probability, the probability of the event happening between, say, 0.5 and 0.8 seconds is 30%. I'm pretty sure that the reason you can assign "uniform" probabilities to ranges of time (more generally, subsets of real numbers), is because it makes sense for a range of time to have a certain density in a larger range. As mentioned earlier, the range from 0.5 to 0.8 seconds is 30% of the range from 0 to 1 seconds. You can't do the same for finite sets of integers. The density of a finite set of integers within the whole set of integers is always going to be 0, so there is no analog for uniform probability there.

Now, you can narrow down to a specific time/real number by taking successively smaller ranges (with successively smaller probabilities.) You may be able to take infinite sets of integers with a certain density and keep taking subsets until you narrow down to a certain integer, but I struggle to imagine what that would look like. GalacticShoe (talk) 23:36, 22 September 2023 (UTC)

Very interesting. So, if I modify my original question to positive integers in the range 1 to 1,000,000, what's the probability that one's a factor of the other? -- Jack of Oz ^{[pleasantries]} 01:41, 23 September 2023 (UTC)

Assuming you draw the two numbers so that every number from 1 to 1,000,000 has equal probability, the probability that one's a factor of the other would be ${\frac {26940068}{1000000000000}}$, or $0.000026940068$, or $0.0026940068\%$. GalacticShoe (talk) 02:28, 23 September 2023 (UTC)

And if the two numbers are always different, I get 2.594009394 x 10^-5. Bubba73 ^{You talkin' to me?} 02:47, 23 September 2023 (UTC)

Excellent. Thanks, all. -- Jack of Oz ^{[pleasantries]} 23:27, 24 September 2023 (UTC)

Resolved

Here is a possible interpretation which gives the answer zero. Let f(n) be the probability if both integers are chosen uniformly from 1 to n for a specific finite n. Then f(n) tends to zero when n tends to infinite. PrimeHunter (talk) 23:09, 22 September 2023 (UTC)

This is the discrete uniform distribution I examined above.  --Lambiam 06:48, 23 September 2023 (UTC)

Now I understand why Lambian was working with probability distributions - you can't come up with much of an answer if you choose integers at random from all integers with them equally weighted. I suggest that a probably distribution in which the probabily of n being chosen is proportional to 1/n might work. This type of distribution is used in analysis of Benford's law. Bubba73 ^{You talkin' to me?} 23:26, 22 September 2023 (UTC)

The sum of 1/n tends to infinite (even over primes) so proportional to 1/n is not possible. It would still tend to infinite with any positive proportionality factor. If we want a decreasing probability for positive integers then the simplest solution may seem drastic: Let n have probability 1/2ⁿ. 1/2 + 1/4 + 1/8 + ... = 1. PrimeHunter (talk) 00:38, 23 September 2023 (UTC)

That is a very unfair distribution. With this distribution, the probability is approximately 0.60669515241529176378.  --Lambiam 06:45, 23 September 2023 (UTC)