2
$\begingroup$

In an online game the chance of succeeding at an action starts at 5% and goes up 5% every time the action fails.

Upon success the chance resets back to 5%.

(So you know how they say a die has no memory of prior rolls? Here it does.)

The question: How many attempts do I need to have a 50/50 chance of success?

Alternate question: What fixed percent chance would duplicate the overall success rate of this system? (Over many rolls.)

$\endgroup$
  • $\begingroup$ Umm...extrapolating from what you say, at the tenth attempt you will have a $50$% chance of success. $\endgroup$ – whuber Aug 28 '13 at 20:37
  • $\begingroup$ @whuber No, because you had a chance of succeeding on each attempt, not just the 10th one. I want the overall chance of success. $\endgroup$ – Ariel Aug 28 '13 at 20:44
  • 2
    $\begingroup$ My point, Ariel, is that you need to clarify what you mean by "chance of success." The "overall" chance of success is 100% because you are assured of success after the 20th roll. Your chance of a success within the first four rolls is $2093/5000$, which is less than 50%, and your chance of a success within the first five is $11279/20000$, which is greater than 50%, so at no stage is your cumulative success rate 50/50, either. $\endgroup$ – whuber Aug 28 '13 at 20:47
  • $\begingroup$ @whuber A "chance of success" means that after X number of attempts I will have succeeded 50% of the time. How did you calculate the odds you listed? Could you put that as an answer? (And I'm fine with a non-integer answer.) I'd like to calculate some other things too, so it would help me if you showed me how you calculated it. $\endgroup$ – Ariel Aug 28 '13 at 21:53
3
$\begingroup$

This probability tree represents the game and guides the calculations:

Tree

The blue node at the left represents the start. At this point there is a 5% chance of success (leading to the up and left). If success is achieved now, only one attempt is made, as indicated in the orange circle.

Lacking success, we progress down and to the right to the next blue node. This time the chance of success is 10% and the chance of failure 90%. And so on, up to the 20th blue node where the chance of success (after 20 tries) equals 100% (and so there is no possibility of failure).

By axiomatic laws of probability, the chance of arriving at any terminal orange node is the product of the chances along the edges leading to that node. For instance, the chance of success in exactly two attempts is 95% times 10%, equal to $19/200,$ and the chance of success in exactly three attempts equals 95% times 90% times 15%, equal to $513/4000.$

By carrying out all the multiplications we compute the chances of success after exactly $k$ attempts for $k=1, 2, \ldots, 20$:

$$\frac{1}{20},\frac{19}{200},\frac{513}{4000},\frac{2907}{20000},\frac{2907}{20000},\frac{26163}{200000},\ldots,\frac{14849255421}{640000000000000000}.$$

From these values all quantities of interest may be calculated. For instance, the chance of success after four attempts is $\frac{1}{20}+\frac{19}{200}+\frac{513}{4000}+\frac{2907}{20000} = \frac{2093}{5000} = 0.4186$ and the chance of success after five attempts is greater by $\frac{2907}{20000}$ again, giving $\frac{11279}{20000} = 0.56395.$ Therefore the median number of attempts lies between four and five.

The expected (mean) number of attempts is (by definition) obtained by multiplying the number of attempts by its chance and summing over all possible numbers. The value is $\frac{3387894135040576041}{640000000000000000}$, approximately equal to $5.29358$. Its reciprocal, approximately $18.8908$%, answers the last question: the fixed chance of success with the same expected number of attempts.

A similar probability tree can help answer any similar questions where the value of $5$% may differ and can even change from one attempt to the next: just write in the appropriate probabilities and do comparable calculations.

$\endgroup$
  • $\begingroup$ I notice that the probably after exactly $k$ attempts peaks between 4 and 5, and the median (i.e. cumulative attempts) is also between 4 and 5. Is this a coincidence? And thank you very much - this is extremely helpful. $\endgroup$ – Ariel Aug 29 '13 at 6:53
  • $\begingroup$ I had noticed that too and checked it to make sure there wasn't some kind of error in calculation. It occurs because in going from the fourth to the fifth attempt, a factor of 20% is removed (chance of success at fourth attempt) to be replaced by 25% (chance of success at fifth attempt) while a factor of 80% is thrown in (chance of failure at fourth attempt). The net change is to replace 20% by 80% of 25%, which is just 20% again. Thinking of a generalization of this problem where 5% is replaced by 100/n% (with n=20 here), that should be considered a coincidence. $\endgroup$ – whuber Aug 29 '13 at 14:14
1
$\begingroup$

Make a 19-state Markov chain and solve for its stationary distribution, then look at the probability of the first state. This will be the long-term expected number of successes per mouse click.

$\endgroup$
  • $\begingroup$ +1--but I believe you need 20 states for this MC (accounting for the conditions prior to the first, second, ..., 20th rolls). The expected number of mouse clicks per success is $\frac{3387894135040576041}{640000000000000000}\approx 5.29358.$ $\endgroup$ – whuber Aug 28 '13 at 20:51
  • $\begingroup$ @whuber This is different from what you answered in a comment to the question (where you had a number between 4 and 5, here it's between 5 and 6). Could you clarify? (And post as an answer.) $\endgroup$ – Ariel Aug 28 '13 at 21:48
  • 1
    $\begingroup$ @whuber I now understand why the two numbers were different - they answer different things. (I wrote a quick program to just try many rolls and see, and both of your numbers match exactly.) But can you explain how you calculated your numbers? $\endgroup$ – Ariel Aug 28 '13 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.