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.

Improve this question
$\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
    Commented Sep 26, 2015 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
    Commented Sep 27, 2015 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
    Commented Sep 27, 2015 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
    Commented Sep 28, 2015 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
    Commented Sep 28, 2015 at 16:37

1 Answer 1

Reset to default
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))$

Improve this answer
$\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
    Commented Mar 12, 2016 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.