Questions tagged [optimal-stopping]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
15 views
3
votes
1answer
49 views

Problem of accepting a prize versus trying to get a better one

I don't know how to better formulate the general problem I am thinking about, let me try formulate an example. Assume you are playing a game with N rounds, and at each round the following happens: ...
1
vote
0answers
17 views

Stopping rule in a Monte Carlo simulation for a convergent sequence of unknown random variables

Given an unknown random variable $X: \Omega \mapsto [a,b] \subset \mathbb{R}$, let us imagine we want to estimate $\mathbb{E}(X)$. We can sample sequentially as many times as desired, let us say $m$ ...
2
votes
1answer
96 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
57 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
395 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
71 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
21 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
40 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
109 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 ...
3
votes
2answers
145 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
132 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
797 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
310 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
226 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
843 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 ...
18
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
629 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
108 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
643 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 ...