1
$\begingroup$

I am reading through articles which present the spectral properties of chaotic systems such that they can be candidates for generating pseudo random binary sequences. One such article, is http://bactra.org/notebooks/symbolic-dynamics.html where it is mentioned that chaotic deterministic dynamics are in a sense completely equivalent to sources of independent, identically-distributed random variables. Is there a proof in a book or how does one proof this statement?

UPDATE: What the statement means is consider a chaotic deterministic system $\tau$ which is a map $w_{n+1} = \tau(w_n)$, generated for an initial condition $w_0$, $n=0,1,..., w_n \in J$ where $ \tau: J = [0,1] \rightarrow J$. Then how to show that $X_n $ is $i.i.d$ random variables where $X_n = \phi(w_n)$ ; function $\phi(.)$ has its domain in $S = \{1,2,\ldots,N\}$ and the range of the function is an alphabet set. The output $X_n$ is a stationary sequence. $w_n$ can be quantized through this function.

Came across these references:Binary Sequences Using Chaotic Dynamics and Their Applications to Communications, download link By Tohru Kohda` and

Chaotic Electronics in Telecommunications
 edited by Michael Kennedy, Riccardo Rovatti, Gianluca Setti

In both, it is mentioned that iid r.v can be generated from ergodic maps. In the book Chapter4, Pg 101 Remark 1.5 mentions a theorem (also mentioned in the paper). Basic premise is that there is a binary function $\phi(.)$ which generates binary sequences $X_n$. Then Theorum 4.88 in Pg 100 says that this is iid r.v and follows Bernoulli distribution. In order to prove this, it must be shown that the binary function $\phi(.)$ satisfies the constant summation property, then only can $\tau(w_n)$ satisfy the Equi-distributivity property (EDP). Then, $\tau(w_n)$ can generate $i.i.d$ random variables [Reference : Paper]. I am not from core mathematics background (from signal processing) and having a tough time to decipher what all this means. Shall be extremely helpful if it is shown in simpler ways how to obtain a proof for this statement i.e. Th (4.88) which is sequences of $i.i.d.$ binary r.vs can be generated by chaotic dynamics. Thank you.

$\endgroup$
  • $\begingroup$ @Donda: Thank you for your explanation but it still is unclear; how to support the statement statistically. $\endgroup$ – SKM Apr 20 '15 at 17:24
  • $\begingroup$ SKM, not even worth an upvote? ;-) What would you accept as "statistical support"? $\endgroup$ – A. Donda Apr 20 '15 at 17:27
  • $\begingroup$ From probability theory viewpoint, there may be proof to show that a process results in random varaibles. So, how to apply those concepts here to show that chaotic dynamics produces iid r.v. This is what I meant by statistical support. In the references which I mentioned, there are concepts such as Frobenius Perron operator to show random variables, but I do not understand the intuitive meaning as to how this theory shows that the variable is a random variable. Any explanation not strictly related to chaos theory to show how a process produces r.v will be enlightening. Thank you. $\endgroup$ – SKM Apr 20 '15 at 18:02
  • $\begingroup$ Ok, I edited my answer, please see whether this is more to the point. $\endgroup$ – A. Donda Apr 20 '15 at 19:40
1
$\begingroup$

Maybe an example helps to understand how deterministic chaotic dynamical systems and stochastic processes can be considered equivalent. The classic example of a chaotic dynamical system is the logistic map famously investigated by Mitchell Feigenbaum. The fully chaotic case of the logistic map, $x_{n+1} = 4 x_n (1 - x_n)$, can be seen as the dyadic transformation $$ y_{n+1}=\begin{cases} 2y_n & 0 \le y_n < 0.5 \\ 2y_n-1 & 0.5 \le y_n < 1 \end{cases} $$ observed through $x_{n}=\sin^{2}(2 \pi y_{n})$, which makes the dyadic transformation arguably the simplest possible chaotic dynamical system (one-dimensional, discrete time, nonlinearity only in the form of piecewise linearity). It is chaotic because arbitrarily small differences in the initial conditions lead to arbitrarily large differences in the outcome after a finite time, limited of course by the range on which the map is defined, $y_n \in [0, 1)$.

The real numbers $y_n$ can alternatively be represented as binary numbers, i.e. $0.$ followed by a sequence of $0$s and $1$s. In this representation, the dyadic transformation becomes a bit shift: all binary digits are shifted to the left by one position, and then the digit before the decimal point is replaced by a $0$ (discarded). This is the perspective of symbolic dynamics, considering dynamics in a continuous state space as equivalent to shift operations on infinite symbol strings.

If we now look at the sequence of discarded binary digits, which coincides with the sequence of digits in the binary representation of the initial state $y_0$, this sequence is of course determined by that initial condition and therefore "not random". However, in practice we never exactly know initial conditions, and the whole point of chaotic dynamics is to recognize that predictability for such systems does not gradually degrade with limited knowledge of $y_0$, but that there is a specific time window beyond which we cannot predict the future at all. Let's say we know $y_0$ up to 100 binary digits, then from that knowledge the sequence of discarded letters is determined for 100 iteration steps – but after that we are completely in the dark. For all intents and purposes, the digit sequence beyond that point is random, and in particular it is equivalent to a Bernoulli process, the sequence of independent tosses of a fair coin.

This of course assumes that "randomness" is not (necessarily) a property of a process, but is something that relates to the limits of our knowledge – if you will, corresponding to a Bayesian interpretation of probability. That is a perspective that worked well in physics before, in statistical mechanics, and it is no wonder that it is picked up again in the study of nonlinear dynamical systems.


In response to the OP's comment:

Thank you for your explanation but it still is unclear how to support the statement statistically. From a probability theory viewpoint, there may be a proof to show that a process results in random variables. So, how to apply those concepts here to show that chaotic dynamics produces iid r.v.

Well, the problem is it is not possible to prove that something is a random variable. An RV is a conceptualization that one decides to apply or not. Some people would say that this conceptualization is only adequate if the process is "objectively" random, e.g. quantum mechanical processes. Others would say that randomness arises from lack of knowledge, and whether that lack of knowledge is only of practical nature (measurement precision, very high-dimensional state spaces) or more fundamental doesn't matter. It is quite enlightening to read the discussion in Chapter 10 of Jaynes' Probability Theory: The Logic of Science, where he shows how those processes that we normally consider prototypically random, throwing of dice and coins, are actually governed by pretty strong deterministic rules, which can be exploited by learning how to manipulate initial conditions.

A deterministic chaotic system has, as the name says, deterministic rules. If one also treats the initial conditions as perfectly determined (in the sense of absolutely precisely known), then of course there is nothing random about it. But as I wrote above, if we recognize that the interesting feature of chaotic dynamics is the discarding of information (clearly seen in the above example of the dyadic transformation), then the interesting situation is the one in which we do not have perfect knowledge of initial conditions but only finite information, which means that after a finite time we have no knowledge at all.

We can now conceptualize this lack of knowledge by treating the initial condition as a random variable, e.g. $$ y_0 = 0.0100011101111abc..._2 $$ We know the first 13 binary digits of $y_0$, but nothing beyond that. This means the digits $a, b, c, \ldots$ are undetermined, and we may therefore conceptualize them as random variables. If we have no knowledge otherwise, we may consider them as uniformly distributed over $\{0, 1\}$ and i.i.d. These binary digits are then produced by the digit-discarding process of the dyadic shift, and after the first 13 digits we are presented with something that is indistinguishable from a Bernoulli process.

Now, it is not directly the dynamics of the dyadic shift itself that is equivalent to a Bernoulli shift, but the sequence of discarded digits. The sequence of numbers itself, $y_0, y_1, y_2, \ldots$, is clearly not independent! This is why in some cases much more theoretical work needs to be done to figure out in which specific sense a given deterministic chaotic system is equivalent to some random variable. Since I'm not familiar with the paper you refer to, I can't tell you more about how exactly they construct this relation in their case – but I am pretty sure that the fundamental ideas are the same as those that I tried to explain here.

$\endgroup$
1
$\begingroup$

I disagree with the premise of your question. Chaotic is not the same as stochastic. However, this doesn't preclude it from being useful for psudo-random number generation. A process doesn't need to be equivalent to i.i.d in order to be useful to generate sequences, which are indistinguishable from i.i.d. for many practical purposes.

Consider the most popular random generators, they're not random at all! They're absolutely deterministic.

$\endgroup$
  • $\begingroup$ Thank you for your reply. Is it possible to support your statement that deterministic chaotic systems can produce $iid$ random variables? Actually, this is my main concern as to how to show that they are useful for PRN generators and I have updated my Question $\endgroup$ – SKM Mar 30 '15 at 22:15
  • 1
    $\begingroup$ The $X_n$ are by definition not iid random variables; they're not random, and even treating the seed as random they're extremely dependent. The sense in which pseudorandom number generators are useful approximations to is perhaps something like this: treating $w_0$ as, say, uniformly random, then most functions of the $X_i$ are uncorrelated with one another. $\endgroup$ – Dougal Mar 31 '15 at 6:12

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.