# TU Darmstadt ULB TUbiblio

# Design and Analysis of Optimal and Minimax Robust Sequential Hypothesis Tests

## Abstract

In this dissertation a framework for the design and analysis of optimal and minimax robust sequential hypothesis tests is developed. It provides a coherent theory as well as algorithms for the implementation of optimal and minimax robust sequential tests in practice.

After introducing some fundamental concepts of sequential analysis and optimal stopping theory, the optimal sequential test for stochastic processes with Markovian representations is derived. This is done by formulating the sequential testing problem as an optimal stopping problem whose cost function is given by a weighted sum of the expected run-length and the error probabilities of the test. Based on this formulation, a cost minimizing testing policy can be obtained by solving a nonlinear integral equation. It is then shown that the partial generalized derivatives of the optimal cost function are, up to a constant scaling factor, identical to the error probabilities of the cost minimizing test. This relation is used to formulate the problem of designing optimal sequential tests under constraints on the error probabilities as a problem of solving an integral equation under constraints on the partial derivatives of its solution function. Finally, it is shown that the latter problem can be solved by means of standard linear programming techniques without the need to calculate the partial derivatives explicitly. Numerical examples are given to illustrate this procedure.

The second half of the dissertation is concerned with the design of minimax robust sequential hypothesis tests. First, the minimax principle and a general model for distributional uncertainties is introduced. Subsequently, sufficient conditions are derived for distributions to be least favorable with respect to the expected run-length and error probabilities of a sequential test. Combining the results on optimal sequential tests and least favorable distributions yields a sufficient condition for a sequential test to be minimax optimal under general distributional uncertainties. The cost function of the minimax optimal test is further identified as a convex statistical similarity measure and the least favorable distributions as the distributions that are most similar with respect to this measure. In order to obtain more specific results, the density band model is introduced as an example for a nonparametric uncertainty model. The corresponding least favorable distributions are stated in an implicit form, based on which a simple algorithm for their numerical calculation is derived. Finally, the minimax robust sequential test under density band uncertainties is discussed and shown to admit the characteristic minimax property of a maximally flat performance profile over its state space. A numerical example for a minimax optimal sequential test completes the dissertation.

Item Type: Ph.D. Thesis
Erschienen: 2016
Creators: Fauß, M.
Title: Design and Analysis of Optimal and Minimax Robust Sequential Hypothesis Tests
Language: English
Abstract:

In this dissertation a framework for the design and analysis of optimal and minimax robust sequential hypothesis tests is developed. It provides a coherent theory as well as algorithms for the implementation of optimal and minimax robust sequential tests in practice.

After introducing some fundamental concepts of sequential analysis and optimal stopping theory, the optimal sequential test for stochastic processes with Markovian representations is derived. This is done by formulating the sequential testing problem as an optimal stopping problem whose cost function is given by a weighted sum of the expected run-length and the error probabilities of the test. Based on this formulation, a cost minimizing testing policy can be obtained by solving a nonlinear integral equation. It is then shown that the partial generalized derivatives of the optimal cost function are, up to a constant scaling factor, identical to the error probabilities of the cost minimizing test. This relation is used to formulate the problem of designing optimal sequential tests under constraints on the error probabilities as a problem of solving an integral equation under constraints on the partial derivatives of its solution function. Finally, it is shown that the latter problem can be solved by means of standard linear programming techniques without the need to calculate the partial derivatives explicitly. Numerical examples are given to illustrate this procedure.

The second half of the dissertation is concerned with the design of minimax robust sequential hypothesis tests. First, the minimax principle and a general model for distributional uncertainties is introduced. Subsequently, sufficient conditions are derived for distributions to be least favorable with respect to the expected run-length and error probabilities of a sequential test. Combining the results on optimal sequential tests and least favorable distributions yields a sufficient condition for a sequential test to be minimax optimal under general distributional uncertainties. The cost function of the minimax optimal test is further identified as a convex statistical similarity measure and the least favorable distributions as the distributions that are most similar with respect to this measure. In order to obtain more specific results, the density band model is introduced as an example for a nonparametric uncertainty model. The corresponding least favorable distributions are stated in an implicit form, based on which a simple algorithm for their numerical calculation is derived. Finally, the minimax robust sequential test under density band uncertainties is discussed and shown to admit the characteristic minimax property of a maximally flat performance profile over its state space. A numerical example for a minimax optimal sequential test completes the dissertation.

