Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: random matrix
Replies: 1   Last Post: May 13, 2011 3:43 PM

 Messages: [ Previous | Next ]
 robert egri Posts: 98 Registered: 12/13/04
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 1-s into 0-s 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 1-s does not exceed M then in this column we flip every 1
to 0, if the number of 1-s exceed M then we leave that column as it is
and move to the next. If now all 1-s of the matrix will have flipped to
0 then we stop (r.v. S=1).

If not all 1-s 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 1-s 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 1-s of the matrix are flipped into 0 then we stop: S=2.

If we still have some 1-s 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

Date Subject Author
5/13/11 robert egri
5/13/11 Ilmari Karonen