A Pascal's-triangle -like random process - MathOverflow

A Pascal's-triangle -like random process

2011-05-27T19:33:34Z

I was exploring Pascal's triangle on a cylinder when I encountered this puzzle-like problem. It is surely elementary, but perhaps weekend-entertaining.

Start with a permutation of $(1,2,3, \ldots, n)$, call it $(x_1,x_2,x_3,\ldots,x_n)$. Perform two operations in sequence: Sum, and Shuffle. Sum computes a new sequence $x'_i = (x_i + x_{i+1})$, with cylindrical index wraparound. (This is the Pascal's-triangle aspect.) Shuffle permutes the resulting numbers (below I used a random permutation). Then the Sum/Shuffle-transformations are repeated. Here is an example, for $n=4$:

I hope the process is clear without further formal definitions. The numbers in the sequence grow by powers of 2, but approach the same normalized ratio, and so in that sense "approach" equality. One could ask many questions (I'll resist, although I welcome speculation!), but this is perhaps the primary question:

For which $n$ could the described process lead to a sequence of identical numbers?

For $n=2$, $(1,2)$ is the only option, which ends in $(3,3)$ after just one step. For $n=3$, all starting permutations lead to a permutation of $(3,4,5)$, which leads to a permutation of $(7,8,9)$, which leads to a permutation of $(15,16,17)$, and then to $(31,32,33)$, and so on. This is all I know: $n=2$ must end in a constant sequence, $n=3$ cannot, and $n=4$ might.

Addendum. After Douglas Zare's (nice!) analysis answered the question for all but $n = 0 \mod 4$, I concentrated on $n=8$ and found these two examples: $$ \left( \begin{array}{cccccccc} 7 & 2 & 8 & 1 & 5 & 4 & 6 & 3 \\ 10 & 9 & 10 & 9 & 6 & 9 & 10 & 9 \\ 9 & 6 & 9 & 10 & 9 & 10 & 9 & 10 \\ 15 & 15 & 19 & 19 & 19 & 19 & 19 & 19 \\ 19 & 19 & 15 & 19 & 19 & 19 & 19 & 15 \\ 34 & 38 & 34 & 34 & 38 & 38 & 38 & 34 \\ 34 & 38 & 34 & 38 & 34 & 38 & 34 & 38 \\ 72 & 72 & 72 & 72 & 72 & 72 & 72 & 72 \end{array} \right) $$

$$ \left( \begin{array}{cccccccc} 4 & 3 & 6 & 1 & 8 & 7 & 2 & 5 \\ 9 & 7 & 9 & 7 & 9 & 15 & 9 & 7 \\ 9 & 7 & 9 & 15 & 9 & 7 & 9 & 7 \\ 16 & 16 & 24 & 24 & 16 & 16 & 16 & 16 \\ 24 & 16 & 16 & 16 & 24 & 16 & 16 & 16 \\ 40 & 40 & 32 & 32 & 40 & 40 & 32 & 32 \\ 40 & 32 & 40 & 32 & 40 & 32 & 40 & 32 \\ 72 & 72 & 72 & 72 & 72 & 72 & 72 & 72 \end{array} \right) $$ The rows alternate between permutation and sum, i.e., each odd row is a permutation of the even row above.

Answer by Vaughn Climenhaga for A Pascal's-triangle -like random process

2011-05-27T20:38:14Z

Not a complete answer, but for $n=4$ if you start with an arithmetic progression ($1,2,3,4$ works) then you have probability $1$ of ending up with them all being identical.

Consider the following set of states for the quadruple $(x_1,x_2,x_3,x_4)$ once it has been ordered so that $x_1 \leq x_2 \leq x_3 \leq x_4$:

State $A_0$: All the $x_i$ are equal.

State $A_1$: $\vec x$ is of the form $(a-d,a-d,a+d,a+d)$ for some $a,d$.

State $A_2$: $\vec x$ is of the form $(a-d, a, a, a+d)$ for some $a,d$.

State $A_3$: the four numbers are distinct and form an arithmetic progression, so $\vec x = (a - 3d, a-d, a+d, a+2d)$ where $a$ is the average value.

Given $\vec x$ in one of the four states, choose a permutation from $S_4$ at random and apply the procedure described in the question. There are really only $3$ equivalence classes of permutations, since you only need to know which of the three numbers $x_2,x_3,x_4$ does not get added to $x_1$, and then everything else is determined.

It's not hard to show that if you are in state $A_j$, then with probability $1/3$ you remain in state $A_j$, while with probability $2/3$ you move to state $A_{j-1}$. (Of course if you're in state $A_0$ then you stay there no matter what.) This means that almost surely you eventually end up in $A_0$, where all four numbers are equal.

