What constitutes randomness?

To begin with, I am not a mathematician, so the question might sound dumb :) Anyway, I have been playing 2048 and thinking on randomness and some things just do not seem very straight to me, when considering what is random.

Given a sequence $S=1, 2, 3, 4,..., m$, each number repeats exactly once and has the same probability to appear in a sequence: $$P(S_{n1})=P(S_{n2})=\frac{1}{n}$$ therefore it is totally random sequence.
Considering Shannon's entropy $$H(X)=-\sum_i P(x_i)\log_2P(x_i)=-\sum_{1}^{n} \frac{1}{n}\log_2\frac{1}{n}=-\log_2\frac{1}{n}$$ we get maximum possible entropy (am I right here?), what suggests remarkably random sequence.
Yet we can derive simple formula to acurately predict the next number at any point in a sequence: $$S(n+1)=S(n)+1;$$ therefore it is totally predictable and has zero randomness.

How should I treat such sequence and what actually constitutes randomness?

If a sequence is random, I should not be able to make any assumptions about the next number at any point of the sequence. At the same time, all the possible numbers should have the same probability of appearing. This implies that if in the past some numbers were more frequent, they are less likely to come up in the future, which means that in time the sequence becomes more predictable - less random, which in turn implies that no finite sequence can be truly random.

This might also mean, that a sequence has different amount of randomness at different points i.e. randomness is a parameter (function), not a property. Finally, if a sequence gets long enough slight discrepancies in frequency become statistically negligible and the sequence should still appear random, yet be of varying randomness.

it is a bit a wall of text with no exact question, but I tried to list where randomness is strange. I would really appreciate if someone would shed some light on this topic without very complicated math :)

EDIT:

Expanding on 5xum's answer: I understand that rolling a 6 five times in a row with d6 still gives probability of 6 exactly $\frac{1}{6}$. Yet, we cannot say the dice is not fair because the sample is too small. How large the sample should be so we could deduce that the dice is fair/unfair? Furthermore, in case of d6, the distribution can only be uniform (meaning total randomness) if a size of a sample is multiple of 6. Should we take such things to consideration when describing randomness of a sample or are we relying on the size of a sample and negligence of frequency differences?

• I recommend reading "What is a random sequence?" Chapter 3.5 of Knuth, Seminumerical Algorithms, Volume 2 of The Art Of Computer Programming. – Gerry Myerson Jun 6 '14 at 7:23
• I would add that Chaitin ( ufrj.academia.edu/GregoryChaitin ) has a lot to say about what is and isn't random, and how hard that search can be. The linked page has podcasts, videos and papers. – postmortes Jun 6 '14 at 8:17

At the same time, all the possible numbers should have the same probability of appearing. This implies that if in the past some numbers were more frequent, they are less likely to come up in the future.

This is where your error lies. The statement above is false.

When you think about generating random numbers, always think about rolling dice. If you roll $6$ five times in a row, is the probability of rolling a six in the next roll any smaller than $\frac16$?

I believe you have a false understanding of what the word "random" actually means. No sequence of numbers is in itself "random". The part that is random is the process that created this sequence. By that, I mean that if I say I will write $5$ sixes in a row, then the sequence $6,6,6,6,6$ is not random. However, if I throw a d6 $5$ times, then the sequence I get is random, even if the sequence is $6,6,6,6,6$. This means that your sentence

Furthermore, in case of d6, the distribution can only be uniform (meaning total randomness) if a size of a sample is multiple of 6.

is misleading. The term "distribution" is used to describe the process by which you get the numbers, not the numbers themselves.

As for asking how to decide if the dice is fair or unfair, that is a job for statistics.

• I have edited my question to answer this – friendzis Jun 6 '14 at 7:49
• @friendzis And I edited my answer. – 5xum Jun 6 '14 at 8:47