Limiting behavior of coins on a finite graph with flips activated by a full neighborhood Let $G = (V,E)$ be a finite graph, and as particular concrete examples, consider the case of a path or cycle graph. Say a configuration on $G$ is a function $f: V \to \{0, 1\}$, which we can think of as coins located at each vertex, facing either tails or heads, respectively. Denote the configuration of $G$ at timestep $n$ by $f_n$. The evolution from timestep $n$ to $n+1$ is given by the following rule: if all neighbors of a vertex $v$ are facing heads, then the coin at vertex $v$ is flipped (i.e., 50% chance of heads, 50% chance of tails) and $f_{n+1}(v)$ is set to be the result of this flip. For all other vertices $v$, $f_{n+1}(v) = f_n (v)$.
Note that if at any point in the evolution, we have two adjacent vertices $v$ and $w$ such that $f(v) = f(w) = 0$, then these two vertices will remain at tails forever. Thus, if $I_n$ denotes the proportion of vertices that are "inactivated" in this fashion at time $n$, then $I_{n+1} \ge I_n$ for all $n$ and thus $L = \lim_{n\to\infty} I_n$ exists. Can we say anything explicit about the distribution of $L$?
For the particular case of the path graph $P_k$ with $k$ vertices, when initializing all vertices as heads, numerical experiments suggest that $L$ is typically very close to about 0.34, irrespective of the length $k$. The limiting configuration consists of islands of that perpetually flicker between 01110 and 01010, and stable blocks of the form 0110, 010, and 00. However, I haven't been able to calculate anything precise about the incidences of each of these block types. Any help would be very appreciated!
 A: I have a few observations for the path graph $P_n$ that may prove useful, but I'm not bothered enough to follow them up. Each seems easy to prove by case exhaustion. These are as follows:

*

*Period two behaviour is the most complex that can occur (see below).

*The limiting behaviour is emerges after just two iterations. In other words, for all $v\in P_n$,
$$f_2(v) = f_4(v),$$
regardless of starting configuration.

*If $f_2(v) = f_3(v) = 1$ (i.e. $f_n(v)$ is eventually 1), then $f_1(v)=f_0(v)=1$.

Stable structures
This given, you can tell all from the starting partition $f_0$ (perhaps not as simply as applying the derivation twice, but hey).
Notation:

*

*$1^n := \underbrace{11…1}_{n}$, and similarly,

*$0^n := \underbrace{00…0}_{n}$.

One way may be to look at the blocks:

*

*By block, I mean a chain of 1s which is surrounded by $0$s on each side (i.e. $01^n0$).

*Two blocks are adjacent if they are separated by just one $0$.

*A block is a middle block if it is adjacent to two blocks (one on each side).

*A block is an end block if it is adjacent to exactly one block (on the left or right).

*A block is a loner if it is surrounded by no other blocks.

(As for the ends of the graph, one may wish to add 001 and 100 artificially to the left and right end respectively for this classification and ensuing description to make consistent sense. One can subtract 4 afterwards!)
One can quickly verify what happens for middle blocks. Here, what happens to the 1s on each side depends on the length of the block it belongs to (and whether it is an end or not):
$$\begin{array}{c|c} 
f_0 & f_2 \\ \hline 
10101 & ?000? \\
101101 & ?0000? \\
1011101 & ?01110? \\
\ \phantom{n\geq4, }{101^n01},\ {n\geq4} & ?010^{n-2}10?
 \end{array}$$
That is,

*

*middle blocks of lengths 1 or 2 disappear completely;

*middle blocks of length 3 survive entirely; and

*middle blocks of length 4 or more: only the endpoints survive.

(Survive here means $f_2(v)=1$, and disappear means is eventually 0.)
Similar thing holds for one-sided blocks, except one of its endpoints always survives.
Finally, only the endpoints of loner blocks survive, unless the block is length 3.
It is the surviving endpoints which satisfy $f_n(v) = 1$ for all $n$. But that's not all — whenever a vertex is between two endpoints which survive, it alternates between 0 and 1, ad infinitum. For example,
$$00111011100 \longrightarrow 00101110100 \longrightarrow 00111011100,$$
and indeed, any chain of adjacent middle blocks of length 3 has this property. More precisely, a vertex will alternate if and only if one of the following holds:

*

*it is between a middle block of length 3 and a block of length 3 or more.

*it is between a middle block of length 3 and an end block of length 1.

*it is the middle vertex of any block of length 3.

These are precisely the vertices which do not get deactivated (surviving endpoints and alternators), so an algorithm may focus on counting these somehow. To my mind this seems like a hard thing to do, so an estimation may be in order.
(PS. If you want my Mathematica file, do say so!)
