Search for: All records

ABSTRACT Given a reversible Markov chain on states, and another chain obtained by perturbing each row of by at most in total variation, we study the total variation distance between the two stationary distributions, . We show that for chains withcutoff, converges to 0, is asymptotically at most (with a sequence of perturbations for which convergence to this bound occurs), and converges to 1, respectively, if the product of and the mixing time of converges to 0, , and , respectively. This echoes recent results for specific random walks that exhibit cutoff, suggesting that cutoff is the key property underlying such results. Moreover, we show is maximized byrestart perturbations, for which “restarts” at a random state with probability at each step. Finally, we show thatpre‐cutoffis (almost) equivalent to a notion of “sensitivity to restart perturbations,” suggesting that chains with sharper convergence to stationarity are inherently less robust. 

Abstract In this paper, we study a new discrete tree and the resulting branching process, which we call the erlang weighted tree(EWT). The EWT appears as the local weak limit of a random graph model proposed in La and Kabkab, Internet Math. 11 (2015), no. 6, 528–554. In contrast to the local weak limit of well‐known random graph models, the EWT has an interdependent structure. In particular, its vertices encode a multi‐type branching process with uncountably many types. We derive the main properties of the EWT, such as the probability of extinction, growth rate, and so forth. We show that the probability of extinction is the smallest fixed point of an operator. We then take a point process perspective and analyze the growth rate operator. We derive the Krein–Rutman eigenvalue and the corresponding eigenfunctions of the growth operator, and show that the probability of extinction equals one if and only if . 

The work studies cooperative decentralized constrained POMDPs with asymmetric information. Using an extension of Sion's Minimax theorem for functions with positive infinity and results on weak-convergence of measures, strong duality and existence of a saddle point are established for the setting of infinite-horizon expected total discounted costs when the observations lie in a countable space, the actions are chosen from a finite space, the immediate constraint costs are bounded, and the immediate objective cost is bounded from below.