2
$\begingroup$

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.

  • 0
    @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.2012-06-30

1 Answers 1

7

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.

  • 0
    @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.2014-08-29