Testing for Directed Information Graphs
| Autor: | Mikael Skoglund, Sina Molavipour, German Bassi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Markov chain Computer science Stochastic process Computer Science - Information Theory Information Theory (cs.IT) 020206 networking & telecommunications 02 engineering and technology Directed graph 03 medical and health sciences 0302 clinical medicine Asymptotically optimal algorithm Metric (mathematics) Convergence (routing) 0202 electrical engineering electronic engineering information engineering Sannolikhetsteori och statistik False alarm Probability Theory and Statistics Algorithm 030217 neurology & neurosurgery Statistical hypothesis testing |
| Popis: | In this paper, we study a hypothesis test to determine the underlying directed graph structure of nodes in a network, where the nodes represent random processes and the direction of the links indicate a causal relationship between said processes. Specifically, a k-th order Markov structure is considered for them, and the chosen metric to determine a connection between nodes is the directed information. The hypothesis test is based on the empirically calculated transition probabilities which are used to estimate the directed information. For a single edge, it is proven that the detection probability can be chosen arbitrarily close to one, while the false alarm probability remains negligible. When the test is performed on the whole graph, we derive bounds for the false alarm and detection probabilities, which show that the test is asymptotically optimal by properly setting the threshold test and using a large number of samples. Furthermore, we study how the convergence of the measures relies on the existence of links in the true graph. Comment: 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2017 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|