//-------------------------------------------------------------------
//	matpower.cpp
//
//	This program will compute and display successive powers of 
//	a Markov chain's transition matrix with specified entries.
//
//		to compile:  $ g++ matpower.cpp -o matpower
//		to execute:  $ ./matpower
//
//	programmer: ALLAN CRUSE
//	written on: 04 MAR 2011
//-------------------------------------------------------------------

#include <stdio.h>		// for printf() 
#include <string.h>		// for memcpy()

#define	N_STATES	2	// number of states 
#define N_STEPS		14	// number of steps

typedef double Matrix[ N_STATES ][ N_STATES ];

Matrix transition = { .8, .2, .3, .7 };

int main( int argc, char **argv )
{
	// display the specified transition matrix
	printf( "\n The Markov Chain Transition Matrix: " );
	for (int i = 0; i < N_STATES; i++)
		{
		printf( "\n         " );
		for (int j = 0; j < N_STATES; j++)
			printf( " %1.4f ", transition[ i ][ j ] );
		}
	printf( "\n\n" );

	// initialize the current matrix power
	Matrix	current;
	for (int i = 0; i < N_STATES; i++)
	for (int j = 0; j < N_STATES; j++)
		current[ i ][ j ] = ( i == j ) ? 1.0 : 0.0;

	// display the sequence of matrix powers
	for ( int step = 0; step < N_STEPS; step++)
		{
		// compute the next matrix power 
		Matrix	product;
		for (int i = 0; i < N_STATES; i++)
		for (int j = 0; j < N_STATES; j++)
			{
			double	sum = 0.0;
			for (int k = 0; k < N_STATES; k++)
				sum += current[ i ][ k ] * transition[ k ][ j ];
			product[ i ][ j ] = sum;
			}
		memcpy( current, product, sizeof( Matrix ) );

		// display the current matrix power
		printf( "\n The Transition Matrix to power %d: ", step+1 );
		for (int i = 0; i < N_STATES; i++)
			{
			printf( "\n         " );
			for (int j = 0; j < N_STATES; j++)
				printf( " %1.4f ", current[ i ][ j ] );
			}
		printf( "\n" );
		}
	printf( "\n" );
}