Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Yesterday I was trying to come up with an example of the weirdest sequence I could think of, and I came up with this. I'm not even sure if this could be called a sequence, but here it goes:

We'll define the sequence $a_n$ in the following way. We'll keep a list of previously calculated terms. Whenever we want to know $a_k$ for some $k$, we'll check if $a_k$ is in the list. If it is, we're done: that's its value. If it isn't, we roll a die, assign the number we get to $a_k$, and write that down in the list. This way, we can find out $a_k$ for any $k$ we want. For example, I just calculated some terms of it: $a_1 =1, a_2=4, a_{27}=1, a_{googol} = 5$.

There is an obvious problem with this definition, namely, that the sequence will be different each time someone different calculates it. I think a way to get past this would be to say that there will be a file on the Internet or something that keeps a list of all previously calculated terms of $a_n$. Another way would be, maybe, to talk not about the sequence itself (because it isn't unique, in a way) but of the probability of it having certain properties each time someone different calculates it.

My main question is: does this sequence have a limit? Or, to put it in the second way I just mentioned: what is the probability it will have a limit? What would happen if, instead of rolling a die, we pick a random real number for each term?

I'm sorry if this question doesn't make sense; I know practically nothing about the kind of math that would be needed to answer it. I don't even know how one would approach a problem like this, and I'm not sure this even counts as a sequence. This is something I randomly thought of, and I'm wondering if there is any previous work on problems like this.

share|improve this question
    
"Random" sequences are interesting and useful. It is not clear how $a_k$ is defined if "$a_k$ is in the list." –  André Nicolas Jun 30 '12 at 14:38
    
The way you've defined the sequence is needlessly complicated. Instead of forming it in chronological order (i.e. by increasing index), you seem to suggest a scenario where we iteratively pick $k$ randomly out of the naturals, and if we already know $a_k$ for the given $k$ we move on to the next choice of $k$, otherwise we roll a die and record the outcome as $a_k$. In addition to being superfluous there are two complications: what does it mean to randomly pick a natural number, and what of the logical possibility that there are terms in the sequence that never get defined! –  anon Jun 30 '12 at 14:43
    
(There's no need for the sequence to be "constructed" outside of chronological order, because the die rolls are independent anyway, and there's no point in allowing ourselves to pick the same index more than once if we're only going to do something with it the first time.) –  anon Jun 30 '12 at 14:45
    
@AndréNicolas: What I mean if that $a_k$ has already been calculated, there is no need to roll the die again. We just look at the list and check what was the value of $a_k$. –  Javier Badia Jun 30 '12 at 15:01
    
@anon: Making a needlessly complicated definition was sort of the point. Also, you don't necessarily have to choose $k$ randomly. You can start from $1$ and work your way up if you want; the point is not so much in what order the terms are calculated, but that you can calculate $a_k$ for any $k$ you want. –  Javier Badia Jun 30 '12 at 15:04

1 Answer 1

up vote 6 down vote accepted

This is very similar to the definition of a random oracle in cryptography.

In any case, it's pretty obvious that your sequence almost surely (i.e. with probability 1) does not converge.

In particular, since your sequence $(a_k)$ only takes on values from a discrete set, in order to converge it would have to be constant from some point $k_0 \in \mathbb N$ onwards. But that can only happen if $a_k = a_{k_0}$ for all $k > k_0$, which is the intersection of infinitely many independent events, each occurring with probability less than $1-\epsilon$ for some fixed $\epsilon > 0$, and thus their intersection only occurs with probability 0.

share|improve this answer
    
+1: Just beat me to it by 5 seconds. –  Cameron Buie Jun 30 '12 at 14:48
    
That's interesting. Does this change if instead of picking a number from ${1,2,3,4,5,6}$ we choose a random real number, or maybe one from the interval $[0,1]$? –  Javier Badia Jun 30 '12 at 15:05
    
@Javier: Just to answer an old question, no it doesn't. If the real-valued sequence converged to some $x \in \mathbb R$, then for any $\epsilon>0$, there would have to be some $k_0$ such that, for all $k>k_0$, $a_k\in[x-\epsilon,x+\epsilon]$. As long as we can choose an $\epsilon>0$ such that each $a_k$ has a non-zero probability of not belonging to $[x-\epsilon,x+\epsilon]$ (i.e. as long as the probability distribution is not concentrated at $x$), the conclusion still follows. –  Ilmari Karonen Aug 29 at 1:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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