Consider a person throwing a ball at a grid of 100 by 100 targets. If they hit a target, assume that it is completely destroyed, and that one throw can only destroy a maximum of 1 target. This person has a 10% chance of completely missing the target area on any throw.
Question:
On what throw (approximately) do you expect this person's probability of hitting a target to drop below 85%.
I am unsure if there is an efficient way to accomplish this, so I'll provide the starting point of my solution.
Solution:
First, determine how many targets must be destroyed to reduce probability to 85%, then determine the expected number of throws to destroy that many targets. This is the 10% chance to miss, plus the 90% chance that you hit the target area, but in a cell that is already destroyed:
$$ P(miss) = 0.15 = 0.1 + (1-0.1)\frac{n}{10000} $$ $$ n = 555.5555.... \approx 556 $$
Where n is the number of previously destroyed targets. Thus, after 556 targets have been destroyed the probability will be less than 85%. What I am unsure about is if there is an efficient way to determine how many throws.
Expectation value (from, eg, Wikipedia):
$$ E(x) = \sum_{i=1}^N x_i p_i $$
But the probability of any event, $p_i$ is dependent on the all of the previous events, which are in turn dependent on previous events (except $p_1$), and given the large number of throws needed (at least 556), this could be a huge relation...
My approximate solution is to take an average probability over those 556 destroyed targets:
$$ \frac{1}{556}\int_0^{556}P(miss,n)dn = \frac{1}{556}\int_0^{556}0.1+\frac{0.9n}{10000}dn $$ $$ \approx0.125 $$ Now, assuming this is a reasonable chance to miss over the first 556 targets, then it would take about 635 throws to destroy 556 targets. (I also ran a few Monte Carlo simulations and this seems reasonable)
Question: Is there a "better" solution to this problem? For example, a more rigorous statistical approach, or a way of solving an exact solution without resorting to a ridiculous recursion relation?
I don't quite follow your notation, but I get the same answer, so you're probably doing it correctly. (EDIT: I mean we get the same answer, so we're probably both right, not my answer must be right, so yours is too.) I did it using expected waiting time. We want the expected number of throws until target number $556$ is destroyed. This is equal to the expected number of throws to destroy the first target, plus the expected number of further throws needed to destroy the second target, plus the number of additional throws to destroy the third target, and so on.
Now if we have repeated independent trials with probability of success $p$, the expected number of trials until the first success is $1/p.$ The probability that the first success comes on trial $n$ is $(1-p)^{n-1}p$ and you can plug it into the formula for expectation, to get $$\sum_{n=1}^{\infty}{n(1-p)^{n-1}p} = \frac{1}{p}.$$
So that means we have $$\sum_{n=1}^{556}{\frac{10^4}{.9(10^4-n)}}=\frac{10^5}{9}\left(\sum_{n=1}^{9999}{\frac{1}{n}}-\sum_{n=1}^{9443}{\frac{1}{n}}\right) = \frac{10^5}{9}(H_{9999}-H_{9443}),$$ where $H_n$ is the $n$th harmonic number.
Using the approximation $H_n \approx \ln n +\gamma,$ we get that the number of throws required is about $$\frac{10^5}{9}\ln\frac{9999}{9443}\approx 635.68$$