Probability for the Sums of Random Variables

probability

From a Probability perspective, I am curious to learn about the distribution of the sums of Random Variables.

For example, suppose I am playing a game in which I flip a fair coin. The probability of getting a heads is 0.5 and the probability of getting a tails is also 0.5.

Let's say that if I get a heads, my score = score + 1. And if I get a tails, my score = score -1

Suppose my current score is 7 – after 3 flips, what is the probability that my score will be greater than or equal to 7?

To answer this question, I can manually ennumerate all possible combinations given my current score and 3 flips:

  • Combination 1: $7 + 1 -1 + 1 = 8$
  • Combination 2: $7 + 1 -1 -1 = 6$
  • Combination 3: $7 + 1 +1 +1 = 10$
  • Combination 4: $7 + 1 +1 -1 = 8$
  • Combination 5: $7 -1 -1 -1 = 4$
  • Combination 6: $7 -1 -1 +1 = 6$
  • Combination 7: $7 + 1 -1 +1 = 8$
  • Combination 8: $7 -1 +1 +1 = 8$

Then, I can count how many of these combinations result in a score greater than 7.

Here, I can see that out of the 8 possible combinations ($2^3 = 8$), 3 of these combinations have a score less than 7 – therefore, the probability that my score will be greater than or equal to 7 after 3 flips is $\frac{5}{8}$

My Question: Now, I am interested in solving these kinds of problems from a more math based perspective. For example, suppose you current score is $m$ and you flip the coin $n$ times, what is the probability that my final score will be greater than $k$?

Currently, I would solve this kind of question via simulation – I would repeatedly simulate games based on the initial conditions and record the final score. Below is some Python code to represent this problem (when current score = 7 and there are 100 flips):

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm

def flip_coin():
    return np.random.choice([-1, 1])

def simulate_game(num_flips):
    score = 7
    scores = [score]
    for i in range(num_flips):
        score += flip_coin()
        scores.append(score)
    return scores

num_sims = 1000
num_flips = 100

df = pd.DataFrame(columns=['simulation number', 'total end score'])

for i in range(num_sims):
    scores = simulate_game(num_flips)
    df.loc[i] = [i+1, scores[-1]]

fig, axs = plt.subplots(1, 2, figsize=(12, 5))

# Plot the simulations
for i in range(num_sims):
    scores = simulate_game(num_flips)
    # Map score values to a color using a colormap
    color = cm.get_cmap('RdYlBu')((scores[-1] - df['total end score'].min()) / 
                                  (df['total end score'].max() - df['total end score'].min()))
    axs[0].plot(range(num_flips+1), scores, color=color)
axs[0].set_xlabel('Turn number')
axs[0].set_ylabel('Score value')
axs[0].set_title(f'{num_sims} simulations of the coin flip game')

# Plot the density plot
# Use the same colormap to color the plot
df['total end score'].plot(kind='density', ax=axs[1], cmap='RdYlBu')
axs[1].set_xlabel('Total end score')
axs[1].set_title('Density plot of total end scores')

plt.show()

enter image description here

Based on the accumulated information from these simulations, I could count the number of simulations in which the final score was greater than $k$ and divide this number by the total number of simulations. And the more simulations I performed, the closer this calculation will be to the real number.

But how can we solve this problem mathematically? Is there some general mathematical result on the sums of Random Variables?

Thanks!

Best Answer

I don't know your level in Mathematics so I will write it as clearly as possible. There might be some English errors, feel free to edit the post.

Suppose that your current score is $m$ and you still have to flip $n$ coins. What is the probability of getting a final score higher than $k$ ?

Mathematical definition of the score

