Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimal-stopping]

The tag has no usage guidance.

2
votes
1answer
89 views

ABC: Population Monte Carlo (PMC) convergence statistics?

I'm using the abcpmc code: Approximate Bayesian Computing (ABC) Population Monte Carlo (PMC) implementation based on Sequential Monte Carlo (SMC) with Particle Filtering techniques. described in ...
0
votes
0answers
48 views

The Secretary Problem for Unknown Number of Candidates

In the secretary problem, the optimal strategy is to reject the first n/e and start selecting the best that is better than the best one in the n/e candidates. For example, if the number of candidates ...
10
votes
1answer
389 views

The Fishing Problem

Suppose you want to go fishing at the nearby lake from 8AM-8PM. Due to overfishing, a law has been instated that says you may only catch one fish per day. When you catch a fish, you can choose to ...
1
vote
0answers
67 views

Neural network training: going backward to go forward?

I am working on CNN models which are intended to predict a protein's structure from its amino acid sequence. I have a decently large data set, 750 protein structures containing over 100,000 amino ...
1
vote
0answers
36 views

At which rank should I reasonably stop selecting interview candidates?

It seems that my problem could be classified as an "optimal stopping" problem, but I am unable to make much of this information. It is an important problem for my organisation (an NGO), in order to ...
0
votes
0answers
19 views

loss function for stopping problem

I want to test different algorithms for predicting when a person stops an activity. The information available to the person (and the algorithms) consists of different performance criteria and other ...
0
votes
0answers
17 views

How to choose iterations end automatically by exponential measure?

I have likelihood growing in the following way Suppose the curve is monotonical and never reaches maximum, like exponent. Is there a common way to choose when to stop iterations automatically? Just ...
4
votes
0answers
39 views

“Approved” switch criterion for the Secretary problem

The secretary problem ( 1, 2, 3, 4, 5 ) optimal stopping, says "stop and keep the best" in a randomized sequence of known length "k" where you can't select previously elements of the sequence. One ...
1
vote
1answer
107 views

Simulation of Secretary problem: optimal pool size given k=2?

Question: Is it incorrect to think there is a "sweet spot" where more samples slightly decreases the likelihood of a "Best pick" in the Secretary Problem? Details: The "Secretary Problem" from "...
11
votes
2answers
2k views

Why is it wrong to stop an A/B test before optimal sample size is reached?

I am in charge of presenting the results of A/B tests (run on website variations) at my company. We run the test for a month and then check the p-values at regular intervals until we reach ...
4
votes
2answers
142 views

Optimal decision process to estimate Markov chain limiting distribution

Suppose there is a irreducible, reversible Markov chain with known states $1,\ldots,N$ and unknown transition matrix $T_{ij}$ and unknown limiting distribution $\pi_i$. I am able to repeatedly ...
3
votes
1answer
97 views

Prove $Z_n = X_n1_{n \le T} + Y_n1_{n+1\ge T}$ is a martingale

Given a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}, \mathbb P)$, let $X = (X_n)_{n \in \mathbb N}$ and $Y = (Y_n)_{n \in \mathbb N}$ be $(\{\mathscr F_n\}, \mathbb P)-$...
1
vote
1answer
57 views

Prove Doob's using a certain Lemma

I am to prove Doob's (d) in the red box below: What I tried: Since $T < \infty$ a.s., we have $$E[X_T] = E[\lim X_{T \wedge n}].$$ By Fatou's Lemma, we have $$E\left[\lim X_{T \wedge n}\right] ...
2
votes
1answer
133 views

How to show that $S \wedge T, S \vee T, S + T$ are stopping times?

