Few months ago my scientific adviser asked me to use probabilistic ideas in such problem :

Consider a matrix NxN. Each element of matrix is a number 1 or 0. We may change all elements of this matrix by major element of neighbors (if there is equal number of '1'-s and '0'-s we choose '0'). Also all changes execute at one moment (to have no indefinite behavior). Now we want to know how many '1'-s we need(lower bound) to reach a $\mathbb{1}$-matrix, which contains only '1'-s.

First of all I've considered this elements as random variable with Bernoulli distribution. So we have $\{X_{i,j}\}_{i,j = 1}^{N}$ are independent random variables (let's suppose they are mutually independent) :$X_{i,j} = 1$

$\begin{equation*} X_{i,j} = \begin{cases} 1 &\text{with $p$}\\ 0 &\text{with $1-p$} \end{cases} \end{equation*}$. , where $p \in(0,1)$. And we need to find $p_{min}$, which guarantee us the good result (for $90 \%$ of experiments).

There is a first problem to deal with. After some matrix changes we miss independence between elements. There occurs some correlation.

However, using Python I've simulated this matrices and make a huge numbers of 'changes'-iterations to reach the result. This simulations shown that there can be 3 possible results : matrix will be $\mathbb{0}$, $\mathbb{1}$ or it cycled. Also I've shown that cycled elements looks like : $\begin{pmatrix} \dots & 0 & 1 & 1\\ \dots& 1 & 1 & 1\\ \dots& 0 & 0 & 1 \\ \dots& \dots & \dots & \dots\\ \end{pmatrix}$. So if $N$ is sufficient large the probability of cycled elements should be small (I guess).

But that's give me only Python-buffing. I've know that cellular-automata are very explored. So maybe there are exist some books or article to read about this? I've found something , but in most of them doesn't go the question of stability of system or finding probability of this elements.

So the main question : maybe there are some books or article, where the author consider this type of problem. It would be amazing if you reccomend me some of them! I'm not interesting in the final answer , I just want to understand it and reach it.

  • $\begingroup$ If your "scientific adviser" asked you to solve this problem, he/she may well have some experience with this. Have you asked him/her for any reference material? It may also be worth having a look at some random graph theory for this, as this problem has a natural interpretation there through adjacency matrices. $\endgroup$ – Carl-Fredrik Nyberg Brodda Feb 6 '19 at 9:05
  • $\begingroup$ @Carl-FredrikNybergBrodda unfortunatly he deals with a bit different area. He just want me to use probabilistic stuff here. It's interesting about random graphs , I don't think about them. Thanks ! $\endgroup$ – openspace Feb 6 '19 at 9:08
  • 1
    $\begingroup$ The tag [textbook-recommendation] is probably not want you want, nor is the generic [books], so I added [reference-request]. $\endgroup$ – David Roberts Feb 6 '19 at 9:26
  • $\begingroup$ @DavidRoberts thanks for edit! $\endgroup$ – openspace Feb 6 '19 at 12:12
  • $\begingroup$ As for cellular automata related problems, you could try the Conwaylife.com forums. $\endgroup$ – LeechLattice Feb 6 '19 at 13:39

For fixed $p<1$ and large enough $N$, almost all configurations does not reach a $1$-matrix, as there is an obstruction, i.e. a configuration of 12 $0$ cells (shown in black):

Black for 0, White for 1

If such a configuration appears at generation 0, it will always remain so. Such a configuration would almost surely appear as the probability for it to appear at generation 0 is a fixed nonzero value (say $(1-p)^{12}$).

  • $\begingroup$ But there is a small probability to have such configuration. Or to reach it. And i guess it's not a $(1-p)^{12}$, because of this probability just garantee that there is a 12 $0$ cells $\endgroup$ – openspace Feb 6 '19 at 13:39
  • $\begingroup$ @openspace So you mean that $p$ varies with $N$? $\endgroup$ – LeechLattice Feb 6 '19 at 13:44
  • $\begingroup$ It would be great to have a connection between $p$ and $N$. $\endgroup$ – openspace Feb 6 '19 at 13:45
  • $\begingroup$ But if almost surely convergence to $1$ is to be guaranteed, there must be $p→1$, as the argument above works for $p$ bounded away from $1$. $\endgroup$ – LeechLattice Feb 6 '19 at 13:47
  • $\begingroup$ I agree with that. It supposed to converges to $1$ with $N \to \infty$. $\endgroup$ – openspace Feb 6 '19 at 13:55

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.