It is crucial to determine what is the mathematical deifnition of the score here. After flipping a coin, either you get $-1$ or $1$ with probability $p=0.5$ (assume more generally that $p\in[0,1]$. Noticing that leads to model a point as a Bernoulli variable of parameter $p$. The score is then a sum of Bernoulli variables with parameter $p$. In the following, we assume that each flip is done independently of the others.

Simplifying the problem

By an independence argument, it is easy to see that your problem is equivalent to:

Assuming the current score to be 0, what is the probability that after flipping $n$ coins, the score will be higher than $k-m$

WLOG, let denote $h:=k-m$.

Case $h>n$. It is not difficult to see that the probability, starting from 0, to be higher than $n$ after flipping $n$ coins is 0.

Case $h<-n$. The same reasonning leads to same conclusions.

Case $-n\leq k \leq n$. This case is not trivial as the others. As we said before, the score is a sum a i.i.d. Bernoulli variables of parameter $p$. Let notice the usefull theorem below.

Theorem Let $X_1,...X_i$ be a sequence of i.i.d variables following a Bernoulli distribution of parameter $p\in [0,1]$. The random variable defined as $S_i=X_1+...+X_j$ follows a Binomial distribution of parameters $p$ and $i$.

At this stage it is almost done since (you are lucky) binomial distribution has been studied for long time ago. A closed formula exists and is given by:

Proposition Let $S_i$ be a Binomial variable of parameter $p$ and $i$. For any $j$ such that $-i\leq j \leq i$, we have: $$\mathbb{P}(S_i \geq j) = \sum_{\ell = j}^i \binom{i}{\ell}p^\ell (1-p)^{i-\ell}.$$

Thanks to this proposition, starting from $0$, the probability that we get a score higher than $k$ (with $-n\leq k \leq n$) is:

$$\sum_{\ell = k}^n\binom{n}{\ell}p^\ell(1-p)^{n-\ell}.$$

Solution to your problem

By shifting the score again, the probability of getting a score higher than $k$ after flipping $n$ coins and starting from a score of $m$ is:

$$ \begin{cases} \displaystyle 0 \text{ if } k-m>n \text{ or } k-m<-n,\\ \displaystyle \sum_{\ell = k-m}^n \binom{n}{\ell}p^\ell(1-p)^{n-\ell} \text{ if } -n\leq k-m\leq n. \end{cases} $$

Conclusion

The key takeway are:

  • Model properly the situation your are dealing with
  • Try to link it with known objects (distributions, ...)
  • Try to seek for the desired properties (this forum, books, research articles, etc...)
  • Try simplify when possible (here, you shift the score to have a simpler but equivalent problem).

Hope it helps!

[Edit]

Other scores

In this section, I briefly introduce situations where the score not $1$ or $-1$.

In the initial set up, you get either $+1$ or $-1$ at each flip. You can assume that at each step, you get a score that is "randomly chosen" on $\mathbb{R}$. By "randomly chosen", I mean that a each step, you get a score that follow a specific distribution (gaussian, exponential, etc...). We still assume the i.i.d. property.

1. Gaussian score

You can imagine that at each step, you will get a score that follow a normal distribution, denoted $\mathcal{N}(0,1)$. the score is no longer an integer but a real number.

Theorem If $S_n:=X_1,...X_n$ are $n$ i.i.d. gaussian variables, the variable $S_n$ follows the distribution $\mathcal{N}(0,n)$.

This theorem is interesting because in this case, the probability for the score to be higher than a certain level can be expressed with the error function $\text{erf}$.

To conclude the gaussian case, if the current score is at level $a\in\mathbb{R}$, the probability of getting a score higher than $b\in\mathbb{R}$ after flipping $n$ coins is:

$$\frac{1-\text{erf}\left(\frac{b-a}{\sqrt{n}}\right)}{2}.$$

This can be proved by a bit of algebras.

2. Exponential case

You can also assume that the score you get follows an exponential distribution. At each step, you get a positive number.

Theorem If $S_n:=X_1,...X_n$ are $n$ i.i.d. exponential distribution of parameter $\lambda>0$, the variable $S_n$ follows a gamma distribution $\Gamma(n,\lambda)$.

The case is also interesting since the cumulative distribution of this distribution is expansively studied in the literrature.

The probability you are looking for is then:

$$1-\frac{\gamma(n, \lambda(b-a))}{\Gamma(n)}$$

where $\gamma$ is the incomplete gamma function.

Simple non-i.i.d. situation

You can also imagine a situation where the flips are not independent. To this aim, you can model a sequence of $n$ flips as a sequence of $n$ gaussian variable. To describe the correlation, you need to know the correlation matrix, usualy denoted $\Sigma$.

The distribution followed by the by the sum of gaussian variables (here the score) follows a multivariate normal distribution. You can then apply some well known properties on this disbtribution to find the desied propbability.

I know that it is quite brief. Detailing all of these situations would require a lot of properties. It is more an overview of what you can do without knwowing hard probabilities.

Related Question