Subexponential convergence for information aggregation on regular trees

Details Subexponential convergence for information aggregation on regular trees Subexponential convergence for information aggregation on regular trees

2011-04-14

arxiv.org/abs/1104.2939v1

Computer Science

Multiagent Systems

8 pages, submitted

Scientific paper

We consider the decentralized binary hypothesis testing problem on trees of bounded degree and increasing depth. For a regular tree of depth t and branching factor k>=2, we assume that the leaves have access to independent and identically distributed noisy observations of the 'state of the world' s. Starting with the leaves, each node makes a decision in a finite alphabet M, that it sends to its parent in the tree. Finally, the root decides between the two possible states of the world based on the information it receives. We prove that the error probability vanishes only subexponentially in the number of available observations, under quite general hypotheses. More precisely the case of binary messages, decay is subexponential for any decision rule. For general (finite) message alphabet M, decay is subexponential for 'node-oblivious' decision rules, that satisfy a mild irreducibility condition. In the latter case, we propose a family of decision rules with close-to-optimal asymptotic behavior.

Affiliated with

Also associated with

No associations

Rating

Subexponential convergence for information aggregation on regular trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subexponential convergence for information aggregation on regular trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subexponential convergence for information aggregation on regular trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8071