5
$\begingroup$

Motivation. Sometimes in life, people seem to do what the majority of their friends are doing. Do we all become more similar over time? Do we split up into pockets of similarity? This post aims to provide a rigid mathematical approach for these questions.

Formalization. Let $\newcommand{\N}{\{0,1\}^\mathbb{Z}}\N$ be the collection of all binary $\mathbb{Z}$-sequences. If $n \in \mathbb{N}$ is a positive integer, and $k\in \mathbb{Z}$ we define the $n$-ball around $k$ by $$B_n(k) := [k-n, k+n]\cap\mathbb{Z}.$$ (Note that every $n$-ball has $2n+1$ elements.)

For any positive integer $n\in\mathbb{N}$ we define the $n$-ball majority map $$\newcommand{\m}{\text{maj}}\m_n: \N\to\N$$ in the following way: for each $f\in\N$ the map $\m_n(f) \in \N$ is defined by

$\big(\m_n(f)\big)(k) = 0$ if $\big|f^{-1}(\{0\})\cap B_n(k)\big|\geq n+1$, and $\big(\m_n(f)\big)(k) = 1$ otherwise.

Whenever $X$ is a set and $g:X\to X$ is a map, we let $g^{(1)} = g$ and inductively define $g^{(n+1)} = g \circ g^{(n)}$ for all $n\in \mathbb{N}$.

Question. Is there a positive integer $n$ and $f\in\N$ such that the iteration map $$\text{it}_{n,f}:\mathbb{N} \to \N$$ defined by $$i\in\mathbb{N}\,\mapsto \,\m_n^{(i)}(f)\in\N$$ is injective?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
7
$\begingroup$

Observe that, in isolation, (the indicator function of) an arithmetic progression of common difference $2$ and length $N > n$ maps to an arithmetic progression of common difference $2$ and length $N-n$.

Now consider a union $\bigcup P_N$ of highly separated arithmetic progressions of common difference $2$ and every length $N > n$. The iteration map gradually kills off the smallest progressions, so your map $i\mapsto \operatorname{maj}_n^{(i)}(f)$ is injective.

This also justifies the comment of @FedorPetrov, by monkey typewriting.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Another example is the positive even integers, for similar reasons. $\endgroup$
    – Sean Eberhard
    Commented Sep 4 at 17:03
6
$\begingroup$

If I understand correctly, you are asking whether this particular dynamical system has any initial conditions that lead to infinite orbits (i.e. orbits that are not eventually periodic). Someone else has already answered the question, so I will just provide some broader contextual information.

First, the specific dynamical system you have proposed is an example of a (one-dimensional) cellular automaton (CA). There is a huge research literature on cellular automata. The particular cellular automaton you have described is called a voter model (for obvious reasons); these have been studied at least since the 1990s. For example, the following three papers seem closely related to your question:

You might also find this LifeWiki website informative (although it is about the two-dimensional version of the voter CA).

Second, if I understand correctly, you are not asking this question out of pure mathematical curiousity; your motivating question was explicitly sociological ("Sometimes in life, people seem to do what the majority of their friends are doing"). There is an entire area of statistical physics called sociophysics (or "social physics") dedicated to using cellular automata (or, much more frequently, stochastic cellular automata) and similar systems to model social interactions. The stochastic version of the cellular automaton you described is often used to model "opinion formation dynamics". See the following literature for further information:

Improve this answer
$\endgroup$

You must log in to answer this question.

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