From Williams (1991) Probability with Martingales: $$(S \wedge T \le n) = (S \le n) \cup (T \le n) \in \mathscr F_n$$ $$\because (S \le n), (T \le n) \in \mathscr F_n$$ $$(S \ \vee \ T \le n) = (S \...
1
vote
0answers
130 views

Optimal stopping rule for sequential subsampling?

I have a set of ranking models added sequential one at a time. Where each model generate ranks for the sample. Finally the expected rank is done by taking the average rank from all models. scenario I ...
2
votes
1answer
781 views

Secretary Problem (Optimal Stopping) When Interviews Are Costly

The Secretary problem is an optimal stopping problem. Imagine hiring one secretary out of $n$ applicants, who are interviewed in random order and either rejected or hired on the spot (as soon as one ...
4
votes
0answers
306 views

Optimal Stopping for Bernoulli One-Armed Bandit with a Fixed, Known Payout

I'm very new to bandit problems (apologies if I've formatted my question incorrectly), but I have to solve the optimal stopping of what I think is a very simple case. Suppose I have two arms $k = {1, ...
0
votes
0answers
48 views

How important is the quality of solutions to NP-hard problems arising in machine learning problems?

Machine learning and inference problems give rise to intractable problems. For instance the exact inference in Bayes nets is an NP-hard problem. At the same time there are polynomially tractable ...
6
votes
0answers
108 views

bias of an estimator when using stopping rules

Consider the setting where $X_1,X_2,...$ are i.i.d. real-valued random variables with $\mathbb{E}[X_i] = \theta$ and let the random variable $\tau$ be an associated stopping time. I'm wondering what ...
5
votes
0answers
223 views

How are optional stopping rules based on e.g. sample confidence (width of confidence interval) biased?

Inspired by this: http://pss.sagepub.com/content/22/11/1359 In the context of open-ended data collection where the necessary sample size cannot be properly estimated, for the purpose of a ...
9
votes
0answers
822 views

Understanding Sequential Probability Ratio Test (SPRT) Likelihood Ratio

I am a software developer looking to develop an alternative for the simple hypothesis testing scheme described here. In short, the test works as follows: Two URLs are compared for their ability to ...
17
votes
4answers
1k views

How could one develop a stopping rule in a power analysis of two independent proportions?

I am a software developer working on A/B testing systems. I don't have a solid stats background but have been picking up knowledge over the past few months. A typical test scenario involves comparing ...
2
votes
0answers
1k views

Determining Optimal Number of Cluster in Hierarchical Clustering in Consideration of Variance of Data

I'm applying a Hierarchical Agglomerative Clustering (HAC) for grouping my data and I need to determine the number of the cluster automatically. To determine the optimal number of cluster, I obtain ...
16
votes
3answers
626 views

Optional stopping rules not in textbooks

Stopping rules affect the relationship between P-values and the error rates associated with decisions. A recent paper by Simmons et al. 2011 coins the term researcher degrees of freedom to describe a ...
3
votes
1answer
125 views

Thoughts on model self-penalization amidst difficult parameter estimation

It is well accepted that one should account for model complexity when performing model comparisons, and the general procedure is to penalize more complex models more strongly. While this makes sense ...
0
votes
2answers
101 views

Difference between the Stopping Criteria [closed]

I would like to know the difference between below mentioned stopping criteria used in various gradient descent algorithm $\frac{Prev\_fun\_value - curr\_fun\_value}{Pre\_fun\_value} \le tol$ $Prev\...
4
votes
0answers
180 views

Stopping rule for chi-squared discretization algorithm

I developed an algorithm that uses the chi-squared test to perform supervised discretization of a continuous variable. I described it in the paper "ChiD-A Chi-Squared Discretization Algorithm" ...
2
votes
0answers
107 views

Optimal stopping under partially observable state

This problem is basically the classic asset selling problem but with imperfect state information. In the classical problem, we have an asset that we wish to sell, we receive offers w(0) to w(N-1). ...
4
votes
2answers
628 views

Optimal stopping from an unknown distribution

The Secretary problem has an algorithm for fixed N and immediate accept/reject (that is, reject reject ... accept one, stop). There are several variants; in mine, secretaries or samples come from a ...