Reading Difficulty: 2-3/5
Prerequisites: Some knowledge of some parts of combinatorics and probability will be helpful.

Here's a short and sweet one for now, but stay tuned for a longer piece soonish. No knowledge of Genshin Impact is required.

In Genshin, there is a very simplistic "crafting" system. Different characters give different bonuses when crafting. Two such characters are Sucrose and Dori.



Here is the setup, in alternative terms: Suppose you start with "tokens". Sucrose and Dori are two different people that can exchange your tokens for money.

• When you give Sucrose tokens, she will give you a dollar. Then, there is a chance that she gives you a second dollar.
• When you give Dori tokens, she will give you a dollar. Then, there is a chance that she gives you back token.

Naturally, your goal is to make as much money as possible. Who should you exchange your tokens with? (For simplicity, let's assume you pick exactly one person to exchange tokens with, i.e. you don't exchange with both of them in some order, which a priori could be wise for small values of .)

I invite you to think about this! It's not a crazy hard problem (at least, compared to some of the other stuff I talk about on this blog...), and it can be a good exercise for C&P in math competitions. Read on for the solution.

---

So it turns out that... (Answer)

Let's do the math now.

Analysis of Sucrose

This is the easy part. If you choose tokens, then you don't get any tokens back, so you'll make exactly exchanges. In expectation, a tenth of these exchanges will grant an extra dollar, so the expected number of dollars you can get from Sucrose is .

As , this is asymptotically equivalent to the fraction .

Analysis of Dori: Heuristics

Here, we'll make a reasonable guess as to what the answer should be approximately by playing fast and loose with our logic.

If we start with tokens, then at the start we can make around exchanges to get dollars. Then, we get about a quarter of this number in tokens back, i.e. we get around tokens returned. Now, we can make around exchanges to get dollars, and we'll get tokens back. The pattern is clear: If we keep doing this "forever", then the expected value seems to be like a geometric series:
The ratio between terms is , so this sums to . This is our guess for the asymptotic ratio as . And, note how close this is to Sucrose's ratio! is veerryyyyy close to --- if we cross multiply by , the difference is vs. .

The reason why this is a "guess" is because we assumed a lot of uniformity. For example, we assumed that we'd get exactly tokens back, which is a reasonable guess but not representative of reality because it's only the expected value, so carrying the value of forward is not necessarily going to work.

Analysis of Dori: Exact Value

Let's try to glean a formula for the exact expected value of dollars you get from Dori as a function of . Let this expected value be .

Since your number of tokens can change, it is natural to try and set up a recurrence. Let's start with tokens, and spend of those tokens. There are two possibilities:

• With chance, Dori only gives you a dollar, so your expected value in this case is .
• With chance, Dori gives you a dollar and increments your number of tokens by , so your expected value in this case is .

It follows that:
This is the recurrence we need!

It's always good to compute some of the first few terms of to make sure that we're on the right track. We can manually find that and , and indeed this is consistent with our recurrence.

We now need to turn the recurrence into a nice formula. Unfortunately it's not going to be nice. First, for we can stack two copies of the recurrence on top of each other:
Then we subtract them to obtain:
(Sanity check: The sum of coefficients on each side is equal, so I didn't mess up.) What this process does is eliminate the .

Now, the characteristic polynomial for this recurrence is given by
Without any calculation we know that must be a root (why?) and that this must factor as
We see that is a root of the cubic (why is this not surprising?), and so this factors further as
By the quadratic formula, we see that the roots of the characteristic polynomial are (a double root) and .

By the theorem that relates recurrences to the roots of their characteristic polynomial, it follows that the closed form for is
for constants . (The term is there because of the double root.)

Fortunately, we have quite a few obvious starting values of that we can use! Plugging in gives the following system:
Of course, no sane person would or should be solving this by hand, so I plugged this into Wolfram Alpha and got the following solution:
Thus our closed form, and the expected value of dollars we get from tokens, is:
(I combined both complex parts since they happened to be conjugates... to the surprise of not many people.)

What is the consequence of this formula? Well, note that , so that whole real-part/complex term will tend to rapidly as . In other words, the oscillatory part of the formula is not significant at all in the long run. And, the term is just a constant, so although this constant will prevail as , it's not asymptotically significant when compared to the linear growth of the term . So in the long run, the expected value will asymptotically look like --- just as we had claimed in the heuristics!