The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math.research

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
robert egri

Posts: 98
Registered: 12/13/04
random matrix
Posted: May 13, 2011 8:37 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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?


Date Subject Author
Read random matrix
robert egri
Read Re: random matrix
Ilmari Karonen

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.