2
$\begingroup$

In paper: A Framework for Investigating the Performance of Chaotic-Map Truly Random Number Generators under Section II it is mentioned that the sequence $\{x_n\}$ generated from the output of a chaotic discrete map is a Markov process.

The reference is also provided which is a book. I have skimmed through the book and resources available in internet but could not find how to show or prove that the sequence is a Markov Process. In essence, do I need to show the Markov property of memory-less property ? But, I cannot understand how to show analytically. It will be of tremendous help if some directions for the proof and references where it exists are provided.

Any other example will also be helpful.

$\endgroup$
5
  • 1
    $\begingroup$ Indeed the sequence is a Markov chain, but a very special one since its transition kernel $$K(x,A):=P(x_{n+1}\in A\mid x_n=x,x_{n-1},\ldots,x_0)$$ is such that, for every $x$, $K(x,\ )$ is a Dirac mass (at $M(x)$). Not your typical Markov chain, but a Markov chain yes. $\endgroup$ – Did Sep 26 '15 at 15:01
  • $\begingroup$ Thank you for your answer, can you provide links where I can find more information? I am not aware of this proof and how to show what is a Dirac mass and hence the proof. $\endgroup$ – Ria George Sep 27 '15 at 21:13
  • $\begingroup$ "can you provide links where I can find more information?" More information about what? "how to show what is a Dirac mass" One does not "show what is a Dirac mass", either one reads the definition to know what is a Dirac mass or one shows that something is a Dirac mass. For your information, the Dirac mass at $y$ is the unique measure $\mu$ such that $\mu(A)=1$ for every $A$ such that $y\in A$ and $\mu(A)=0$ for every $A$ such that $y\notin A$. $\endgroup$ – Did Sep 27 '15 at 21:21
  • $\begingroup$ How to show that K(x) is a dirac mass? Is it needed to show this in order to prove that the sequence output from the chaotic map is a Markov chain? Can you outline the steps to show that the chaotic map generates r.v which forms markov chain? $\endgroup$ – Ria George Sep 28 '15 at 0:11
  • $\begingroup$ "Can you outline the steps to show that the chaotic map generates r.v which forms markov chain?" I already did. Perhaps you are missing the point but every deterministic sequence $(x_n)$ such that $x_{n+1}=M(x_n)$ for some function $M$ is a (very degenerate) Markov chain. Proof: Look up the definitions. $\endgroup$ – Did Sep 28 '15 at 16:37
3
$\begingroup$

From the article : "The output of the map function from the previous time-step is fed back as the input of the current time-step. That is $x_n=M(x_{n-1})$."

Therefore, the information about $x_n$ is described by its immediate previous state (all the information about past states is irrelevant), making it a Markovian process.

If you don't want to use words : $P(x_n\in A_n |x_1\in A_1,...x_{n-1}\in A_{n-1}) = P(x_{n-1}\in M^{-1}(A_n))$

$\endgroup$
1
  • $\begingroup$ The identity at the end is 1. false in the case at hand, 2. not how one characterizes Markov chains $\endgroup$ – Did Mar 12 '16 at 13:07

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.