Expanding a Probability Tree

Question

Consider the following situation:

Take some integer $N$

Each day there is a:

• $p_1$ probability that $N$ will increase by $n_1$ % of its current value
• $p_2$ probability that $N$ will decrease by $n_2$ % of its current value
• $p_3 = 1- p_1+ p_2$ probability that $N$ keep its current value

My Question: On any given day, I am trying to find out what possible values $N$ can assume - and what are the probabilities of assuming these values.

To solve this question, I first wrote the possible values that $N$ can take on the first day:

$$N_{1} = N \times [ p_3 + p_1(1+n_1) + p_2(1-n_2)]^{1}$$

On the second day, we can write:

$$N_{2} = N \times [ p_3 + p_1(1+n_1) + p_2(1-n_2)]^{2}$$

$$ N_{2} = N \times [p_3^2 + 2p_3p_1(1+n_1) + 2p_3p_2(1-n_2) + p_1^2(1+n_1)^2 + 2p_1(1+n_1)p_2(1-n_2) + p_2^2(1-n_2)^2]$$

By analyzing the above expression, I can indirectly see that on the second day, $N$ can have 9 possible values:

• $N$ can happen one possible way with probability $p_3^2$
• $N*(1+n_1)$ can happen two possible ways with a total probability $2*p_3p_1$
• $N*(1-n_2)$ can happen two possible ways with a total probability $2*p_3p_2$
• $N*(1+n_1)^2$ can happen one possible way with probability $p_1^2$
• $N*(1+n_1)(1-n_2)$ can happen two possible ways with a total probability $2*p_1p_2$
• $N*(1-n_2)^2$ can happen one possible way with probability $p_2^2$

Based on this, I can observe that : $$(p_1 + p_2 + p_3)^2 = p_3^2 + 2p_3p_1 + 2p_3p_2 + p_1^2 + 2p_1p_2 + p_2^2 = 1$$

Thus, it would appear that I could find out all possible values that $N$ can assume on any given day along with the corresponding probabilities using the relationship:

$$N_{k} = N \times [ p_3 + p_1(1+n_1) + p_2(1-n_2)]^{k}$$

• Is my understanding correct?

• Can this above logic be used to expand any Probability Function corresponding to any Discrete Random Variable - and thus find out the possible values and corresponding probabilities that a Discrete Random Variable can take in the future?

• And is there a more compact way (in mathematical notation) to represent this expansion in the general case?

Thanks!

Note:

• The following relationship (Multinomial Theorem : https://en.wikipedia.org/wiki/Multinomial_theorem) can be useful here:

$$(x_1 + x_2 + ... + x_m)^n = \sum_{k_1=0}^n \sum_{k_2=0}^n ... \sum_{k_m=0}^n \binom{n}{k_1, k_2, ..., k_m} x_1^{k_1} x_2^{k_2} ... x_m^{k_m} = \sum_{k_1=0}^n \sum_{k_2=0}^n ... \sum_{k_m=0}^n \frac{n!}{k_1! k_2! ... k_m!} x_1^{k_1} x_2^{k_2} ... x_m^{k_m} $$

Answer 1

Let $d$ equal the number of days. The possible values of $N$ are

$N_{d} = N(1+n_{1})^{i}(1-n_{2})^{j}$ with $i\geq0$, $j\geq0$ and $i+j\leq d$

and this has probability $p=(n!/(i!j!(d-j-i)!))*p_{1} ^{i} p_{2} ^{j} p_{3} ^{d-i-j}$

and there are $(d+1)(d+2)/2$ possible values of $N_{d}$ at date $d$

Some More Explanation:

Fix $d$, the number of days. For each day there are three possible outcomes, $N$ goes up ($U$), $N$ goes down ($D$), or $N$ stays the same $(S)$. So if $d=6$ an example of a potential outcome would be $\{U,D,S,D,U,U\}$.

If we let $i$ be the number of ups, $j$ be number number downs that have occurred and and $k=d-j-i$ be the number of time $N$ stays the same. The probability of this sequence (in order) is given by $p=p_{1}^{i}p_{2}^{j}p_{3}^{k}$ , and the random variable $N_{d}$ would be given by \begin{align} N_{d}=N(1+n_{1})^{i}(1-n_{2})^{j} \end{align}

This gives the probability of a particular order sequence, an the associated $N_{d}$. However, the outcome $N_{d}$ only depends on the number of ups, downs and sames which occur, not the order in which they occur.

To keep things simple, let's assume that $(1+n_{1})^{i}\neq(1-n_{2})^{-j}$ for all $i,j\in\{1,2,3,.....,d\}$. This means that there is a unique $N_{d}$ for a given set of $i,j,k$.

Ignoring $k$ as the residual, any $i,j\in\left\{ 0,1,2,...,d\right\} $ such that $i+j\leq d$ is a possible outcome with a unique $N_{d}$ given by \begin{align} N_{d}=N(1+n_{1})^{i}(1-n_{2})^{j} \end{align}

Further, the probability of this $N_{d}$ is given by $p_{1}^{i}p_{2}^{j}p_{3}^{k}$ times the number of permutations for which this combination of $i$ and $j$ can occur. For example, if $d=2$ and $i=j=1$, then there are two possible permutations $\{U,D\}$ and $\{D,U\}$; so the probability would be $p=2p_{1}p_{2}$.

In this setting the number of possible permutations is given by \begin{align} \left(\begin{array}{c} d\\ i,j,d-i-j \end{array}\right)=\frac{d!}{i!j!\left(d-i-j\right)!} \end{align}

Note, this can be seen as first choosing which elements are ups ($i$), then choosing which elements are downs ($j$), \begin{align} \left(\begin{array}{c} d\\ i,j,d-i-j \end{array}\right)=\left(\begin{array}{c} d\\ i \end{array}\right)\left(\begin{array}{c} d-i\\ j \end{array}\right) \end{align}

(See https://en.wikipedia.org/wiki/Combination for more on combination selection).

So the probability of \begin{align} N_{d}=(1+n_{1})^{i}(1-n_{2})^{j} \end{align}

is given by \begin{align} p=\left(\begin{array}{c} d\\ i,j,d-i-j \end{array}\right)p_{1}^{i}p_{2}^{j}p_{3}^{d-i-j} \end{align} for any $i,j\in\left\{ 0,1,2,...,d\right\} $ with $i+j\leq d$ (and zero otherwise).

Finally, let's turn to the number of possible values of $N_{d}$, which is given by $\left(d+1\right)\left(d+2\right)/2$. This can be found on the Wikipedia article on the multinomial theorem you linked to, or this one on trinomial expansion which applies here https://en.wikipedia.org/wiki/Trinomial\_expansion.

A more visual way to see why this would be; consider a rectangle with $d+1$ rows representing $d$ to $0$ running from top to bottom, and with $d+2$ columns, representing $0$ to $d+1$ running from left to right. This rectangle represents $\left(d+1\right)\left(d+2\right)$ pairs of $i$ and $j$, with only pairs with $i+j\leq d$ feasible.

\begin{align} \begin{array}{ccccccc} d & * & - & - & - & - & -\\ d-1 & * & * & - & - & - & -\\ \vdots & * & * & * & - & - & -\\ 1 & * & * & * & * & - & -\\ 0 & * & * & * & * & * & -\\ & 0 & 1 & \cdots & d-1 & d & d+1 \end{array} \end{align}

As such only the lower left half of the triangle represents feasible pairs (here $*$ represents feasible pairs). So the number of feasible pairs is $\left(d+1\right)\left(d+2\right)/2$.