5
$\begingroup$

From my intro to probability theory book: What is the probability that a randomly selected positive integer will give a number ending in 1 if it is squared? Hint: It is enough to consider the 1 digit numbers. Answer: 0.2

I do not understand why we only need to consider one digit numbers. I see that 1 & 9 are the one digit numbers that produces a square ending in 1, giving a probability of 2/10 of randomly selecting them, but how can we generalize this to all positive integers?

$\endgroup$
  • 2
    $\begingroup$ Hint: the final digit in the product of any two integers will always equal the product of the final digit in each of the two integers - let me know in the comments if you're still having trouble and I can come back and provide a more comprehensive answer. $\endgroup$ – Colin T Bowers Mar 28 '14 at 3:47
8
$\begingroup$

In fact that answer is not sufficiently justified given the information in the question.

It depends on the distribution over the positive integers. The question says "randomly chosen", and the burning question is "what the heck does that mean"?

The positive integers can't all be chosen with equal probability*, so the answer therefore depends on how you assign probability to the original set of positive integers.

* (if they think it's possible, they're welcome to attempt to explain how one actually does that, which might be fun to watch)

Even the Hint doesn't pin it down.

Let's consider the 1-digit integers, and the last digit of their squares:

 1  2  3  4  5  6  7  8  9  0
 1  4  9  6  5  6  9  4  1  0

No doubt they're saying "well, all those last digits have an equal chance of turning up, and so the chance that a square ends in 1 is 2/10. But there's no reasonable basis on which to assert that the last digits do have an equal chance of turning up.

For example, if we toss a coin until we observe a head, and count the number of tosses, that will give a distribution over the integers. With that distribution, the chance is a little over 0.5:

$$p = (\frac{1}{2}+(\frac{1}{2})^9)(1 + (\frac{1}{2})^{10} + (\frac{1}{2})^{20} +...)$$

$$ = \frac{1}{2}\frac{1+(\frac{1}{2})^{10}}{1 - (\frac{1}{2})^{10}}$$

Other answers are possible.

Now it's possible to find distributions for which 0.2 is the right answer, and it's even possible to come up with distributions for which you can immediately work it out from the above table of single digits and the knowledge of the distribution (most obviously, any distribution where the ratios on the single digits are preserved throughout the integers) - but the distributions for which it works are generally substantially less "obvious" or "natural" than say a geometric($\frac{1}{2}$) distribution, like the one I used above.

$\endgroup$
  • $\begingroup$ Could you please explain in more detail how you got the first line of your equation? What do the exponents represent? $\endgroup$ – AYD Mar 28 '14 at 17:43
  • 1
    $\begingroup$ (+1) Although I have offered a different answer--on the premise it might indeed be "fun to watch"--there is much wisdom in this one; careful study of its points would be worthwhile. $\endgroup$ – whuber Mar 28 '14 at 18:54
6
$\begingroup$

When a mathematician asks to pick a "random integer" or "random natural number," they usually have in mind a limiting process in which the numbers all "become equally probable." The process can be quite general: I believe all that you need is that (a) the relative probabilities of any two sets should converge and (b) the relative probabilities of any two finite sets should converge to the ratio of their cardinalities.

One nice set of distributions with these properties is the geometric, where the chance of $k\ge 1$ is given by

$${\Pr}_x(k) = (1-x)x^{k-1}$$

for a parameter $0 \lt x \lt 1$ and values $k\in \{1,2,\ldots\}.$ The figure plots these distributions for $x=0.9, 0.99, 0.999$ and $1\le k\le 100$: as $x$ gets close to $1$, the distributions gets flatter and flatter: more and more uniform.

Figure

The advantage of this particular family of probability measures is that the probability of any set $A$ of positive integers, such as those whose squares end in "1", is the limiting value of

$${\Pr}_x(A) = (1-x)\sum_{k\in A} x^{k-1}$$

as $x\to 1.$ This limiting value, which appears to be the product of something going to $0$ (that is, $1-x$) and something that is growing infinitely large (the unnormalized chance of $A$ as given by the sum), often can easily be computed using L'Hopital's Rule. Let's illustrate with the question in hand, where

$$A=\{1,9,11,19,21,\ldots\}=\{10i+1\ |\ i \ge 0\}\cup\{10i+9\ |\ i \ge 0\} = A_1\cup A_9.$$

