| CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| ith X 0 = x and Y 0 = y. We define the coupling as follows: X t and Y t both choose the same i and the same b at every step. Clearly this satisfies the two conditions (i) and (ii) in the above definition, so it is a valid coupling. Now the two copies must certainly coincide after each coordinate i has been chosen at least once. Hence max x,y T xy is dominated by the time T until all coupons are collected in the coupon collector's problem (here 5-1 we have n "coupons", one per coordinate). Recall that for the coupon collector problem Pr[T > n ln n+cn] < e -c for any c > 0. Thus we get from the above theorem that #(n ln(n) + cn) e -c or equivalently, that #(#) n ln(n) + n ln(# -1 ). In particular, # mix n ln n + O(n). This is the same value as we got using the Strong Stationary Time, and is tight up to constants. (Recall that # mix 2 n ln n.) The above analysis is made rather trite by the self-loop probability of 2 . Let's consider a variation of the same problem with self-lo | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||