Situation we are to conjecture about.
Ben Edwards
conjecture about, was it something like:
Let P and P' be stochastic matrices with stationary distributions
\pi_P and \pi_P', what can we say about Q=(P+P')/2, specifically \pi_Q
Thomas Hayes
George Stelle
There is no pair of linear maps M, M', s.t. pi_q = M pi + M' pi' for all possible pi, pi'. In other words, there is no fixed linear combination of pi and pi' that is always equal to p_q. Thus, if it is possible to come up with some M and M', they must be functions of P and P' (or pi and pi').
In the special case where pi + pi' = pi P' + pi' P, pi_q = (pi + pi')/2.
George
George Stelle
UNM fud Student
Thomas Hayes
Please post your ideas, even if you can already see the conjecture is false.
You have to start somewhere.
One comments on George's conjectures:
On Fri, Sep 17, 2010 at 10:49 AM, George Stelle <ste...@gmail.com> wrote:
> A couple of simple (obvious?) conjectures to get us started.
>
> There is no pair of linear maps M, M', s.t. pi_q = M pi + M' pi' for all
> possible pi, pi'. In other words, there is no fixed linear combination of
> pi and pi' that is always equal to p_q. Thus, if it is possible to come up
> with some M and M', they must be functions of P and P' (or pi and pi').
>
> In the special case where pi + pi' = pi P' + pi' P, pi_q = (pi + pi')/2.
This special case includes the important case when pi = pi'. Is this all,
or does it include other interesting cases?
Now, has anyone resolved these yet?
Tom
Olumuyiwa Oluwasanmi
and trace((A+B)/2 ) is the average of the eigenvalues of the matrix A and B.
One special case that I can see is if the eigenvector of (A+B) are decomposable in a certain way say v_a is the eigenvector of A and v_b is the eigenvector of B(both in the stationary distribution) and v is the eigenvector of A +B
and we can write v as c_1v_a +c_2v_b then (A+B)(c_1v_a +c_2v_b) =(c_1v_a +c_2v_b) for the stationary distribution.
=(c_1v_a +c_2v_b) + c_2Av_b +c_1B_v_a =(c_1v_a +c_2v_b)
under this condition, one would assume that c_2Av_b +c_1B_v_a =0 being a reasonable assumption the special case in class would be the case of say v_a being an eigenvector of B with some other eigenvalue and ditto for v_b being an eigenvector of A with some other eigenvalue we can calculate easily the constants c_1 and c_2.
--
Olumuyiwa Oluwasanmi
www.cs.unm.edu/~muyiwa
505-480-5878
Ben Edwards
something about the stationary distribution?
How about something simpler?
If P and P' have unique stationary distributions, then so does Q.
Olumuyiwa Oluwasanmi
Thomas Hayes
1) We know that, if pi_P = pi_{P'} then pi_Q also equals this.
is it true that, if pi_P is very close to pi_{P'}, then pi_Q is also
close by?
2) Is it true that, for every x, pi_Q(x) is in between pi_P(x) and pi_{P'}(x)?
In other words, pi_Q is between the elementwise min and max of pi_P
and pi_{P'}? Is pi_Q less than the sum pi_P plus pi_{P'}?
3) What about convergence? If the Markov chains for P and P' converge
quickly, can we say that the Markov chain for Q converges quickly?
What if we also assume pi_P = pi_{P'}?
I don't necessarily have answers for all of these...
Tom
Olumuyiwa Oluwasanmi
if ||pi_P -pi_{P'}||_{2} < epsilon, where epsilon is some very small real and positive number then we can say
more generally that |pi_P- pi_{P'}|<epsilon.x , where x is some arbitrary vector, then we can
say pi_P< pi_{P'} + epsilon.x , then pi_P(P+P')/2=1/2.(pi_P +pi_P.P')<1/2(pi_P + (pi_{P'} + epsilon.x).P')
= 1/2((pi_P + pi_{P'} + epsilon.x.P' ) which is the average of the distributions as epsilon goes to 0. Similarly, we can construct a lower bound on the stationary distribution.
3) Definitely a yes, in the case of a symmetric P and P' from the trace of P' and P we can establish an upper bound on the eigenvalues of Q if P and P' are symmetric see the articles http://www.scielo.cl/pdf/proy/v22n2/art03.pdf
and http://www.ams.org/notices/200102/fea-knutson.pdf,
we have the average of the corresponding eigenvalues of P and P' as an upper bound on the eigenvalues of Q which implies fast convergence for Q if P and P' converge fast, the convergence of Q will be somewhat between that of P and P'.
2) The answer to 3) somehow feeds back into 2) as well this may imply that 2) is true in the Symmetric case.
Olumuyiwa Oluwasanmi
I need to be careful about using < sign without norms should have used ||1/2.(pi_P +pi_P.P') -Q||=||1/2.(pi_P +pi_P.P') -1/2(pi_P + (pi_{P'} + epsilon.x).P')||=||epsilon.x -epsilon.y|| , where y=P'x
-> epsilon||x -y|| so we the eigenvector of Q remains close as well.
secondly, we need to be careful as we are dealing with distributions(sum of the entry of vectors are 1)
we can treat pi's as plain old eigenvectors in a more general sense.