Because $A_1$ and $A_9$ are disjoint, this breaks the probability calculation into two parts:

$${\Pr}_x(A) = {\Pr}_x(A_1) + {\Pr}_x(A_9) = (1-x)\left(\sum_{i=0}^\infty x^{10i+1} + \sum_{i=0}^\infty x^{10i+9}\right).$$

Both of these sums are geometric series with common ratios $x^{10},$ which reduces them to

$${\Pr}_x(A) = (1-x)\left(\frac{x}{1-x^{10}} + \frac{x^9}{1-x^{10}}\right) = \frac{(1-x)(x+x^9)}{1-x^{10}}.$$

Because both the numerator and the denominator of this fraction converge to $0$ as $x\to 1,$ L'Hopital's Rule says the limit can be found as the limiting ratio of the derivatives of the numerator and denominator:

$$\lim_{x\to 1}{\Pr}_x(A) = \lim_{x\to 1} \frac{1 - 2x + 9x^8 - 10x^9}{-10x^{9}} = \frac{-2}{-10}=\frac{2}{10}.$$

Clearly we did not just "consider only one-digit numbers" in the calculation--all the positive integers were involved--but because $A_1$ and $A_9$ are defined only in terms of the final digits ($1$ and $9$ respectively), in that sense we only have to be concerned about the final digits (in this particular problem).

$\endgroup$
  • 2
    $\begingroup$ +1 A very nice take on the question. While the limiting geometric is one of the cases where you can "work it out from the above table of single digits and the knowledge of the distribution" (as I mention in my answer), it is arguably a limiting case that would be 'natural' to consider. $\endgroup$ – Glen_b Mar 28 '14 at 23:46
1
$\begingroup$

I think the solution is simply as this: every number has only ten possible last digits, which is all that matters to tell if a number ends at 1. Thus, if you select a number at random, the last digit has only ten possibilities, and that's what makes your sample space: you only focus on the last digit. Every number has only ten possible last digits, all with equal probability of appearing: $\Omega=\{0,1,2,...,9\}$, for which the favorable elements for your problem are 1 and 9; thus $P = 2/10 = 0.2$.

$\endgroup$
  • 1
    $\begingroup$ This answer is invalid because it confuses the sample space with a random variable. The sample space is explicitly the set of "positive integers." The fact that the random variable only has ten possible values does not assure they are equally probable! As a counterexample, contemplate the similar random variable given by the last digit of $x^2+x$. Although the "last digit has ten possibilities," only three values actually arise: $0$, $2$, or $6$. What would you say their chances are: $1/10$ or $1/3$? Neither is plausible under most reasonable probability models for this question. $\endgroup$ – whuber Mar 28 '14 at 15:53
  • 1
    $\begingroup$ I'm not confusing the sample space; I just narrowed it down to ten which are the numbers that matter in the context of the problem (the last ten possible digits of any positive integer). I understand the need to try to go with a full theoretical answer, but the intuitive idea is what I just wrote. $\endgroup$ – Néstor Mar 28 '14 at 16:40
  • 1
    $\begingroup$ That's exactly the confusion: the sample space does not change. The question concerns the random variable equal to $k^2\mod 10$ for $k\in\{1,2,\ldots\}$. It explicitly does not concern just the numbers $\{1,2,\ldots,9,0\}$. My counterexample shows what can go wrong when you ignore this crucial distinction. $\endgroup$ – whuber Mar 28 '14 at 16:42
  • 2
    $\begingroup$ I was afraid you would make that objection, so I need to introduce a more complicated counterexample. What is the chance that a randomly chosen prime integer will end in 1? Seemingly this question, too, depends only on the last digit. The answer--$1/4$--is fairly deep; it is an instance of Dirichlet's theorem on arithmetic progressions. Once again I have to insist on maintaining the crucial distinction between a sample space and the range of a random variable. By overlooking that distinction you obtained the correct answer purely by luck and intuition but not by objectively valid reasoning. $\endgroup$ – whuber Mar 28 '14 at 18:51
  • 2
    $\begingroup$ @whuber: almost a year has passed and my mind went back to this episode. After thinking a lot about it, I definetly believe that you are right and I was wrong about my solution. Your answer, BTW, is superb :). $\endgroup$ – Néstor Mar 22 '15 at 20:05

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.