I'm not sure what happens if you try this for $n\geq 5$.

Answer by Barry Cipra for A Pascal's-triangle -like random process

2011-05-27T21:54:34Z

The basic structure of the numbers you get is invariant under affine transformations, from $(a,b,c,d)$ to $(ra+u,rb+u,rc+u,rd+u)$, so you may as well assume you're working with integers that sum to 0 --- i.e., $d=-(a+b+c)$. (It doesn't really matter that they're integers, but it's convenient.) After the first sum, you're at a 4-tuple of the form $(A,B,-A,-B)$. A permutation either brings the $A$ and $-A$ together (cyclically), or it doesn't. If it doesn't, the next sum remains of the form $(A,B,-A,-B)$ (with new values of $A$ and $B$), so the process continues. If it does bring the $A$ and $-A$ together, say to $(A,-A,B,-B)$, the next sum has the form $(0,C,0,-C)$, which can be scaled to $(0,1,0,-1)$, unless $C=0$ --- i.e., unless $A=B$. If the next permutation brings the 0's together (cyclically), the ensuing sum remains $(0,1,0,-1)$. If it leaves them apart, the ensuing sum is $(1,1,-1,-1)$, so you're back at something of the form $(A,B,-A,-B)$, but this time with $A=B$ --- i.e., the condition under which you can get to $(0,C,0,-C)$ with $C=0$.

Answer by Douglas Zare for A Pascal's-triangle -like random process

2011-05-28T01:10:15Z

This covers all but multiples of $4$:

Consider the preimage of the $0$ vector under the cyclic sum. All vectors in the preimage alternate $(a,-a,...,a,-a)$ and if the length is odd, then $a=-a$. By invariance under affine transforms, the preimages of constant vectors are shifted by a constant. So, if $n\gt 1$ is odd, you don't reach a constant vector since you don't start with one.

For $n==2k$, what is the preimage of a vector $\vec{v} = (v_1,...v_n)$ with $k$ $0s$ and $k$ $1s$? Up to a cyclic shift, the vectors whose cyclic sum is $\vec{v}$ are $(a,-a,a,-a...)+(0,v_1,v_2-v_1,v_3-v_2+v_1,...\sum_{j=1}^i (-1)^{i-j}v_j,...)$ and $0=\sum_{j=1}^n(-1)^{n-j}v_j$. If $k$ is odd, then no way to choose signs for the $1s$ will make that sum $0$, since you can't have equally many $+1$s and $-1$s. So, if $n\gt 2$ is congruent to $2 \mod 4$ then you don't reach a constant vector since you can't reach a vector with only two values, with $n/2$ of each.

It's not obvious to me how this might be extended to the next preimages since the preimages of balanced $0-1$ vectors do not need to have only a few values.

On the flip side, if there is a way to go from any vector to a constant vector, then this will happen eventually with probability $1$. I don't yet see whether this is possible for $n=8$.

Answer by domotorp for A Pascal's-triangle -like random process

2011-05-29T06:55:38Z

It is possible if and only if 4 divides n. Douglas Zare showed that if 4 does not divide n, then it is impossible (btw, his argument might be simpler to state mod 2 - if 4 does not divide n, then it is already impossible to get all numbers divisible by 4). Now, if n=4k, do the following:

1, 12, 2, 10, 4, 8, 6, 7, 5, 9, 3, 11.

This will give 2k-1 n's, 2k-1 n+2's and two n+1's. Next, do

12, 14, 12, 14, 12, 14, 12, 14, 12, 14, 13, 13.

This gives 4k-2 2n+2's, one 2n+3 and one 2n+1.

Now, for simplicity, subtract 2n+2 from each number. We have all zeros but one +1 and one -1. Make the permutation so that we double the number of +1's and -1's in each step, until they become >n/4, then "mix them a bit"* so that in the next step we can exactly n/2 of both. Then an alternating sequence will give all equal numbers.

$^*Edit$: As Douglas pointed out this mixing is not that clear how to do. So instead, I claim that we for any i from 1 to n/2 it is possible to get exactly i +1's and i -1's. The proof is by induction - we either double or double -1, by putting a +1 and a -1 next to each other. Eventually we can get n/2 of each and we are done.

However, this my method only works for the numbers 1, 2, .. , n. What if we start from another sequence? Mod 2 the problem is always solvable, maybe that helps, but over Z already 1, 0, .. , 0 is not clear how to solve.

Edit: As Doublas pointed out this is possible if and only if n is a power of 2. So to summarize, I think if 4 does not divide n>1, then you can not get all equal numbers starting from 1, 2, .. , n, if 4 divides n you can, while if is n>2 is a power of 2, then it seems you can start from any sequence. (Though we have not seen a full proof of this last part yet.)