0
$\begingroup$

Sorry if this question is a bit lower-level, yet complicated, but I feel like there is something wrong and I cannot put my finger on it. This scenario is adapted from something I read elsewhere on the internet, but simplified to get the basic point across.

Lets say I have a system where I have different tiered shapes. Triangles can be bought from the store for 1 dollar. To make a square, you must combine two triangles. However, this combining has a 20% chance to be successful, in which case the 2 triangles combine to become 1 square. It has a 80% chance to fail, in which case the 2 triangles combine to form 1 failed triangle. What's the average cost for a square? You would buy 2 triangles at a time until you succeed. Then you can sell the excess failed triangles from failed attempts for 1 dollar each. However, you cannot combine the triangles from failed attempts to save money (lets just say they are failed and only can be combined once to make the situation simpler, but again, can be sold to the store for 1 dollar).

Person 1 says the following: Well since it is a 20% success rate, then on average I should have 5 combinations needed to get 1 square. 5 combinations costs 10 triangles, and I would be left with 1 square and 4 failed triangles. I bought 10 triangles for 10 dollars, but then I sold the 4 failed ones for 4 dollars, so the net cost is 6 dollars per square.

Person 2 says the following: Since this is a cumulative probability of independent events we can predict the probability of getting a square after $n$ combinations using $1-(1-x)^n$ where $x$ is the probability of success per event and $n$ is number of attempts. This handy formula is derived from multiplying the probability of failure after each event. We want the average number of times to combine, so we want to find the $n$ that corresponds to 0.5 probability (meaning that after $n$ combinations, there will be a 50% chance of getting at least 1 success. Since the success rate is 20%, we do $0.5=1-(1-0.2)^n$ and solve for $n$. We find $n\approx3.106$. This means we need on average about 3.106 combinations, or 6.212 triangles to be bought. Also, I can sell the failed triangles. Since all but one of the combinations fail, then if there are 3.106 combinations needed on average, then we would have 2.106 failed combinations, which can be sold for 2.106 dollars. We do 6.212-2.106 to get the net cost of 4.106 dollars per square.

Who is more correct? For the record I am pretty certain that person 1's interpretation of average needed combinations is naive and incorrect, but I am not sure if person 2's calculation for the number of failed triangles is correct. Even more confusing, other people have verified person 1's concept using computer programs running over millions of trials, finding that the result is always 6 dollars. Thus, person 1's interpretation is generally accepted in this community. This, again, seems impossible considering that the average needed combination calculation seems to be naive and incorrect.

And for fun, here's the full scenario (still adapted): When combining a shape, there is a 50% chance to return a failed shape of the same tier, 20% to upgrade 1 tier, and 30% chance return a failed shape of 1 tier lower. If you combine 2 triangles, since triangles are the lowest tier, it has an 80% chance to give a failed triangle and 20% chance to give a square. If I were to combine two squares, there's a 50% chance to return a failed square, a 20% chance to return a pentagon, and a 30% chance to return a failed triangle. The same goes for combining pentagons to potentially get a hexagon. Find the average cost per square, assuming that triangles are worth 1 dollar. Then use that average cost to calculate the average cost per pentagon (failed squares can be sold for the average cost per square) and average cost per hexagon (failed pentagons can be sold for the average cost per pentagon, just like squares).

Thank you so much. I hope we can get to the bottom of this.

$\endgroup$
1
$\begingroup$

Let $T$ be the random number of pairs of triangles one must buy and combine in order to obtain the first square. What is the probability that $T = 1$, that is to say, one is successful with the first pair of triangles purchased? This is simply $p = 0.2$ as you specified. How much did it cost? Well, it cost $2T = 2$ dollars.

What is the probability that $T = 2$? This means the first combination failed and the second succeeded. This happens with probability $(1-p)p = (0.8)(0.2) = 0.16$, because the outcome of each trial is independent of the outcome of the previous trial. You spent $2T = 4$ dollars for the four triangles, and resold the $T - 1 = 1$ failed triangle created in the first trial, for a net cost of $2T - (T - 1) = T + 1 = 3$ dollars.

In general, the probability that it takes exactly $T = t$ pairs of triangles to obtain the first square is $$\Pr[T = t] = (1-p)^{t-1} p, \quad t = 1, 2, 3, \ldots,$$ because in order for the first success to occur on the $t^{\rm th}$ trial, all the previous $t-1$ trials must be failures, each with probability $1-p$, and then the $t^{\rm th}$ trial succeeds with probability $p$. The net cost of this outcome is $$C = 2T - (T-1) = T+1$$ dollars: it costs $2T$ dollars to buy all the pairs of triangles, then since only the last pair is successful, there are $T-1$ failed triangles to sell back.

On average, how many trials are needed to obtain the first square? This is the expected value of $T$, which is given by $$\operatorname{E}[T] = \sum_{t=1}^\infty t \Pr[T = t] = 1p + 2(1-p)p + 3(1-p)^2 p + 4(1-p)^3 p + \cdots.$$ It is not too difficult to prove that this has value $1/p$. So in the case that $p = 0.2$, it takes on average $5$ trials to obtain the first square. The average cost is therefore $$\operatorname{E}[C] = \operatorname{E}[T] + 1 = 6$$ dollars.

If you run a simulation by repeatedly buying triangles and counting how many pairs it takes to get the first square, each time keeping track of this number, you might obtain something like $$\{4, 1, 1, 10, 3, 4, 1, 3, 4, 2, 3, 5, 12, 5, 3, 3, 12, 2, 2, 5, \ldots\}$$ and then if you took the average of these results, you'd find it would be very close to $5$--and the cost would be close to $6$. But you'd need to do this many, many times.

What does the other method describe? Well, it answers the question, "what is the fewest number of pairs would I need to buy in order to have at least a 50% chance of getting a square?" This of course is not the same thing as the average number of pairs one needs to buy to obtain the first square. Instead, it is asking for the smallest $m$ such that $$\Pr[T \le m] \ge 0.5.$$ To solve this, we have to compute $$\Pr[T \le m] = \sum_{t=1}^m (1-p)^{t-1} p = 1 - (1-p)^m,$$ which aligns with your formula and makes intuitive sense, since the probability that it takes strictly more than $m$ pairs is equal to the probability that the first $m$ pairs are failures; i.e., $$\Pr[T > m] = (1-p)^m,$$ hence the probability the first success occurs in $m$ or fewer combinations is $1$ minus this. Then we want to solve $$1 - (1-0.2)^m \ge 0.5,$$ or $$m \ge \frac{\log 2}{\log \frac{5}{4}} \approx 3.10628.$$ Since it is nonsensical to require a noninteger number of combinations, the smallest $m$ that guarantees a probability of at least $0.5$ of a success is $m = 4$, and the probability of success within $4$ trials is $\Pr[T \le 4] = 1 - (1-0.2)^4 \approx 0.5904$. But the number $m = 3.10628$ is not some kind of "average" number of trials, at least not in the same sense as "average" was used in the first calculation. Such a value is an artifact of treating an equation that only has meaning for positive integer values of the variable $m$ as if it is valid for all real numbers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the great explanation. I now realized the two people were talking about separate things. I have one more question. Which would you say is more useful for someone who would want to go out and create a square? Knowing the average cost per square or knowing the median "50% success" number for the square? It's good to know the average cost but over half of all people trying to get a square will not need more than 4 combinations (8 triangles, 8 dollars), and only some unlucky people will need many many combinations, skewing the average with outliers. $\endgroup$ – KITTENDESTROYER-9000 Jul 9 at 16:10
  • 1
    $\begingroup$ The average combinations (your "Person 1" calculation) in a sense represents the average number of tries per player that a large group of players would need until each player gets a square. The median combinations (your "Person 2" calculation) represents the number of individual tries for a large group of players trying for a square by which point at least half of the players should have a square. Which one is "more useful" depends on whether a player intends to keep trying until they get a square, or whether one wants to know how many tries one needs to have at least 50% chance of success. $\endgroup$ – heropup Jul 9 at 17:07

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.