You must on average be improving to not guarantee failure.

post by eeegnu · 2022-03-26T05:28:12.690Z · LW · GW · 1 comments

Contents

1 comment

I was thinking about what happens when you run independent Bernoulli trials forever, with probability $p_i$ of success, but you lose the first time you fail. If all $p_i$ are the same, then with probability 1 we will eventually fail^[1]. Similarly, if the supremum of the sequence of probabilities $p$ is not 1, then we're also guaranteed to fail, since $P\left(p\text{never fails}\right)=\prod p_i\le \prod \underset{i}{sup}p=0$. The condition that ${lim}_{i\to \infty }{p}_i=1$ is necessary but not sufficient to guarantee that failure isn't certain^[2]. That seems to say that not only do we need to improve, but we also can't improve too slowly, or else we're sure to fail. So just how quickly do we need to improve? Well we have that $\sum (1-p_i)<\infty ⟹\prod p_i>0$^[3], which is much easier to work with (though this isn't a bijection so it can only be used to show that a sequence $p$ improves quickly enough.) Let $q_i=1-p_i$, which can be interpreted as our probability of failure. We know right away that any kind of geometric progression of failure minimization, e.g. $q=\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots$ will give us a better than 0 chance. That says that for any positive constant $c>1$, it's sufficient for $q_i>q_{i+1}c$ to not guarantee failure! But surely we can do better than this, i.e. there's no need to have to improve at a constant rate. We know that $\sum \frac{1}{n^2}=\frac{{\pi }^2}{6}$ converges, so here we need only for $q_i>q_{i+1}(1+\frac{2}{i}+\frac{1}{i^2})$ or simply $q_i>q_{i+1}(1+o(\frac{1}{i}\left)\right)$, so the further out we go, the less we need to improve relative to our previous rate of failure. This analysis was rather quick, and I'm curious if we can do better than this.

I thought about this problem after thinking about processes where even a single failure would be catastrophic. While in the real world a sufficient number of 0's for the probability of an event makes it negligible, things are different if you live forever and you're dealing with something that can never be minimized to a 0% chance of failure. You need to at least on average improve your odds between samplings, or failure is eventually certain.

1. ^{^}

   Technically this isn't guaranteed, there's nothing stopping a fair coin from landing on heads forever other than our finite lifespans preventing us from observing it. But I think it's fair to call a 0% chance of success a failure.

2. ^{^}

   For example, 0.9 (10 times), 0.99 (100 times), 0.999 (1000 times), ..., and if we take the product of these regions we get increasingly good approximations of $1/e\approx 0.37$, whose products will tend to 0.

3. ^{^}

   https://math.stackexchange.com/questions/209108/infinite-product-problem-sum-p-n-infty-implies-prod-1-p-n0

   Note that we don't care about when $p_i=0$ since this means we're guaranteed to fail anyhow.

1 comments

Comments sorted by top scores.