Using this definition of a random process is a sequence of random variables whose outcomes do not follow a deterministic pattern, but follow an evolution described by probability distributions.

I have an intuitive notion of a property of a random sequence. That the sequence should remain random after "random" series of operations (depending on the entries of the sequence) of addition and modulus subtraction (modulus). What is this notion/property of randomness called? Does it hold?


Let the $n$'th term be $a_n$ then $b_n = |a_n - a_{n+1}| - a_{n+1} $

If $a_n$ is a random sequence, so is $b_n$


Algorithm to tell if an infinite sequence is random or not?


It is not precisely clear what definition of randomness you use when you say a sequence of numbers "is random" or "stays random". But I assume you mean something like the following:

Let $n \in \mathbb{N}_{\geq 2}$ and let $X_1,X_2,... \Omega : \rightarrow \{1,...,n\}$ be independent, discrete random variables and let each $X_i$ be uniformly distributed on the set $\{1,...,n\}$. Then, for each $w \in \Omega$, the sequence $$ s(\omega):= (X_1(w),X_2(\omega),...) $$ could be called a random sequence. This is the most straightforward definition of randomness.

If you would now (say) use addition of components to form a new sequence $$ s_{+}(\omega) := (X_1(\omega)+X_2(\omega), X_2(\omega)+X_3(\omega),...) ,$$ then all entries of $s_{+}$ are still identically distributed, but they have lost their independence. To see this, imagine that $X_i(\omega)+X_{i+1}(\omega)$ is very high. This would imply an increased probability that $X_{i+1}(\omega)$ is very high, which in turn would imply an increased probability that the next entry $X_{i+1}(\omega)+X_{i+2}(\omega)$ is very high as well.

Since the sequence $s_+$ has no independent entries anymore, it is in this sense less random then the sequence $s$. As a rule of thumb: the more operations (addition, subtraction, division of components,...) you apply to $s$, the more dependent the entries of the resulting sequence will get and the more patterns will emerge, which will make the sequence less random in an intuitive sense.

The point is, if you accept the definition from above about what it means for a sequence $s$ of natural numbers to be random, then it is impossibe for the sequence $s_+$ to be random as well according to the same definition of randomness. The same holds for similar sequences $s_-,s_*,...$. As soon as the entries of the sequence loose their independence, patterns can and will emerge in the long run.

  • $\begingroup$ Thank you for your answer. I seem to have given a terrible example in hindsight. What if the operation used depends on $X_i(\omega)$ and $X_{i+1}(\omega)$ as in the motivation? Does your argument still hold? $\endgroup$ – More Anonymous Mar 5 '18 at 0:10
  • $\begingroup$ With this "definition", it seems that every sequence is declared random. $\endgroup$ – Did Mar 5 '18 at 8:24
  • $\begingroup$ Reason for downvote? I've edited it.. Hopefully it's more reasonable now $\endgroup$ – More Anonymous Mar 5 '18 at 8:38
  • $\begingroup$ @Did. No, of course not every sequence is random according to my definition. You seem to be confused about the role of independence of the components of the sequence, which is crucial for the definition. $\endgroup$ – Joker123 Mar 5 '18 at 13:28
  • 1
    $\begingroup$ Are you telling me that people are not calling i.i.d. sequences random sequences on occasion? You seem to confuse "random" will something more like "well-mixed". I am giving a definition for a process which produces random sequences; you seem to be concerned with a definition of a measure of "well-mixedness" of a particular instantiation of a single sequence. It is not clear at all, however, how the fact that a sequence is well-mixed implies that it is the product of a random process, and therefore random in this (rigorous) sense. $\endgroup$ – Joker123 Mar 5 '18 at 14:38

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.