Expected number of operations until matrix contains no zeros.

Question

Let $A_{ij}$ be a $n\times n$ matrix of all zeros ($a_{ij} = 0, \forall i,j$). Consider the following operation: Choose three numbers $x,y,z \in \{1,\ldots,n\}$ at random (with replacement). Decrease one of $a_{xy}, a_{yz}$ by 1 and increase $a_{xz}$ by 1.

What is the expected number of these operations until $a_{ij} \neq 0, \forall i,j$?

Motivation

I was implementing a dynamical graph with a local, parallel update rule and realized that some edges could be "deleted" more than once. Trying to think of a work-around, I considered working with a complete graph where one just decrements edge-weights instead of deleting edges. ($A$ can be viewed as a weighted adjacency matrix of a complete digraph with edge-weights $=0$.) Unfortunately, this trivializes the "local" part of the rule, but the above question struck me as interesting.

Perhaps even more interesting: What is the expected number of operations until the graph $G=\{V,E\}$ with $V=\{1,\ldots,n\}$ and $E=\{(i,j) |a_{ij}=0\}$ is disconnected?

I'll include the code I used to explore this problem for completeness:

from random import randint

def operation():
    x=randint(0, n-1)
    y=randint(0, n-1)
    z=randint(0, n-1)
    A[x][z]+=1
    if randint(0,1)==0:
        A[x][y]-=1
    else:
        A[y][z]-=1

def has_zeros(): #Return True if A has zeros
    zeros=False
    for i in range(n):
        for j in range(n):
            if A[i][j]==0:
                zeros=True
                break
        if zeros:
            break
    return zeros 

n=100 #Dimension of matrix
A=[[0 for x in range(n)] for y in range(n)] #Zero-matrix

moves=0
#Main loop
while has_zeros():
    operation()
    moves+=1

print(moves,'total moves.')

To explore the graph question, include:

import networkx as nx   
def zero_graph_connected():
    G=nx.DiGraph()
    #Build graph from matrix
    for j in range(n):
        G.add_node(j) #nothing happens if j is already a node of G
        for k in range(n):
            if A[j][k]==0:
                G.add_edge(j,k) #node k will be added automatically
    return nx.is_connected(G.to_undirected()) #Is graph connected?

And change the main loop to:

while zero_graph_connected():
    operation()
    moves+=1

As a bonus I've plotted 3 trials of number of operations for $A$ to contain no zeros up to $n=25$:

And 3 trials of number of operations for $G$ to disconnect up to $n=25$:

Answer 1

1. At the first step, we can compute the probability of $A[i][j]=0$. In other words $$p=\Pr\{A[i][j] = 0\}=?, \quad 1\leq i,j\leq n$$

2. The constructed graph with the mentioned rules is a random graph $G(n,p)$, so if $p\geq \frac{(1+\epsilon)}{n}$, then there exist a giant component with size $O(n)$, almost all of vertices are in the same component. Otherwise, there is no a giant component with linear size.

---

Now, I compute the value of $p$. Let $N$ be the number of operations, and $N$ is even. \begin{align} p &=\Pr\{A[i][j] = 0\} \\& = \Pr\{\text{A[i][j] doest not change in the process}\} + \Pr\{\text{the number of increments and decrements are equal}\} \\ & = (1-\frac{1}{n^{2}})^{2N} + \Bigg[\Big(\binom{2N}{2}\big((\frac{1}{n^{2}})^{1}\times (\frac{1}{n^{2}})^{1}\big)\times(1-\frac{1}{n^{2}})^{2N-2}\Big) + ... + \Big(\binom{2N}{2N}\big((\frac{1}{n^{2}})^{N}\times (\frac{1}{n^{2}})^{N}\big)\times(1-\frac{1}{n^{2}})^{2N-2N}\Big) \Bigg] \\ & = (1-\frac{1}{n^{2}})^{2N} +\sum_{i=1}^{N}\binom{2N}{2i}\big((\frac{1}{n^{2}})^{i}\times (\frac{1}{n^{2}})^{i}\big)\times(1-\frac{1}{n^{2}})^{2N-2i} \end{align}