Mfrhtyj

I want to determine the generating function of the numbers of visits up to a specific time. Formally: let ${X_{n}}_{n geq 0}$ be a markov chain on the state space $S = {1,ldots,r}$ with transition matrix $P = (p_{i,j})_{1 leq i,j leq r}$ and initial probability vector $alpha = (alpha_{i} : i in S)$ with $alpha_{i} = mathbb{P}(X_{0} = i)$. Let $q(n_{1},ldots,n_{r})$ be the probability that up to time $n-1$ the state $1$ is visited $n_{1}$-times,$ldots$,state $r$ is visited $n_{r}$-times and $F_{n}(x_{1},ldots,x_{r}) = sum_{n_{1}+ cdots +n_{r} = n}q(n_{1},ldots,n_{r})x_{1}^{n_{1}}cdots x_{r}^{n_{r}}$ be the corresponding generating function of $q(n_{1},ldots,n_{r})$. Now I want to show that
$$
F_{n}(x_{1},ldots,x_{r}) = (alpha_{1}x_{1},ldots,alpha_{r}x_{r}) left( P D_{r}right)^{n-1} e,
$$
where $e = (1,ldots,1)^{intercal}$ and $D$ is given by
$$
D =
begin{bmatrix}
x_{1} && \
& ddots &\
& & x_{r}
end{bmatrix}.
$$
Here is my solution:
$$
begin{align*}
sum_{n_{1} + cdots + n_{r} = n}q(n_{1},ldots,n_{r}) &= sum_{j in I}mathbb{P}(X_{n-1} = j) \
&= sum_{j in I}sum_{i in I}alpha_{i}p_{i,j}^{n-1} \
&= left(sum_{i in I}alpha_{i}p_{i,1}^{n-1},ldots,sum_{i in I}alpha_{i}p_{i,r}^{n-1} right) e \
&= alpha P^{(n-1)} e.
end{align*}
$$
Does this suffice as a proof and is it correct? Thanks for any help!

Your computation is correct but it only proves the special case $x_1 = ldots = x_r = 1$.
To prove the general case, set $$A(n_1, ldots, n_r) = left{sigma colon {0, ldots, n-1} to I ; middle| ; #sigma^{-1}(i) = n_iright}.$$
Then $$begin{align*} q(n_1,ldots, n_r) &= mathbb{P}big(exists sigma in A(n_1, ldots, n_r), , X_k = sigma(k) text{ for } 0 leq k leq n-1 big) \ &= sum_{sigma in A(n_1, ldots, n_r)} mathbb{P}big( X_k = sigma(k) text{ for } 0 leq k leq n-1big) \ &= sum_{sigma in A(n_1, ldots, n_r)} alpha_{sigma(0)}p(sigma(0),sigma(1))cdots p(sigma(n-2), sigma(n-1)). end{align*}$$
Now we get
$$begin{align*} F_n(x_1, ldots, x_n) &= sum_{n_1 + ldots + n_r = n}q(n_1,ldots, n_r) x_1^{n_1} cdots x_r^{n_r} \ &= sum_{n_1 + ldots + n_r = n} bigg(sum_{sigma in A(n_1, ldots, n_r)} alpha_{sigma(0)}p(sigma(0),sigma(1))cdots p(sigma(n-2), sigma(n-1)) bigg)x_1^{n_1} cdots x_r^{n_r} \ &= sum_{n_1 + ldots + n_r = n \ sigma in A(n_1, ldots, n_r)} alpha_{sigma(0)}p(sigma(0),sigma(1))cdots p(sigma(n-2), sigma(n-1)) x_1^{#sigma^{-1}(1)} cdots x_r^{#sigma^{-1}(r)} \ &= sum_{sigma in A} alpha_{sigma(0)}p(sigma(0),sigma(1))cdots p(sigma(n-2), sigma(n-1)) x_1^{#sigma^{-1}(1)} cdots x_r^{#sigma^{-1}(r)} end{align*}$$
where $A = bigcup_{n_1 + cdots + n_r = n} A(n_1, ldots, n_r)$. The last equality is due to the fact that the $A(n_1, ldots, n_r)$ are pairwise disjoint. Notice that $A$ is actually the set of all functions from ${0, ldots, n-1}$ to $I$. This is because if $sigma$ is such a function, then setting $n_i = # sigma^{-1}(i)$ we have $sum_i n_i = # sigma^{-1}(I) = # {0, ldots, n-1 } = n$ and clearly $sigma in A(n_1, ldots, n_r)$. On the other hand, we have $x_1^{#sigma^{-1}(1)} cdots x_r^{#sigma^{-1}(r)} = x_{sigma(0)}x_{sigma(1)} cdots x_{sigma(n-1)}$ (by counting the number of times that each of the $x_i$ appears in both terms). Therefore
$$ begin{align*}F_n(x_1, ldots, x_n) = sum_{sigma colon {0, ldots, n-1} to I} alpha_{sigma(0)}p(sigma(0),sigma(1))cdots p(sigma(n-2), sigma(n-1)) x_{sigma(0)}x_{sigma(1)} cdots x_{sigma(n-1)}.end{align*}$$
This can be rewritten as $$F_n(x_1, ldots, x_n) = sum_{i_0, ldots, i_{n-1} in I} alpha_{i_0}x_{i_0}p(i_0,i_1)x_{i_1}cdots p(i_{n-2}, i_{n-1})x_{i_{n-1}}.$$
Finally, if you develop the RHS you get the same expression which proves the desired equality.