| (1) Minor suggestion
>TRACE::GILBERT
>Given that p is the probability of an element being a 1 (otherwise it is a 0),
>then the probability that the sum of m elements is even is given by
>
> [m/2]
> ====
> \ ( m ) m-2*i 2*i
> > ( ) (1 - p) p
> / (2*i)
> ====
> i=0
Yup.
>which is simply
>
> m
> (1-2*p)
Nearly. I make it:
m
�(1 + (1-2p) )
To believe this, firstly look at the examples p = 0,� & 1, and n = 0 &
% (infinity). Next see that if x & y are any variables, then:
m m
�( (x+y) + (x-y) )
will contain exactly the terms of even order in y. All we have here is the
special case y = p, x = 1-p. Denote 1-p by q.
(2) Some particular values of p.
p = 0: all row and column sums are always even.
p = �: the probability that all row and column sums are even is �^(m+n-1).
p = 1: need m & n both even, then evenness of sums is guaranteed.
(3) Simple cases: n = 1,2,3.
Now to return to our original problem, let P(m,n) [m,n>0] denote the
probability that all row-sums and all column-sums in an m by n array are
even. We ignore the distracting condition that at least one 1 must be
present, since that is a trivial tack-on at the end.
While pursuing trivia, we might as well say:
P(m,n) = P(n,m)
P(m,1) = q^m
Now P(m,2) we can get from the formula above, setting y = p�, and
x = q�, P(m,2) =
m m
�( (q�+p�) + (q�-p�) )
Note that this happens because each column must contain two elements the same,
for the column sum to be even. P(m,3) is not that easy. However, it is
"obvious" :-) that:
P(m+1,3) = q�*P(m,3) + p�q*[ (q�+3p�q)^m - P(m,3) ]
= (q�-p�q)*P(m,3) + p�q*(q�+3p�q)^m
P(m,3) = sum(j=0,...m-1) (q�-p�q)^j * (q�+3p�q)^(m-j) * p�q
+ (q�-p�q)^m
= [ (q�+3p�q)^m + 3(q�-p�q)^m ] / 4
This works for p = 0,�,1.
(4) n >= 4
Let P(m,4) be as before. Let Q(m,4) be the probability that all
column sums are even, and all row sums are odd. Then, using the same trick
as before:
P(m+1,4) = q^4*P(m,4) + p^4*Q(m,4)
+ p�q�*[ (p^4 + 6p�q� + q^4)^m - P(m,4) - Q(m,4)]
Q(m+1,4) = p^4*P(m,4) + q^4*Q(m,4)
+ p�q�*[ (p^4 + 6p�q� + q^4)^m - P(m,4) - Q(m,4)]
The only real difference between P & Q is in the transient:
P(0,4) = 1, Q(0,4) = 0.
Letting S = P+Q, R = P-Q
S = (p^4+q^4)*S + 2*p�q�*[(p^4 - 6p�q� + q^4) - S]
= (p^4 -2p�q� +q^4)*S + 2*p�q�*(p^4 - 6p�q� + q^4)
R = (q^4-p^4)*R
is clearly going to give us the answer for P(m,4). The question is, what is
the function as n becomes still bigger?
We say that K(m,n,x) is the probability that an array of m columns and
n rows has the properties:
(1) each column sum is odd
(2) exactly x of the row sums are odd.
Note: (i) K(m,n,0) = P(m,n)
(ii) K(m,n,x) = 0 if x is odd
Then we can build a recursion in m. We can see that this will
give us the vector K(m+1,n,.) as a linear function of K(m,n,.). Thus
K(m,n,.) is expressible as a sum of mth powers of various functions of p&q
(n being held constant all the while).
I haven't time to take this further.
Regards,
Andrew.
|