Computer Science – Information Theory
Scientific paper
2012-03-20
Computer Science
Information Theory
26 pages, 2 figures, submitted to IEEE Transactions on Information Theory
Scientific paper
Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declaration. The special cases of the problem are shown to be that of variable-length coding with feedback and noisy dynamic search. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively select the most "informative" sensing action among the available ones. In this paper, using results in dynamic programming, a lower bound for the optimal total cost is established. Moreover, upper bounds are obtained via an analysis of heuristic policies for dynamic selection of actions. It is shown that the proposed heuristics achieve asymptotic optimality in many practically relevant problems including the problems of variable-length coding with feedback and noisy dynamic search; where asymptotic optimality implies that the relative difference between the total cost achieved by the proposed policies and the optimal total cost approaches zero as the penalty of wrong declaration or the number of hypotheses (hence the number of collected samples) increases. Furthermore, using the obtained bounds, the gain of adaptive selection of sensing actions is shown to be at least logarithmic in the penalty associated with wrong declarations.
Javidi Tara
Naghshvar Mohammad
No associations
LandOfFree
Active Sequential Hypothesis Testing 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 Active Sequential Hypothesis Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Active Sequential Hypothesis Testing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-487823