# Probability of Getting a Given Sum in a Coin Flip Game

• Suppose I am playing a game where I flip a $$k$$ sided coin (i.e. sides are denoted by $$k_1$$, $$k_2$$ ...$$k_k$$) .
• There is a probability of $$p_1$$, $$p_2$$, ...$$p_k$$ of the coin landing on any one of these sides
• A score of $$c_1$$, $$c_2$$, ...$$c_k$$ associated with coin landing on each side ($$c_i$$ can be positive or negative integers)
• At each turn, my score becomes: current_score + $$c_i$$
• I play this game for $$n$$ turns
• The result of each turn is independent from the previous turn

My Question: If my current score is 0 , after 5 more turns - I want to know how many outcomes can happen (e.g. $$x$$ number of games games where my score is 5*$$c_1$$, $$y$$ number of games where my score is 4*$$c_1$$ + $$c_2$$, etc.), and the probability of obtaining each one of these combinations (e.g. there is a probability of $$q_1$$ where I end up with a score of 5*$$c_1$$, etc.)

My attempt to solve this problem: I think that this question can be answered with the Multinomial Distribution. Here, $$x_i$$ is the number of times that the coin landed on face $$k_i$$ and $$p_i$$ is the probability of the coin landing once on face $$k_i$$. Thus, the probability of getting any $$n$$-length sequence in any order is given by: (this is the equivalent of saying that, what is the probability in $$n$$ flips that the coin lands $$x_1$$ times on face $$k_1$$, $$x_2$$ times on face $$k_2$$ ... and $$x_k$$ times on face $$k_k$$)

\begin{align} f(x_1,\ldots,x_k;n,p_1,\ldots,p_k) & {} = \Pr(X_1 = x_1 \text{ and } \dots \text{ and } X_k = x_k) \\ & {} = \begin{cases} { \displaystyle {n! \over x_1!\cdots x_k!}p_1^{x_1}\times\cdots\times p_k^{x_k}}, \quad & \text{when } \sum_{i=1}^k x_i=n \\ \\ 0 & \text{otherwise,} \end{cases} \end{align}

For example, here is the probability of the coin landing 5 consecutive times on $$k_1$$ (in any order) :

$$P(X = k_1, k_1, k_1, k_1, k_1) = \frac{5!}{1!1!1!1!1!} p_1^{1} p_1^{1} p_1^{1} p_1^{1} p_1^{1}$$

And here is the probability of the coin landing 3 times on $$k_1$$ and 2 times on $$k_2$$ in $$n = 5$$ turns (in any order):

$$P(X = k_1,k_1,k_2, k_2, k_2) = \frac{5!}{2!3!} p_1^{2} p_2^{3}$$

In general, after 5 turns, there can be $$5Ck$$ score combinations: $$5Ck = \frac{5!}{k!(5-k)!}$$

From here, I would have to identify which combinations I am interested in. For example, suppose I am interested in a score of $$b$$ after 5 turns. I would identify which of the $$5Ck$$ combinations sum to $$b$$ (e.g. perhaps $$c1 + c3 + c9 - c2 + c5 = b$$ , perhaps $$c10 + c3 + c9 - c2 + c5 = b$$, etc). I think these combinations can be counted like this (see references):

$$\text{No. of ways}= {b - 1 \choose 5-1} = \frac{[b-1]!}{[5-1]![b - 1 - (5 - 1)]!}$$

I would then need to find a formula to identify each combination that result in a sum of $$b$$ after $$n$$ = 5 turns and weigh each combination by its corresponding probability .... and then sum each weighted combination.

• Is there such a compact formula I can use to solve my original question?
• In general, is my analysis correct?

Thanks!

References:

• It's more complicated than that, since different combinations may lead to the same tally, depending on the $c_i$ values. For instance, say that $k=3$ and $c = 1, 2, 3$, you may obtain a score of 5 with $1, 1, 3$ but also with $1, 2, 2$. I don't think there is a shorter way than enumerating all the possibilities and then aggregate the outcomes with the same tally. Nov 17, 2023 at 5:59
• @nicola: thank you for your reply! I will keep looking into this. lately I have become very interested in these types of problems. I can't stop thinking about them! Nov 17, 2023 at 7:50
• Here are some other problems I thought about: math.stackexchange.com/questions/4804927/… , math.stackexchange.com/questions/4804059/… Nov 17, 2023 at 7:51
• The pattern of values C_i is very important in your problem. if $C_0=1, C_1=2, C_k= 2^k$, the problem is simple, you have no duplicates, for any tally, there is only 1 way to pbtain this value. If $C_k=k$ (like a standard 6-faces die), it is much more complex, because you have many ways to obtain medium values. Nov 17, 2023 at 15:45

$$(1+x+x^2+x^3.... +x^k)^n$$
Is there a formula to calculate the coefficient of $$x^a$$ (where $$a$$ can be any integer value less than k^n) that's more efficient than grinding through every possible permutation that sums to $$a$$ with the multinomial theorem and then summing them all?