Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



random matrix
Posted:
May 13, 2011 8:37 AM


Hello
Take two integers M and N, 0 < M < N, and a number p, 0<p<1. Generate a random NxN matrix whose elements a_ij={0,1} iid and Pr{a_ij=1} = p.
We transform the matrix by flipping certain 1s into 0s by some process as described below. My question is the distribution of the number of steps S it takes to transform the initial matrix into an all 0 matrix (stopping criterion); the distribution of the integer r.v. S depends on N, M, p.
If all matrix elements are 0 then S=0. If not then we process the columns as follows: going from column index j=1 to N, if in column j the number of 1s does not exceed M then in this column we flip every 1 to 0, if the number of 1s exceed M then we leave that column as it is and move to the next. If now all 1s of the matrix will have flipped to 0 then we stop (r.v. S=1).
If not all 1s are flipped then we move on to process the rows the same way: for row index i=1 to N we count the number of 1s row i and if the number does not exceed M then in this row i we flip every 1 to 0, but if it exceeds M then we do not do anything and move to the next row. If now all 1s of the matrix are flipped into 0 then we stop: S=2.
If we still have some 1s left in the matrix then we will process again the columns, then the rows, and so on.
My first question would be the distribution of S but if that is hopeless to calculate I have two others that maybe easier to answer:
1. what is the expected value E{S} and variance of V{S} given N,M,p? 2. are there thresholds p1(N,M) and p2(N,M) such that if p<p1 then Pr{S<inf}=1 but if p>p2 then Pr{S=inf}=1?
thanks Robert



