Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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 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
|
|
|
|
