13

Let's say we have a vector $v = (x_1, ..., x_n) \in \mathbb{N}^n$ where $x_1 = x_2 = ... = x_n$. Next we choose an ordered pair of coordinates at random $(i, j)$ where $i, j \in \{1, ..., n\}$ and $i \neq j$. Finally we substitute the vector $v$ with a new vector $v' = (x_1, ..., x_i + 1, ..., x_j - 1, ..., x_n)$. Now we choose again an ordered pair of coordinates at random and substitute the vector $v'$ with a new vector doing the same we did for $v$. We continue doing this until one of the coordinates becomes zero.
What is the expected number of operations we are going to make?

I know the answer for $n = 2$ because you can model this process with a random walk. If $v = (x, x)$, then the expected number of operations is the same as the expected number of steps it will take to hit $x$ or $-x$ doing a random walk starting at zero. In this case the expected number of step starting at $y$ satisfies the recurrence relation $$E_y = 1 + \frac{1}{2} E_{y - 1} + \frac{1}{2} E_{y + 1}. $$ Then one can solve this linear recurrence.
I tried to do the same for the original problem but the recurrence relation is more difficult. Let $F_{(x_1, ..., x_n)}$ be the expected number of operations one can make to vector $v= (x_1, ..., x_n)$ before one of the coordinates becomes zero (in this case we allow $x_1, ..., x_n$ to be different). If I'm not wrong $F$ satisfies the following relation $$F_{(x_1, ..., x_n)} = 1 + \sum_{i, j} \frac{1}{n (n - 1)} F_{(x_1, ..., x_n) + e_{i, j}}, $$ where the $i$-th coordiante of $e_{i, j}$ is $1$, the $j$-th is $-1$ and the rest are all zero (the sum runs through all possible operations).

Sebastián Reca
  • 141
  • 1
    The operation you are considering is called an (elementary?) raising operator (a general raising operator is a product of perhaps repeated elementary ones). There is a partial order on $\mathbb Z^n$ given by $a \geqslant b$ iff for each $i$ we have $a_1+\cdots+a_i\geqslant b_1+\cdots+b_i$, and raising operators are nondecreasing for this order. – Pedro Mar 04 '18 at 02:09
  • 1
    Note that raising operators do not modify the total weight of vectors. Moreover, whenever $a$ and $b$ are of equal weight and $a\leqslant b$, there is a raising operator $R$ such that $Ra =b$. It is not clear if this should really help here, though, but perhaps knowing these operators have a name might help in searching for references. Buena suerte! ;) – Pedro Mar 04 '18 at 02:09
  • I think we can project the movement to hyperplane $x_1+\cdots+x_n=nN$, where $N=x_1=\cdots=x_n$ is the initial coordinate of $v$. With the stopping condition(i.e. stop when some coordinate becomes zero) we are on a bounded domain, with each transition $(0,\cdots,1,\cdots,-1,\cdots,0)$ parallel to some boundary line $x_k=0,k\not\in{i,j},x_i+x_j=nN$. Seem like we can reduce the dimension...will this help? – MikeG Feb 21 '21 at 07:26

0 Answers0