1
$\begingroup$

This is based from the paper titled, "Chaos-Based Simultaneous Compression and Encryption for Hadoop" in Section 2.3.1 download link

The Authors say that given a symbolic sequence, it can be encoded into an initial condition by reverse interval mapping using the inverse map $f^{-1}_T(.)$. Then, starting from the initial condition, if the map $f_T(.)$ is iterated and the symbolic dynamics obtained by state space partition using the intervals computed from the encoding stage, we can obtain the same symbolic sequence.

Improve this question
$\endgroup$
1
  • $\begingroup$ The question has been edited to the point where it is no longer a question. $\endgroup$
    – Gerry Myerson
    Commented Apr 24, 2017 at 6:10

1 Answer 1

Reset to default
2
$\begingroup$

The article is indeed confusing. Let me focus on the $p=1/2$ case. Note first that the tent map is not invertible, as shown in the picture below from wikipedia).

tent map from wikipedia

The tent map has two inverse branches. What is (almost) invertible is the conjugacy between the shift map on the symbolic space and the tent map. This conjugacy can be defined using the binary expansion of reals in the interval $[0,1]$ (for $p=1/2$). This is slightly easier to define for the doubling map $x \mapsto 2x \ mod \ 1$ and is done as follows.

$$ \matrix{\varphi : &\{0,1\}^{\bf N} & \rightarrow & [0,1]\cr & (a_i)_{i\in {\bf N}} & \mapsto & \sum_{i=0}^{\infty} {a_i\over 2^{i+1}} \cr}$$

This is best represented in the diagram below.

$$ \matrix{ \{0,1\}^{\bf N} & \xrightarrow{shift} & \{0,1\}^{\bf N} \cr \ {\llap{\varphi}\left\downarrow \right.} & & \ {\left\downarrow \right.\rlap{\varphi}} \cr [0,1] & \xrightarrow{doubling} & [0,1] \cr} $$

Note that there is also a semiconjugacy from the doubling map to the tent map from the relation $tent \circ doubling = tent \circ tent$.

$$ \matrix{ [0,1] & \xrightarrow{doubling} & [0,1] \cr \ {\llap{tent}\left\downarrow \right.} & & \ {\left\downarrow \right.\rlap{tent}} \cr [0,1] & \xrightarrow{tent} & [0,1] \cr} $$ It's better to define the symbolic model for the tent map directly though so that the semi-conjugacy is invertible outside a countable set of points.

See the classical book of Hirsh, Smale and Devaney, "differential equations, dynamical systems and an introduction to chaos" chapter 15 for a nice discussion of the tent map and its symbolic model in the case $p=1/2$. You will find there a far better explanation of the model. Note that getting the symbolic sequence associated to a point just amounts to iterate the point and checking if the iterate is on the left interval $[0,1/2]$ (-> bit 0) or on the right interval $[1/2,1]$ (-> bit 1).

My thanks to Anthony Quas for correcting me about the conjugacy.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ The semi-conjugacy for the tent map is (unfortunately) more complicated than you have described here. Your is the semi-conjugate for the doubling map. $\endgroup$
    – Anthony Quas
    Commented Mar 31, 2017 at 12:15
  • $\begingroup$ @coudy: It is still unclear to me what you have described. So, the map $f^{-1}(.)$ which is used in reverse interval mapping is the shift map? The shift map is the Bernoulli dyadic map (please correct me if wrong). For more branches or for multile partitions in the case of mapping multiple symbols, the $f^{-1}(.)$ is further extended based on the probability of the occurrence of unique symbols. If I have understood correctly, the $f^{-1}(.)$ is termed the inverse map, but it should be the shift map. Please let me know, I have these doubts. $\endgroup$
    – SKM
    Commented Mar 31, 2017 at 15:17
  • $\begingroup$ If the shift map is related to tent map, then Is the inverse shift map chaotic? Can you please explain more in non-technical terms? $\endgroup$
    – SKM
    Commented Mar 31, 2017 at 17:44
  • $\begingroup$ See the following reference. math.stonybrook.edu/~jack/DYNOTES/dn2.pdf As pointed out by A. Quas, I talked about the simpler example of the doubling map. It is more complicated to write down the conjugacy for the tent map. $\endgroup$
    – coudy
    Commented Mar 31, 2017 at 18:50
  • 1
    $\begingroup$ What you call the inverse map is a map from $\{0,1\} \times [0,1]$ to $[0,1]$ that is obtained from the two inverse branches of the tent map. You can't iterate it and I don't see how to give a meaning to the question: is it chaotic? Note that the first inverse branch $x \mapsto "f^{-1}(0,x)"$ is just division by 2. If you iterate it, every point goes to $0$. Note that the two branches make an iterated function system, maybe this helps? $\endgroup$
    – coudy
    Commented Mar 31, 2017 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .