Show Random Walk Respects Identity

[Polo Lagrie]

Hi,

I have the following homework question:

Let Xt be the continuous-time simple random walk on a circle as in Example 2, Section 7.2. Show that there exists a c,β > 0, independent of N such that for all initial probability distributions ν and all t > 0

[tex]∥νe^tA−π∥_TV ≤ ce^(−βt/N2)[/tex]

Here's what I'm thinking so far:

We proved the following in class:

[tex]∥νe^tA−π∥_TV ≤ 1/2 ||e^(tA) v/π −1||_π[/tex]

I know I can apply this to the function above in the form:

[tex]∥νe^(tA) −π∥TV ≤1/2e^λ2t ||v/π||_π[/tex]But I'm now stuck. Any help would be greatly appreciated!

P.s. Sorry for the poor formatting--new at Latex.

 

[lippyka]

The trick here is to rewrite the equation as follows:∥νe^tA−π∥_TV ≤ ce^(−βt/N2) ⇔ ||e^(tA) v/π −1||_π ≤ 2ce^(−βt/N2) From there, you can use your definition of ||e^(tA) v/π −1||_π to come up with a bound for c and β.Let's start by writing out the definition of ||e^(tA) v/π −1||_π:||e^(tA) v/π −1||_π = ∑_i |e^(tA) v_i/π −1|We want to find a c and β such that this expression is less than or equal to 2ce^(−βt/N2). Let's start by considering only the exponential part. Since we know that e^(−βt/N2) ≤ 1, we can choose β such that e^(−βt/N2) = 1/2. This implies that β = ln(2N2/t). Now, for the rest of the expression, we can take the maximum value of |e^(tA) v_i/π −1| over all i. This will be the maximum value of the sum, and therefore can be used as an upper bound for c. For this expression, the maximum value occurs when e^(tA) v_i/π is maximized, which happens when v_i is maximized. So, we can choose c to be the maximum value of e^(tA) v_i/π, which is e^(tA) max_i v_i/π.Therefore, we have c = e^(tA) max_i v_i/π and β = ln(2N2/t), which are the desired constants.