Global AI and Data Science

STOP TIME

Consider a Coin Tossing Experiment where one goes on tossing the coin till HEAD turns up. If we denote the length of such runs by the Stop Time T, T takes values 0, 1, 2, 3, …. and P(T = n) = 1 / 2ⁿ that goes to zero as n increases.

 SPRT

As in classical hypothesis testing, SPRT starts with a pair of hypotheses, say H₀ and H^₁ for the null hypothesis and alternative hypothesis respectively. They must be specified as follows:

The next step is to calculate the cumulative sum of the log-likelihood ratio,

The stopping rule is a simple thresholding scheme:

where a and b (0 < a < b) depend on the desired type I and type II errors. They may be chosen as follows:

In other words, alpha and beta must be decided beforehand in order to set the thresholds appropriately. The numerical value will depend on the application. The reason for using approximation signs is that, in the discrete case, the signal may cross the threshold between samples. Thus, depending on the penalty of making an error and the sampling frequency, one might set the thresholds more aggressively. Of course, the exact bounds may be used in the continuous case.

STOP TIME OF SPRT FOR EXPONENTIAL MODEL

A textbook example is parameter estimation of a probability distribution function. Consider the exponential distribution:

The hypotheses are,

Then the log-likelihood function (LLF) for one sample is,

The cumulative sum of the LLFs for all x is,

Accordingly, the stopping rule is,

After re-arranging we finally find,

So the distribution of Stop Time is a scaled version of the distribution of sum x_i.

REMARKS

For SPRT with general model P and Composite Hypothesis, Prof. R. A. Wijsman (Annals of Statistics, 1971) developed an Exponential Bound of the Stop Time. As per my personal communication with Prof. J. K. Ghosh in a conference at Banaras Hindu University this bound could be heavily improved.

QUESTION I

Secretary Problem: You are supposed to choose the maximum number where a finite set of numbers are appearing one by one in a sequence and once you reject a number you are not allowed to choose it back. What would be your best strategy?

QUESTION II

Suppose the bus arrives at every 10 minutes interval at the bus stop. What would be the distribution of your Waiting Time (Stop Time) for the bus?