Markov chains : a graph theoretical approach
- Authors: Marcon, Sinclair Antony
- Date: 2013-05-01
- Subjects: Markov processes , Graph theory
- Type: Thesis
- Identifier: uj:7506 , http://hdl.handle.net/10210/8363
- Description: M.Sc. (Mathematics) , In chapter 1, we give the reader some background concerning digraphs that are used in the discussion of Markov chains; namely, their Markov digraphs. Warshall’s Algorithm for reachability is also introduced as this is used to define terms such as transient states and irreducibility. Some initial theory and definitions concerning Markov chains and their corresponding Markov digraphs are given in chapter 2. Furthermore, we discuss l–step transitions (walks of length l) for homogeneous and inhomogeneous Markov chains and other generalizations. In chapter 3, we define terms such as communication, intercommunication, recurrence and transience. We also prove some results regarding the irreducibility of some Markov chains through the use of the reachability matrix. Furthermore, periodicity and aperiodicity are also investigated and the existence of walks of any length greater than some specified integer N is also considered. A discussion on random walks on an undirected torus is also contained in this chapter. In chapter 4, we explore stationary distributions and what it means for a Markov chain to be reversible. Furthermore, the hitting time and the mean hitting time in a Markov digraph are also defined and the proof of the theorems regarding them are done. The demonstrations of the theorems concerning the existence and uniqueness of stationary distributions and the Markov Chain Convergence Theorem are carried out. Later in this chapter, we define the Markov digraph of undirected graphs, which are Markov chains as well. The existing theory is then applied to these. In chapter 5, we explore and see how to simulate Markov chains on a computer by using Markov Chain Monte Carlo Methods. We also show how these apply to random q–colourings of undirected graphs. Finally, in chapter 6, we consider a physical application of these Graph Theoretical concepts—the simulation of the Ising model. Initially, the relevant concepts of the Potts model are given and then the Gibbs sampler algorithm in chapter 5 is modified and used to simulate the Ising model. A relation between the chromatic polynomial and the partition function of the Potts model is also demonstrated.
- Full Text:
Narrowband PLC channel modeling using USRP and PSK modulations
- Authors: Familua, A. D. , Ogunyanda, K. , Swart, Theo G. , Van Olst, Rex , Cheng, L.
- Date: 2014
- Subjects: Markov processes , Carrier transmission on power lines , Forward error correction , Quadrature phase shift keying , Software radio , Narrowband power line communications , Power line communications
- Type: Article
- Identifier: uj:4804 , http://hdl.handle.net/10210/12061
- Description: The indoor narrowband power line communication (NB-PLC) suffers from noise impairments, which emanate from several end-user electrical devices connected across the PLC channel. These noise impairments result into burst errors, which consequently lead to data corruption. Therefore, in order to implement robust communication techniques that will thrive on the noisy PLC channel, a full knowledge and modeling of the noise that exists on the NB-PLC channel is inevitable. This paper thus reports a First-order Markov modeling of NB-PLC channel noise, based on experimental measurements. For the modeling, BPSK, DBPSK, QPSK and DQPSK modulation schemes were implemented using Universal Software Radio Peripheral (USRP). The resulting channel models are useful for improving the robustness of the above modulation schemes as well as designing forward error correction techniques for mitigating the effect of noise impairments. The results are also useful in optimizing NB-PLC system design, thereby, enhancing the accuracy and improving the overall PLC system performance.
- Full Text:
Markov characterization of fading channels
- Authors: Swarts, Francis
- Date: 2014-07-31
- Subjects: Markov processes
- Type: Thesis
- Identifier: uj:11937 , http://hdl.handle.net/10210/11665
- Description: M. Ing. (Electrical and Electronic Engineering) , This thesis investigates various methods of modeling fading communication channels. These modeling methods include various techniques for the modeling of different fading mechanisms. The fading mechanism mainly considered throughout this thesis, is slow Rayleigh fading. Concise mathematical methods of modeling the effect that a fading communication channel has on binary digital data passing through it, is considered. A discussion on binary channel models, presented in the past, such as the Gilbert, Gilbert - Elliott and Fritchman channel models is also presented. All of these mathematical channel modeling techniques, are Markov chain based. Most of the investigations undertaken during the course of this work were based on Fritchman channel models. Results indicating the capabilities as well as the short falls of Fritchman models are presented. The experimental results presented here were obtained using dedicated error recording equipment, designed especially for the purpose of undertaking measurements, which enables one to deduce mathematical channel models. Detail regarding this equipment can be found in one of the two accompanying volumes, volume II. Furthermore, a new approach to channel modeling, based on hidden Markov models, is also presented for the modeling of channels with soft decision outputs. Results proving the accuracy of the proposed soft decision modeling technique, are also presented.
- Full Text:
Markov chain Monte Carlo methods for finite element model updating
- Authors: Joubert, Daniel Johannes
- Date: 2015
- Subjects: Finite Element Method , Markov processes , Monte Carlo method , Computer simulation
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/57283 , uj:16375
- Description: Abstract: Finite Element model updating is a computation tool aimed at aligning the computed dynamic properties in the Finite Element (FE) model, i.e. eigenvalues and eigenvectors, and experimental modal data of rigid body structures. Generally, FE models have very high degrees of freedom, often several thousands. The Finite Element Method (FEM) is only able to accurately predict a few of the natural frequencies and mode shapes (eigenvalues and eigenvectors). In order to ensure the validity of the FEM, a chosen number of the natural frequencies and mode shapes are experimentally measured. These are often misaligned or in disagreement with the results from the computed FEM. Finite Element (FE) model updating is a concept wherein a variety of methods are used to compute physically accurate modal frequencies for structures, accounting for random behavior of material properties under dynamic conditions, this behavior can be termed stochastic. The author applies two methods applied in recent years, and one new algorithm to further investigate the effectiveness of introducing multivariate Gaussian mixture models and Bayesian analysis in the model updating context. The focus is largely based on Markov Chain Monte Carlo methods whereby all inference on uncertainties is based on the posterior probability distribution obtained from Bayes’ theorem. Observations are obtained sequentially providing an on-line inference in approximating the posterior probability. In the coming Chapters detailed descriptions will cover all the theory and arithmetic involved for the simulated algorithms. The three algorithms are, the standard Metropolis Hastings (MH), Adaptive Metropolis Hastings (AMH), and Monte Carlo Dynamically Weighted Importance Sampling (MCDWIS). Metropolis Hastings (MH) is a well-known Markov Chain Monte Carlo (MCMC) sampling method. The desired result from this algorithm is a good acceptance rate and good correlation between the computed stochastic parameters. The Adaptive Metropolis Hastings (AMH) algorithm adaptively scales the covariance matrix ‘on the fly’ to see convergence to a Gaussian target distribution. From the AMH algorithm we want to observe the adaptation of the scaling factor and the covariance matrix. Monte Carlo Dynamically Weighted Importance Sampling (MCDWIS) is an algorithm which combines Importance Sampling theory with Dynamic Weighting theory in a population control scheme, namely the Adaptive Pruned Enriched Population Control Scheme (APEPCS). The motivation behind applying MCDWIS is in the complexity of computing normalizing constants in higher dimensional or multimodal systems. In addition, a dynamic weighting step with an Adaptive Pruned Enriched Population Control Scheme (APEPCS) allows for further control over weighted samples and population size. The performance of the MCDWIS simulation... , M.Ing. Mechanical Engineering
- Full Text:
A manpower planning model to predict future workforce behaviour and retention : a Markov chain approach
- Authors: Okaekwu, Emeka David
- Date: 2016
- Subjects: Manpower planning , Manpower planning - Case studies , Manpower planning - Evaluation , Human capital , Markov processes
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/233637 , uj:23858
- Description: M.Phil. (Engineering Management) , Abstract: Proper manpower planning is a key factor in the demand and supply of workforce in every organization. It probes the skills and capability sets, the right quantity, location, timing, and quality of the needed manpower. It is evident according to empirical studies that undivided attention has been given to manpower planning in the last decade. Different bodies involved include government parastatals, academic and industrial organizations and institutions performing some form of manpower planning research and activities to maintain stability and retention in the system. Whether these inputs are reflected in the manpower policies and make a significant contribution in this regard is yet to be seen. Several analytics and methods of modelling manpower planning exist, however, Markov chain has been used widely and accepted in various facets and domains. In this research, Markov Chain is used as a tool to analyse the manpower data from an academic institution as a case study with the aim to unearthing the hidden details regarding existing manpower policies and hence, its fairness and robustness towards staff training, promotion, and ultimately retention. A 9-year stage of manpower data split into states is used and matrix operations employed in analysing the manpower data obtained. Bayesian probability is also used for establishing the transition probability matrix (TPrM), and these matrix transformations are carried out repeatedly to achieve stability. The results of the analysis show that manpower policy in the participating organization towards overall staff retention is rigid and stern. The results clearly satisfy the purpose of the study which is to predict the trend in the manpower practice, the potential cause of manpower loss and subsequently, the flow and fairness of the existing manpower policy.
- Full Text:
Modelling a random cash flow of an asset using the Semi-Markovian model
- Authors: Mishindo, Leon Mbucici
- Date: 2016
- Subjects: Markov processes , Stochastic processes , Cash flow , Finance - Mathematical models
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/245887 , uj:25478
- Description: M.Com. , Abstract: In this dissertation, we have used a semi-Markovian model to calculate the conditional higher moments of any order of the present value of cash flows generated by an investment, taking into account the state of the market. With the force of interest following a stochastic process, we give an example to illustrate our results. In this work we assume that the state of economy explains the state of a country’s finances. This state is perceptible on the basis of certain indicators such as the index of a stock market. In South Africa it is the All Share Index (ALSI) that we have taken into consideration. We have observed the daily series of the ALSI index for the period from 6 December 1994 to 6 September 2014. We have further subdivided this period into two sub-periods. The first sub-period runs from December 6, 1994 to December 31, 2007 coinciding with the period before the global financial crisis and the second sub-period runs from January 1, 2008 to September 6, 2014, and relates to the post-crisis period. We have found that the daily average of the index for the pre-crisis is much lower than the daily average for the post-crisis period. Consequently, we assumed that each of these two periods put the South African economy in a particular state. Symbolically we denote state1 to represent the pre-crisis state, corresponding to the low level of the index and state0 for which the index has a high average. The consideration of South African data to conduct this study is essentially judged by the importance of its economy on the African continent. Moreover, this study established a multi-state model based on a semi-Markov approach that calculates the moments of any order of the present value of a given cash-flow. As results we found explicit formulas for the first two moments for the compound renewal sums with discounted cash flows, for a random interest rate. We observe that the length of stay in a state has a positive influence on the current value of moments in state 0. Instead In the state 1 when the length of stay increases, the present value of moments shows a slight downward trend. In additional to the above findings, when considering time, the current values of moments of order 1 are growing except in the case where the interest rate is lower in state 1. But when the interest rate increases the present value of moments also increases, even when the length of stays increasing this cause moments to increase. When the interest rate is lower, the moments of order 2 decrease with time regardless of the state in which we stand. The length of stay has the same effect on the moments, it positively influences the moments of order 2 in the state 0,..
- Full Text:
Worldwide interoperability for microwave access performance simulations using Markov model and simulators
- Authors: Nkaule, Sandla
- Date: 2017
- Subjects: IEEE 802.16 (Standard) , Wireless communication systems , Signal processing - Digital techniques , Microwave transmission lines , Markov processes
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/262611 , uj:27728
- Description: M.Tech. (Electrical Engineering) , Abstract: Wireless communication has been part of communication for decades and continues to evolve in a radical manner. These days communication cannot be separated with various technologies and newly developed devices tend to be integrated to support wireless. WiMAX is a wireless industry coalition and is part of the latest wireless infrastructure which includes 3G and LTE and needs to supports both communication and other technologies. WiMAX is seen as WiFi that supports greater distances of up to about 50 kms in radius. In this study we simulate the WiMAX performance - simulations are done using OPNET, NS-3 and Markov Chains are also used to evaluate the performance and compare the results. The study looks at the delay and the throughput in the WiMAX network as we increase numbers of connected devices from 20 to 50, 75 and lastly 100 mobile devices. The results of these performance indicators were analyzed and OPNET was found to be the best simulation tool amongst the three that was user friendly and easy to work with, which also returned results that are satisfactory and resembles reality.
- Full Text:
Low disparity channel coding schemes for DC free transmission
- Authors: Heymann, Carl
- Date: 2018
- Subjects: Coding theory , Markov processes , Information theory , Electric current converters
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/262895 , uj:27787
- Description: Abstract: In this dissertation, three new DC free coding schemes are presented. The first is inspired by the balancing scheme by Knuth, as well as the work by Frontana, Jamieson and Fair. It is a multi-mode, low-disparity scheme, that controls the running digital sum (RDS) of a sequence by creating an inversion point, indicated by a number of redundant prefix bits. The number of prefix bits can be varied in the design of a specific scheme, allowing the designer to trade code rate for DC suppression performance. The second scheme uses the same concepts, applied to run-length limited (RLL) sequences. The new scheme inserts a fixed-length, inverting marker at a point in each codeword such that the overall sequence’s RDS is minimised. The third coding scheme is a variable-length scheme applied to run-length limited sequences. It inserts special marker runs, of a reserved run-length, whenever the RDS exceeds a threshold value. A Markov chain model is presented, allowing the code rate and RDS variance to be accurately predicted when encoding maxentropic RLL sequences. A lower RDS variance reflects better DC-suppression performance. , M.Ing. (Electrical Engineering)
- Full Text:
Policy uncertainty, credit risk and unemployment in South Africa
- Authors: Leballo, Keorapetse
- Date: 2020
- Subjects: South Africa - Economic policy , Credit - Risk assessment , Medical policy - South Africa , Markov processes
- Language: English
- Type: Masters (Thesis)
- Identifier: http://hdl.handle.net/10210/474700 , uj:42796
- Description: Abstract: A high and persistent level of unemployment along with the elevated costs of servicing debt are among the major challenges facing the South African government today. To this end, this study examines the role that sovereign credit risk and economic policy uncertainty respectively have on these two major challenges. We make use of a vector error correction and Markov-chain model to quantify these impacts under the guidance of pre-existing long-run cointegrating relationships, as well as the transitory assumption of interest rates across the evolution of the business cycle. Controlling for other salient macroeconomic features, our empirical findings point towards the existence of a symmetrical response of unemployment rates to changes in the credit risk level. Moreover, elevated forms of policy uncertainty are found to have adverse effects on debt servicing costs, where the impact is seen to be less pronounced during periods of slowing economic activity. The policy implication is that elevated levels of policy uncertainty reduce access to debt capital markets, as illustrated by increasing debt servicing costs, which consequently lessen government’s ability to raise funding and absorb an idling labour force... , M.Com. (Economics)
- Full Text: