Committee:
Beck, Carolyn (Chair, Director)
Srikant, Rayadurgam (Chair, Director)
Katselis, Dimitrios (Member)
Sowers, Richard (Member)
Varshney, Lav (Member)
Data Analytics
Asymptotic and Non-asymptotic analysis for the Identification of Structured Discrete Systems Over Networks
This thesis focuses on the identification problem of a specific structured discrete-state dynamic system, which is driven by a class of binary autoregressive models, called the Bernoulli Autoregressive (BAR) model. The model is defined over a network of nodes, where each node can be at a state of 0 or 1 at each time instant. And the probability of a node being 1 at the current state depends on states of its parental nodes in the previous time instant and a Bernoulli noise term. Such interactions between nodes are exactly captured by the underlying network. Therefore, the parameter estimation of the BAR model naturally produces the structure inference of the network. The considered identification method is the Maximum Likelihood estimation, a powerful classical estimation method which has a long history dating back to the 1920s and enjoys wide applicability and versatility in statistical inference, system identification, and machine learning. Motivated by its nice invariance property in reparametrization, we also derive a closed-form ML estimator, called the indirect ML estimator throughout the thesis. We show that both estimators are strongly consistent, that is, they converge to the corresponding true values almost surely as the number of observations goes to infinity. Besides, the strong consistency can be shown to hold for both the ML and the indirect ML estimators of a more general form of the BAR model. We are also interested in whether the estimators can achieve probably correct estimation with finite samples from a single trajectory. For this purpose, we establish a finite-sample bound for the indirect ML estimator by leveraging several concentration results, one of which is concerned with the transportation method. Finally, we extend this concentration result and show that it can be applied to derive sharper finite-sample error bounds for estimating the stationary distribution of an ergodic, discrete-time, finte-state Markov chain.
