Would an infinite random sequence of real numbers contain repetitions?
$begingroup$
If random real numbers are selected from the set of all real numbers, for an infinite number of iterations, what is the likelihood of repetitions occurring?
sequences-and-series infinity
$endgroup$
add a comment |
$begingroup$
If random real numbers are selected from the set of all real numbers, for an infinite number of iterations, what is the likelihood of repetitions occurring?
sequences-and-series infinity
$endgroup$
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
1
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
4
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
1
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00
add a comment |
$begingroup$
If random real numbers are selected from the set of all real numbers, for an infinite number of iterations, what is the likelihood of repetitions occurring?
sequences-and-series infinity
$endgroup$
If random real numbers are selected from the set of all real numbers, for an infinite number of iterations, what is the likelihood of repetitions occurring?
sequences-and-series infinity
sequences-and-series infinity
edited Apr 13 '16 at 6:07
mattecapu
695618
695618
asked Apr 12 '16 at 23:38
Jing WangJing Wang
312
312
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
1
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
4
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
1
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00
add a comment |
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
1
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
4
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
1
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
1
1
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
4
4
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
1
1
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
There is no such thing as "random real numbers selected from the set of all real numbers". Assuming what you mean is that you are taking independent samples $X_n$ from some continuous probability distribution, then yes, for any fixed $n ne m$, the probability $mathbb P(X_n = X_m)$ that $X_n = X_m$ is $0$, and so by countable additivity the probability of a repeat is also $0$.
$endgroup$
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
|
show 4 more comments
$begingroup$
It's very hard to say just how to select a "random real number". Even selecting a random positive integer is tricky - any individual number will be chosen with zero probability.
So this is not an official mathematical answer to your question, since you haven't specified the selection method:
I'm quite sure that any reasonable way you do it you'll find the likelihood of repetitions is zero. @fleablood 's comment explains why. The probability for any particular number must be $0$ so the probability of a repeat in any finite sequence is $0$. That will also be true for any countable sequence.
The question does kind of specify countability when it says "an infinite number of iterations" but if that infinity is the cardinality of $mathbb{R}$ the question is much murkier.
$endgroup$
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
add a comment |
$begingroup$
(I read the problem too quickly and my entire first attempt was way off. Feel free to skip past the part that I've indented with block-quotes)
HINT: I would look at what happens when you pick numbers from "1" to
"n", find a function that shows what happens when you repeat "n"
times, then find the limit as "n" goes to infinity.
Do you know how to set this up?
ORIGINAL EDIT "No I don't know how to" Very well then, let's start
with $n=5$
a) If you are referring to repetition anywhere in the sequence, then
sequences like 1-4-3-5-3 or 2-5-4-1-2 would all count, leaving only
the sequences that only contain each number one time: 1-3-4-2-5,
2-4-3-5-1, 5-3-4-1-2...
Out of the total $5^5 = 3125$ combinations, this leaves $5! =
> 5*4*3*2*1 = 120$ that do not repeat contain repetition against
$3125-120 = 3005$ combinations that do (3.84% without repetition,
96.16% with). Whereas if $n=10$, then we have $10^{10} = 10$ billion combinations, only $10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800$ of which
use each number exactly once without repetition (0.036288% without
repetition, 99.963712% with).
As $n$ gets larger and larger, the probability $frac{n!}{n^n}$ that
each number from 1 to $n$ is used once and only once approaches 0,
approaching a 100% chance as $n$ approaches infinity that there will
be at least one repetition at some point in the sequence.
b) Or, if you only mean repetition from one number to the next
(1-3-4-1-5 doesn't count as repetition, but 2-3-3-1-4 does), then you
have $n-1$ pairs of adjacent numbers and a $frac{1}{n}$ chance that
any given pair is a match (whatever the first number is, there are $n$
possibilities for what the next one will be).
The odds that one given pair does not match are
$frac{n-1}{n}=1-frac{1}{n}$, and the odds that none of the $n-1$
pairs match equals $(frac{n-1}{n})^{n-1}= (1-frac{1}{n})^{n-1}$. Do
you know how to find $lim limits_{n to ∞}(1-frac{1}{n})^{n-1}$?
2nd EDIT: And I just realized I was supposed to be going by "all real numbers" in my previous two examples.
In any case, the set of all real numbers (integer, rational, irrational algebraic, irrational transcendental) is uncountably infinite, whereas the length of the sequence (the first number, the second, the third ... the billionth ... the googol-th ...) would be countably infinite.
Both versions of repetition that I looked at would actually have a 0% chance of occurring.
$endgroup$
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1739927%2fwould-an-infinite-random-sequence-of-real-numbers-contain-repetitions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There is no such thing as "random real numbers selected from the set of all real numbers". Assuming what you mean is that you are taking independent samples $X_n$ from some continuous probability distribution, then yes, for any fixed $n ne m$, the probability $mathbb P(X_n = X_m)$ that $X_n = X_m$ is $0$, and so by countable additivity the probability of a repeat is also $0$.
$endgroup$
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
|
show 4 more comments
$begingroup$
There is no such thing as "random real numbers selected from the set of all real numbers". Assuming what you mean is that you are taking independent samples $X_n$ from some continuous probability distribution, then yes, for any fixed $n ne m$, the probability $mathbb P(X_n = X_m)$ that $X_n = X_m$ is $0$, and so by countable additivity the probability of a repeat is also $0$.
$endgroup$
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
|
show 4 more comments
$begingroup$
There is no such thing as "random real numbers selected from the set of all real numbers". Assuming what you mean is that you are taking independent samples $X_n$ from some continuous probability distribution, then yes, for any fixed $n ne m$, the probability $mathbb P(X_n = X_m)$ that $X_n = X_m$ is $0$, and so by countable additivity the probability of a repeat is also $0$.
$endgroup$
There is no such thing as "random real numbers selected from the set of all real numbers". Assuming what you mean is that you are taking independent samples $X_n$ from some continuous probability distribution, then yes, for any fixed $n ne m$, the probability $mathbb P(X_n = X_m)$ that $X_n = X_m$ is $0$, and so by countable additivity the probability of a repeat is also $0$.
edited Apr 13 '16 at 1:13
answered Apr 13 '16 at 0:05
Robert IsraelRobert Israel
322k23212465
322k23212465
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
|
show 4 more comments
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
1
1
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
$begingroup$
Even if the probability is zero wouldn't that only mean the probability that "the next number chosen is the same as the previous one" is zero? And that with an infinitely large sequence, everything would occur in every order, including an infinite sequence of identical numbers?
$endgroup$
– Jing Wang
Apr 13 '16 at 1:08
2
2
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
$begingroup$
No, for every $m ne n$, the probability that the $m$'th and $n$'th are the same is $0$. The probability of the union of countably many events, each of probability $0$, is $0$. That's called countable additivity.
$endgroup$
– Robert Israel
Apr 13 '16 at 1:13
4
4
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
$begingroup$
@JingWang: You're only selecting countably many of them.
$endgroup$
– user2357112
Apr 13 '16 at 1:47
1
1
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
$begingroup$
@ChrisMoore: No. This answer assumes that the OP intended a continuous probability distribution, where the probability of any specific value is 0. No such distribution exists over the natural numbers, so such an assumption would clearly be false there. (To see why, we can apply the same countable additivity that the answer mentions: if the probability of each natural number is 0, then the total probability of all natural numbers would have to be zero.) [continued]
$endgroup$
– ruakh
Apr 13 '16 at 5:26
1
1
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
$begingroup$
@ChrisMoore: [continued] So if we limit ourselves to the natural numbers, then at least one number n must have nonzero probability, in which case the probability goes to 1 that n appears multiple times.
$endgroup$
– ruakh
Apr 13 '16 at 5:28
|
show 4 more comments
$begingroup$
It's very hard to say just how to select a "random real number". Even selecting a random positive integer is tricky - any individual number will be chosen with zero probability.
So this is not an official mathematical answer to your question, since you haven't specified the selection method:
I'm quite sure that any reasonable way you do it you'll find the likelihood of repetitions is zero. @fleablood 's comment explains why. The probability for any particular number must be $0$ so the probability of a repeat in any finite sequence is $0$. That will also be true for any countable sequence.
The question does kind of specify countability when it says "an infinite number of iterations" but if that infinity is the cardinality of $mathbb{R}$ the question is much murkier.
$endgroup$
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
add a comment |
$begingroup$
It's very hard to say just how to select a "random real number". Even selecting a random positive integer is tricky - any individual number will be chosen with zero probability.
So this is not an official mathematical answer to your question, since you haven't specified the selection method:
I'm quite sure that any reasonable way you do it you'll find the likelihood of repetitions is zero. @fleablood 's comment explains why. The probability for any particular number must be $0$ so the probability of a repeat in any finite sequence is $0$. That will also be true for any countable sequence.
The question does kind of specify countability when it says "an infinite number of iterations" but if that infinity is the cardinality of $mathbb{R}$ the question is much murkier.
$endgroup$
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
add a comment |
$begingroup$
It's very hard to say just how to select a "random real number". Even selecting a random positive integer is tricky - any individual number will be chosen with zero probability.
So this is not an official mathematical answer to your question, since you haven't specified the selection method:
I'm quite sure that any reasonable way you do it you'll find the likelihood of repetitions is zero. @fleablood 's comment explains why. The probability for any particular number must be $0$ so the probability of a repeat in any finite sequence is $0$. That will also be true for any countable sequence.
The question does kind of specify countability when it says "an infinite number of iterations" but if that infinity is the cardinality of $mathbb{R}$ the question is much murkier.
$endgroup$
It's very hard to say just how to select a "random real number". Even selecting a random positive integer is tricky - any individual number will be chosen with zero probability.
So this is not an official mathematical answer to your question, since you haven't specified the selection method:
I'm quite sure that any reasonable way you do it you'll find the likelihood of repetitions is zero. @fleablood 's comment explains why. The probability for any particular number must be $0$ so the probability of a repeat in any finite sequence is $0$. That will also be true for any countable sequence.
The question does kind of specify countability when it says "an infinite number of iterations" but if that infinity is the cardinality of $mathbb{R}$ the question is much murkier.
edited Apr 12 '16 at 23:54
answered Apr 12 '16 at 23:44
Ethan BolkerEthan Bolker
42.7k549113
42.7k549113
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
add a comment |
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
Would it be okay to say the probability of iteration n being a repeat is that r_n is one of n values and the probability of that is 0. The probability of a repeat never happening is lim 1 -0^n = 1. I'd accept that, would you?
$endgroup$
– fleablood
Apr 12 '16 at 23:48
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
$begingroup$
@fleablood Interesting question. See my edit.
$endgroup$
– Ethan Bolker
Apr 12 '16 at 23:55
add a comment |
$begingroup$
(I read the problem too quickly and my entire first attempt was way off. Feel free to skip past the part that I've indented with block-quotes)
HINT: I would look at what happens when you pick numbers from "1" to
"n", find a function that shows what happens when you repeat "n"
times, then find the limit as "n" goes to infinity.
Do you know how to set this up?
ORIGINAL EDIT "No I don't know how to" Very well then, let's start
with $n=5$
a) If you are referring to repetition anywhere in the sequence, then
sequences like 1-4-3-5-3 or 2-5-4-1-2 would all count, leaving only
the sequences that only contain each number one time: 1-3-4-2-5,
2-4-3-5-1, 5-3-4-1-2...
Out of the total $5^5 = 3125$ combinations, this leaves $5! =
> 5*4*3*2*1 = 120$ that do not repeat contain repetition against
$3125-120 = 3005$ combinations that do (3.84% without repetition,
96.16% with). Whereas if $n=10$, then we have $10^{10} = 10$ billion combinations, only $10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800$ of which
use each number exactly once without repetition (0.036288% without
repetition, 99.963712% with).
As $n$ gets larger and larger, the probability $frac{n!}{n^n}$ that
each number from 1 to $n$ is used once and only once approaches 0,
approaching a 100% chance as $n$ approaches infinity that there will
be at least one repetition at some point in the sequence.
b) Or, if you only mean repetition from one number to the next
(1-3-4-1-5 doesn't count as repetition, but 2-3-3-1-4 does), then you
have $n-1$ pairs of adjacent numbers and a $frac{1}{n}$ chance that
any given pair is a match (whatever the first number is, there are $n$
possibilities for what the next one will be).
The odds that one given pair does not match are
$frac{n-1}{n}=1-frac{1}{n}$, and the odds that none of the $n-1$
pairs match equals $(frac{n-1}{n})^{n-1}= (1-frac{1}{n})^{n-1}$. Do
you know how to find $lim limits_{n to ∞}(1-frac{1}{n})^{n-1}$?
2nd EDIT: And I just realized I was supposed to be going by "all real numbers" in my previous two examples.
In any case, the set of all real numbers (integer, rational, irrational algebraic, irrational transcendental) is uncountably infinite, whereas the length of the sequence (the first number, the second, the third ... the billionth ... the googol-th ...) would be countably infinite.
Both versions of repetition that I looked at would actually have a 0% chance of occurring.
$endgroup$
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
|
show 1 more comment
$begingroup$
(I read the problem too quickly and my entire first attempt was way off. Feel free to skip past the part that I've indented with block-quotes)
HINT: I would look at what happens when you pick numbers from "1" to
"n", find a function that shows what happens when you repeat "n"
times, then find the limit as "n" goes to infinity.
Do you know how to set this up?
ORIGINAL EDIT "No I don't know how to" Very well then, let's start
with $n=5$
a) If you are referring to repetition anywhere in the sequence, then
sequences like 1-4-3-5-3 or 2-5-4-1-2 would all count, leaving only
the sequences that only contain each number one time: 1-3-4-2-5,
2-4-3-5-1, 5-3-4-1-2...
Out of the total $5^5 = 3125$ combinations, this leaves $5! =
> 5*4*3*2*1 = 120$ that do not repeat contain repetition against
$3125-120 = 3005$ combinations that do (3.84% without repetition,
96.16% with). Whereas if $n=10$, then we have $10^{10} = 10$ billion combinations, only $10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800$ of which
use each number exactly once without repetition (0.036288% without
repetition, 99.963712% with).
As $n$ gets larger and larger, the probability $frac{n!}{n^n}$ that
each number from 1 to $n$ is used once and only once approaches 0,
approaching a 100% chance as $n$ approaches infinity that there will
be at least one repetition at some point in the sequence.
b) Or, if you only mean repetition from one number to the next
(1-3-4-1-5 doesn't count as repetition, but 2-3-3-1-4 does), then you
have $n-1$ pairs of adjacent numbers and a $frac{1}{n}$ chance that
any given pair is a match (whatever the first number is, there are $n$
possibilities for what the next one will be).
The odds that one given pair does not match are
$frac{n-1}{n}=1-frac{1}{n}$, and the odds that none of the $n-1$
pairs match equals $(frac{n-1}{n})^{n-1}= (1-frac{1}{n})^{n-1}$. Do
you know how to find $lim limits_{n to ∞}(1-frac{1}{n})^{n-1}$?
2nd EDIT: And I just realized I was supposed to be going by "all real numbers" in my previous two examples.
In any case, the set of all real numbers (integer, rational, irrational algebraic, irrational transcendental) is uncountably infinite, whereas the length of the sequence (the first number, the second, the third ... the billionth ... the googol-th ...) would be countably infinite.
Both versions of repetition that I looked at would actually have a 0% chance of occurring.
$endgroup$
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
|
show 1 more comment
$begingroup$
(I read the problem too quickly and my entire first attempt was way off. Feel free to skip past the part that I've indented with block-quotes)
HINT: I would look at what happens when you pick numbers from "1" to
"n", find a function that shows what happens when you repeat "n"
times, then find the limit as "n" goes to infinity.
Do you know how to set this up?
ORIGINAL EDIT "No I don't know how to" Very well then, let's start
with $n=5$
a) If you are referring to repetition anywhere in the sequence, then
sequences like 1-4-3-5-3 or 2-5-4-1-2 would all count, leaving only
the sequences that only contain each number one time: 1-3-4-2-5,
2-4-3-5-1, 5-3-4-1-2...
Out of the total $5^5 = 3125$ combinations, this leaves $5! =
> 5*4*3*2*1 = 120$ that do not repeat contain repetition against
$3125-120 = 3005$ combinations that do (3.84% without repetition,
96.16% with). Whereas if $n=10$, then we have $10^{10} = 10$ billion combinations, only $10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800$ of which
use each number exactly once without repetition (0.036288% without
repetition, 99.963712% with).
As $n$ gets larger and larger, the probability $frac{n!}{n^n}$ that
each number from 1 to $n$ is used once and only once approaches 0,
approaching a 100% chance as $n$ approaches infinity that there will
be at least one repetition at some point in the sequence.
b) Or, if you only mean repetition from one number to the next
(1-3-4-1-5 doesn't count as repetition, but 2-3-3-1-4 does), then you
have $n-1$ pairs of adjacent numbers and a $frac{1}{n}$ chance that
any given pair is a match (whatever the first number is, there are $n$
possibilities for what the next one will be).
The odds that one given pair does not match are
$frac{n-1}{n}=1-frac{1}{n}$, and the odds that none of the $n-1$
pairs match equals $(frac{n-1}{n})^{n-1}= (1-frac{1}{n})^{n-1}$. Do
you know how to find $lim limits_{n to ∞}(1-frac{1}{n})^{n-1}$?
2nd EDIT: And I just realized I was supposed to be going by "all real numbers" in my previous two examples.
In any case, the set of all real numbers (integer, rational, irrational algebraic, irrational transcendental) is uncountably infinite, whereas the length of the sequence (the first number, the second, the third ... the billionth ... the googol-th ...) would be countably infinite.
Both versions of repetition that I looked at would actually have a 0% chance of occurring.
$endgroup$
(I read the problem too quickly and my entire first attempt was way off. Feel free to skip past the part that I've indented with block-quotes)
HINT: I would look at what happens when you pick numbers from "1" to
"n", find a function that shows what happens when you repeat "n"
times, then find the limit as "n" goes to infinity.
Do you know how to set this up?
ORIGINAL EDIT "No I don't know how to" Very well then, let's start
with $n=5$
a) If you are referring to repetition anywhere in the sequence, then
sequences like 1-4-3-5-3 or 2-5-4-1-2 would all count, leaving only
the sequences that only contain each number one time: 1-3-4-2-5,
2-4-3-5-1, 5-3-4-1-2...
Out of the total $5^5 = 3125$ combinations, this leaves $5! =
> 5*4*3*2*1 = 120$ that do not repeat contain repetition against
$3125-120 = 3005$ combinations that do (3.84% without repetition,
96.16% with). Whereas if $n=10$, then we have $10^{10} = 10$ billion combinations, only $10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800$ of which
use each number exactly once without repetition (0.036288% without
repetition, 99.963712% with).
As $n$ gets larger and larger, the probability $frac{n!}{n^n}$ that
each number from 1 to $n$ is used once and only once approaches 0,
approaching a 100% chance as $n$ approaches infinity that there will
be at least one repetition at some point in the sequence.
b) Or, if you only mean repetition from one number to the next
(1-3-4-1-5 doesn't count as repetition, but 2-3-3-1-4 does), then you
have $n-1$ pairs of adjacent numbers and a $frac{1}{n}$ chance that
any given pair is a match (whatever the first number is, there are $n$
possibilities for what the next one will be).
The odds that one given pair does not match are
$frac{n-1}{n}=1-frac{1}{n}$, and the odds that none of the $n-1$
pairs match equals $(frac{n-1}{n})^{n-1}= (1-frac{1}{n})^{n-1}$. Do
you know how to find $lim limits_{n to ∞}(1-frac{1}{n})^{n-1}$?
2nd EDIT: And I just realized I was supposed to be going by "all real numbers" in my previous two examples.
In any case, the set of all real numbers (integer, rational, irrational algebraic, irrational transcendental) is uncountably infinite, whereas the length of the sequence (the first number, the second, the third ... the billionth ... the googol-th ...) would be countably infinite.
Both versions of repetition that I looked at would actually have a 0% chance of occurring.
edited Apr 14 '16 at 12:57
answered Apr 13 '16 at 1:17
Simpson17866Simpson17866
3672513
3672513
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
|
show 1 more comment
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
1
1
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
No I don't know how to
$endgroup$
– Jing Wang
Apr 13 '16 at 4:58
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
$begingroup$
@JingWang Just finished elaborating.
$endgroup$
– Simpson17866
Apr 13 '16 at 16:16
1
1
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
I think there's a problem with this answer. You seem to be assuming that the first $n$ numbers in the sequence are chosen from ${1, ldots, n}$. In that case the probability that you have a permutation does in fact approach $0$. But in fact each segment of length $n$ is a random sequence of $n$ real numbers of any size.
$endgroup$
– Ethan Bolker
Apr 14 '16 at 0:01
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
$begingroup$
@EthanBolker It seemed like first seeing what the functions would look like with finite numbers, secondly seeing what happens when we take the limit as the numbers approach infinity, would work better than inventing infinite functions from scratch.
$endgroup$
– Simpson17866
Apr 14 '16 at 4:09
1
1
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
$begingroup$
@Simpson17866 thank you for showing this, however it seems like you are talking about Natural numbers rather than Real numbers? (I guess you've answered my second question before I even asked it).
$endgroup$
– Jing Wang
Apr 14 '16 at 5:11
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1739927%2fwould-an-infinite-random-sequence-of-real-numbers-contain-repetitions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I'm pretty sure it is 0. For a repitition to occur at iteration n then that means r_n is one of the n previous. The probability of that is n/card(Real) = 0. The sum of these 0 probabilities is 0.
$endgroup$
– fleablood
Apr 12 '16 at 23:44
1
$begingroup$
infinite like countably infinite? uncountably infinite? which uncountable infinite then?
$endgroup$
– mattecapu
Apr 13 '16 at 5:52
4
$begingroup$
How the random selection is done may well matter; e.g., selection by means of some algorithm (since the set of computable reals is countable, unlike $mathbb{R}$). Note that "random" does not imply a uniform distribution.
$endgroup$
– r.e.s.
Apr 13 '16 at 6:12
$begingroup$
Perhaps I mean each choice is independent of the others, if that helps?
$endgroup$
– Jing Wang
Apr 13 '16 at 7:35
1
$begingroup$
@mattecapu Good point. For 2^$aleph_0$ iterations p=1.
$endgroup$
– Peter A. Schneider
Apr 13 '16 at 8:00