Consider the following "game" of chance. Each time the player pushes a button he is awarded a random (finite, integer, non-negative) number of points. The probability of receiving any particular score is known and fixed for every trial (button push). Each trial is also independent. The player starts with an initial score of 0.
What I am trying to calculate is the probability distribution for the player's cumulative score after a number of trials. I represent the problem as a Markov chain where each state corresponds to a cumulative score (i.e. State s is the state where the player's cumulative score is s). As the player's score never decreases, the transition matrix is lower triangular. In general the matrix would not be finite, however we can define a maximum score of interest, M, and a terminal state where the cumulative score is greater than or equal to M. This results in M+1 states numbered 0 to M.
The probability distribution for the cumulative player score after n trials is given by the left column of the transition matrix to the power n. For my particular problem I have found that the probability that the score is > 4*n is trivially small after a large number of trials and therefore define M as 4*n. For small values of n (less than 1000) this can be computed (albeit slowly) by exponentiating the transition matrix directly (using exponentiation by squaring), but what I am interested in is very large values of n, in which case, the transition matrix wouldn't even fit in memory.
What I am looking for is a way to compute only the first column of the transition matrix raised to the n-th power for a very large transition matrix (or another way to represent the problem that can feasibly be computed).