Uncontrolled Keywords: Sequential Analysis, sequential Detection, sequential hypothesis test, optimal stopping, minimax robustness, distributional uncertainty, linear programming, convex functionals, statistical similarity
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Signal Processing
18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications
Date Deposited: 12 Jun 2016 19:55
URN: urn:nbn:de:tuda-tuprints-54941
Referees: Zoubir, Prof. Dr. Abdelhak M. ; Poor, Prof. Dr. Vincent H.
Refereed / Verteidigung / mdl. Prüfung: 1 March 2016
Alternative Abstract:
Alternative abstract Language

In dieser Dissertation wird ein Verfahren zum Entwurf und zur Analyse von optimalen und minimax robusten equentiellen Hypothesentests entwickelt. Die Arbeit umfasst sowohl einen umfassenden Theorieteil als auch Algortihmen zur praktischen Implementierung robuster sequentieller Tests.

Nach einer Einführung in die grundlegenden Konzepte der sequentiellen Analyse und der Stoppzeit-Theorie, wird der optimale sequentielle Test für stochastische Prozesse mit Markov-Darstellung hergeleitet. Zu diesem Zweck wird das Problem des Entwurfs sequentieller Tests in ein Problem der Ermittlung optimaler Stoppzeiten überführt, dessen Kostenfunktion sich aus der zu erwartenden Laufzeit und den gwichteten Fehlerwahrscheinlichkeiten des Tests zusammensetzt. Aufbauend auf dieser Formulierung kann die Strategie eines mit minimalen Kosten verbundenen sequentiellen Tests durch Lösung einer nichtlinearen Integralgleichung bestimmt werden. In der Dissertation wird nachgewiesen, dass die partiellen Ableitung der Kostenfunktion des optimalen Tests bis auf eine konstante Skalierung mit den Fehlerwahrscheinlichkeiten des zugrunde liegenden sequentiellen Tests übereinstimmen. Mit Hilfe dieses Zusammenhangs lässt sich der Entwurfs optimaler sequentieller Test mit beschränkten Fehlerwahrscheinlichkeiten auf die Lösung einer Integralgleichung zurückführen, deren Lösungsfunktion zusätzliche Bedingungen an ihre partiellen Ableitungen erfüllen muss. Es wird weiterhin gezeigt, dass die gesuchte Lösungsfunktion sich mittels etablierter Methoden der linearen Optimierung bestimmen lässt, ohne die partiellen Ableitungen explizit zu berechnen. Das Verfahren wird anhand mehrere numerischer Beispiele veranschaulicht.

In der zweiten Hälfte der Dissertation wird der Entwurf minimax robuster sequentieller Tests behandelt. Zunächst werden das Minimax-Prinzip und ein allgemeines Model für Unsicherheiten in den Verteilungen eingeführt und erläutert. Danach werden hinreichende Bedingungen dafür hergeleitet, dass gegebene Wahrscheinlichkeitsverteilungen am ungünstigsten sind, das heißt, zu der größten mittleren Laufzeit und den größten Fehlerwahrscheinlichkeiten eines sequentiellen Tests führen. Durch Zusammenführung der Ergebnisse zu optimalen sequentiellen Tests und ungünstigsten Verteilungen ergeben sich hinreichende Bedingungen für die minimax Optimalität sequentieller Tests unter allgemeinen Verteilungsunsicherheiten. Des Weiteren wird die Kostenfunktion des minimax optimalen Tests als ein konvexes statistisches Ähnlichkeitsmaß identifiziert und die ungünstigsten Verteilungen als diejenigen, welche die größte Ähnlichkeit bezüglich dieses Maßes aufweisen. Als konkretes Beispiel für nichtparametrische Verteilungsunsicherheiten wird das Dichte-Band-Modell (density band model) eingeführt. Die sich aus diesem Modell ergebenden ungünstigsten Verteilungen werden zunächst in impliziter Form hergeleitet. Basierend auf der implizierten Darstellung wird ein Algorithmus zu ihrer numerische Berechnung entwickelt. Schließlich wird der minimax robuste sequentielle Test unter Unsicherheiten des Dichte-Band-Typs hergeleitet, welcher die für minimax Verfahren charakteristische Eigenschaft eines maximal flachen Profils der Laufzeiten und Fehlerwahrscheinlichkeiten über dem Zustandsraum aufweist. Ein numerisches Beispiel für einen minimax optimalen sequentiellen Test schließt die Dissertation ab.

German
Export:
Suche nach Titel in: TUfind oder in Google Send an inquiry

Options (only for editors) Show editorial Details