At a national hotel chain, at the end of every month, there is a probability $p$ that you are upgraded to the next tier. After $N$ months, how many months do you expect to have spent in each tier assuming at least the first month must be spent in the lowest tier, and that you can only move up one tier at a time?
It was not difficult to find the likelihood of being in any of the given tiers after N months, and achieved the answer by summing the columns of my markov chain (+1 for the first state). Is there a nice combinatorial method for solving this?
Any help appreciated.
We can make quick work of this problem using linearity of expectation.
Fix a number $t\in \{1,\dots,N\}$. We shall compute the expected number of months spent at tier $t$ (where the first month is at tier one). For each $m\in \{1,\dots,N\}$, let $X_{m,t}$ be a random variable which is equal to $1$ if the $m^\text{th}$ month was spent at tier $t$, and which equals $0$ otherwise. The number of months at tier $t$ is $$ X_{1,t}+\dots+X_{N,t} $$ so the expected number of months at tier $t$ is the sum of $\mathbb E[X_{m,t}]$ from $m=1$ to $m=N$.
Preceded by the $m^\text{th}$ month, there are $m-1$ indepedent chances to get an upgrade. In order to have $\{X_{m,t}=1\}$, we need exactly $t-1$ of those upgrades to occur. Therefore, $$ \mathbb E[X_{t,m}]=\mathbb P(X_{t,m}=1)=\binom{m-1}{t-1}p^{t-1}(1-p)^{m-t} $$ Finally, using $q=1-p$, we conclude $$ \text{expected # monts at tier $t$} =\sum_{m=t}^N\mathbb E[X_{t,m}] =p^{t-1}\sum_{m=t}^N\binom{m-1}{t-1}q^{m-t}. $$ I do not know if there is a closed form for this answer. It can be written as $$ [x^{N-1}]\frac{(px)^{t-1}}{(1-qx)^t(1-x)} $$ Here, $[x^k]f(x)$ means "the coefficient of $x^k$ when $f(x)$ is expanded into a power series centered at $x=0$". For each fixed $t\in \mathbb N$, you can use the above to get a closed formula in terms of $N$. For example, when $t=1$, you get $$ [x^{N-1}]\frac{1}{(1-qx)(1-x)} =[x^{N-1}]\left(\frac{1}{(1-q)(1-x)}-\frac{q}{(1-q)(1-qx)}\right)=\frac1{1-q}-\frac{q^N}{1-q}=\frac{1-q^N}{1-q} $$ In general, you can use this same methodology to get a closed form for any fixed $t$, in terms of $N$. You just need to expand out $\frac{(px)^{t-1}}{(1-qx)^t(1-x)}$ using partial fractions, then extract the coefficient of each fraction.