Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach

Using methods of statistical physics, we study the average number and kernel size of general sparse random matrices over GF(q), with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of GF(q) matrices onto spin systems using the representation of the cyclic group of order q as the q-th complex roots of unity. This representation facilitates the derivation of the average kernel size of random matrices using the replica approach, under the replica symmetric ansatz, resulting in saddle point equations for general connectivity distributions. Numerical solutions are then obtained for particular cases by population dynamics. Similar techniques also allow us to obtain an expression for the exact and average number of random matrices for any general connectivity profile. We present numerical results for particular distributions.

The Number of Parts of Given Multiplicity in a Random Integer Partition

2000 Mathematics Subject Classification: 05A16, 05A17.

Exploring the random genesis of co-occurrence networks

Using the network random generation models from Gustedt (2009)[23], we simulate and analyze several characteristics (such as the number of components, the degree distribution and the clustering coefficient) of the generated networks. This is done for a variety of distributions (fixed value, Bernoulli, Poisson, binomial) that are used to control the parameters of the generation process. These parameters are in particular the size of newly appearing sets of objects, the number of contexts in which new elements appear initially, the number of objects that are shared with `parent` contexts, and, the time period inside which a context may serve as a parent context (aging). The results show that these models allow to fine-tune the generation process such that the graphs adopt properties as can be found in real world graphs. (C) 2011 Elsevier B.V. All rights reserved.

PREVALENCE OF ANTI- Toxocara ANTIBODIES IN A RANDOM SAMPLE OF INPATIENTS AT A CHILDREN'S HOSPITAL IN VITÓRIA, ESPÍRITO SANTO, BRAZIL

In the streets of Vitória, in the State of Espírito Santo, Brazil, are large number of stray dogs, many of which are infected with Toxocara canis, suggesting a high risk for human infection. In order to investigate the prevalence of Toxocara infection in children in Espírito Santo we studied the prevalence of anti-Toxocara antibodies in 100 random inpatients over one year of age, at the Children's Hospital N.S. da Glória, the reference children's hospital for the State.All the sera were collected during the period between October 1996 and January 1997. The mean age was 6.6±4.1 yrs. (1 to 14 yrs., median 6yrs.) and there were patients from all of the different wards of the hospital. Sixty-eigth patients came from the metropolitan area of Vitória and the other 32 from 17 other municipalities. The anti-Toxocara antibodies were investigated by ELISA-IgG using a secretory-excretory antigen obtained from second stage larvae. All sera were adsorbed with Ascaris suum antigen before the test. Thirty-nine sera (39%) were positive, predominantly from boys, but the gender difference was not statistically significant (boys:25/56 or 44.6%; girls:14/44 or 31.8%; p=0.311). The prevalence of positive sera was higher, but not statistically significant, in children from the urban periphery of metropolitan Vitória (formed by the cities of Vitória, Cariacica, Vila Velha, Serra and Viana) than in children from 17 other municipalities (44.1% and 28.1% respectively, p=0.190). Although the samples studied do not represent all children living in the State of Espírito Santo, since the Children's Hospital N.S. da Glória admits only patients from the state health system, it is probable that these results indicate a high frequency of Toxocara infection in children living in Espírito Santo. Further studies of population samples are necessary to ascertain the prevalence of Toxocara infection in our country.

Sequencing and identification of expressed Schistosoma mansoni genes by random selection of cDNA clones from a directional library

We have initiated a gene discovery program in Schistosoma mansoni based on the technique of Expressed Sequence Tags (ESTs), i.e. partial sequences of cDNAs obtained from single passes in automatic DNA sequencers. ESTs can be used to identify genese onf the basis of their homology whith sequences from other species deposited in DNA or protein databases. Trasncripts with sequences without matches in teh databases may represent novel parasite-specific genes. This approach has shown to be very efficient and in less than two years a broad range of novel genes has already been ascertained, more than doubling the number of known S. mansoni genes.

The number of families of Triatoma dimidiata in a Guatemalan house

Triatoma dimidiata is an important vector of Chagas disease in Guatemala. To help understand the biology and population dynamics of the insect, we estimated the number of full sibling families living in one house. Forty one families with an average size of 2.17 individuals were detected using random amplification of polymorphic DNA-polymerase chain reaction genetic markers. This result suggests high levels of migration of the vector, polyandry, and a significant capability for spreading the disease.

Multiuser detection with an unknown number of active users: receiver design

In multiuser detection, the set of users active at any time may be unknown to the receiver. In these conditions, optimum reception consists of detecting simultaneously the set of activeusers and their data, problem that can be solved exactly by applying random-set theory (RST) and Bayesian recursions (BR). However, implementation of optimum receivers may be limited by their complexity, which grows exponentially with the number of potential users. In this paper we examine three strategies leading to reduced-complexity receivers.In particular, we show how a simple approximation of BRs enables the use of Sphere Detection (SD) algorithm, whichexhibits satisfactory performance with limited complexity.

The Effect of Four-Lane to Three-Lane Conversion on the Number of Crashes and Crash Rates in Iowa Roads, June 2005

We analyze crash data collected by the Iowa Department of Transportation using Bayesian methods. The data set includes monthly crash numbers, estimated monthly traffic volumes, site length and other information collected at 30 paired sites in Iowa over more than 20 years during which an intervention experiment was set up. The intervention consisted in transforming 15 undivided road segments from four-lane to three lanes, while an additional 15 segments, thought to be comparable in terms of traffic safety-related characteristics were not converted. The main objective of this work is to find out whether the intervention reduces the number of crashes and the crash rates at the treated sites. We fitted a hierarchical Poisson regression model with a change-point to the number of monthly crashes per mile at each of the sites. Explanatory variables in the model included estimated monthly traffic volume, time, an indicator for intervention reflecting whether the site was a “treatment” or a “control” site, and various interactions. We accounted for seasonal effects in the number of crashes at a site by including smooth trigonometric functions with three different periods to reflect the four seasons of the year. A change-point at the month and year in which the intervention was completed for treated sites was also included. The number of crashes at a site can be thought to follow a Poisson distribution. To estimate the association between crashes and the explanatory variables, we used a log link function and added a random effect to account for overdispersion and for autocorrelation among observations obtained at the same site. We used proper but non-informative priors for all parameters in the model, and carried out all calculations using Markov chain Monte Carlo methods implemented in WinBUGS. We evaluated the effect of the four to three-lane conversion by comparing the expected number of crashes per year per mile during the years preceding the conversion and following the conversion for treatment and control sites. We estimated this difference using the observed traffic volumes at each site and also on a per 100,000,000 vehicles. We also conducted a prospective analysis to forecast the expected number of crashes per mile at each site in the study one year, three years and five years following the four to three-lane conversion. Posterior predictive distributions of the number of crashes, the crash rate and the percent reduction in crashes per mile were obtained for each site for the months of January and June one, three and five years after completion of the intervention. The model appears to fit the data well. We found that in most sites, the intervention was effective and reduced the number of crashes. Overall, and for the observed traffic volumes, the reduction in the expected number of crashes per year and mile at converted sites was 32.3% (31.4% to 33.5% with 95% probability) while at the control sites, the reduction was estimated to be 7.1% (5.7% to 8.2% with 95% probability). When the reduction in the expected number of crashes per year, mile and 100,000,000 AADT was computed, the estimates were 44.3% (43.9% to 44.6%) and 25.5% (24.6% to 26.0%) for converted and control sites, respectively. In both cases, the difference in the percent reduction in the expected number of crashes during the years following the conversion was significantly larger at converted sites than at control sites, even though the number of crashes appears to decline over time at all sites. Results indicate that the reduction in the expected number of sites per mile has a steeper negative slope at converted than at control sites. Consistent with this, the forecasted reduction in the number of crashes per year and mile during the years after completion of the conversion at converted sites is more pronounced than at control sites. Seasonal effects on the number of crashes have been well-documented. In this dataset, we found that, as expected, the expected number of monthly crashes per mile tends to be higher during winter months than during the rest of the year. Perhaps more interestingly, we found that there is an interaction between the four to three-lane conversion and season; the reduction in the number of crashes appears to be more pronounced during months, when the weather is nice than during other times of the year, even though a reduction was estimated for the entire year. Thus, it appears that the four to three-lane conversion, while effective year-round, is particularly effective in reducing the expected number of crashes in nice weather.

Random amplification of polymorphic DNA reveals clonal relationships among enteropathogenic Escherichia coli isolated from non-human primates and humans

Enteropathogenic Escherichia coli (EPEC) strains are important agents of infantile diarrhea all over the world, gaining even greater importance in developing countries. EPEC have also been isolated from various animal species, but most isolates belong to serotypes that differ from those recovered from humans. However, it has been demonstrated that several isolates from non-human primates belong to the serogroups and/or serotypes related to those implicated in human disease. The objective of this study was to evaluate the genetic differences between thirteen strains isolated from non-human primates and the same number of strains isolated from human infections. Human isolates belonged to the same serogroup/serotype as the monkey strains and the evaluation was done by analysis of random amplified polymorphic DNA. Dendrogram analysis showed that there was no clustering between human and monkey strains. Human and non-human isolates of the EPEC serotypes O127:H40 and O128:H2 shared 90 and 87% of their bands, respectively, indicating strong genomic similarity between the strains, leading to the speculation that they may have arisen from the same pathogenic clone. To our knowledge, this study is the first one comparing genomic similarity between human and non-human primate strains and the results provide further evidence that monkey EPEC strains correlate with human EPEC, as suggested in a previous investigation.

Image classification for a large number of object categories

L'increment de bases de dades que cada vegada contenen imatges més difícils i amb un nombre més elevat de categories, està forçant el desenvolupament de tècniques de representació d'imatges que siguin discriminatives quan es vol treballar amb múltiples classes i d'algorismes que siguin eficients en l'aprenentatge i classificació. Aquesta tesi explora el problema de classificar les imatges segons l'objecte que contenen quan es disposa d'un gran nombre de categories. Primerament s'investiga com un sistema híbrid format per un model generatiu i un model discriminatiu pot beneficiar la tasca de classificació d'imatges on el nivell d'anotació humà sigui mínim. Per aquesta tasca introduïm un nou vocabulari utilitzant una representació densa de descriptors color-SIFT, i desprès s'investiga com els diferents paràmetres afecten la classificació final. Tot seguit es proposa un mètode par tal d'incorporar informació espacial amb el sistema híbrid, mostrant que la informació de context es de gran ajuda per la classificació d'imatges. Desprès introduïm un nou descriptor de forma que representa la imatge segons la seva forma local i la seva forma espacial, tot junt amb un kernel que incorpora aquesta informació espacial en forma piramidal. La forma es representada per un vector compacte obtenint un descriptor molt adequat per ésser utilitzat amb algorismes d'aprenentatge amb kernels. Els experiments realitzats postren que aquesta informació de forma te uns resultats semblants (i a vegades millors) als descriptors basats en aparença. També s'investiga com diferents característiques es poden combinar per ésser utilitzades en la classificació d'imatges i es mostra com el descriptor de forma proposat juntament amb un descriptor d'aparença millora substancialment la classificació. Finalment es descriu un algoritme que detecta les regions d'interès automàticament durant l'entrenament i la classificació. Això proporciona un mètode per inhibir el fons de la imatge i afegeix invariança a la posició dels objectes dins les imatges. S'ensenya que la forma i l'aparença sobre aquesta regió d'interès i utilitzant els classificadors random forests millora la classificació i el temps computacional. Es comparen els postres resultats amb resultats de la literatura utilitzant les mateixes bases de dades que els autors Aixa com els mateixos protocols d'aprenentatge i classificació. Es veu com totes les innovacions introduïdes incrementen la classificació final de les imatges.

Systolic random number generation for genetic algorithms

A parallel hardware random number generator for use with a VLSI genetic algorithm processing device is proposed. The design uses an systolic array of mixed congruential random number generators. The generators are constantly reseeded with the outputs of the proceeding generators to avoid significant biasing of the randomness of the array which would result in longer times for the algorithm to converge to a solution. 1 Introduction In recent years there has been a growing interest in developing hardware genetic algorithm devices [1, 2, 3]. A genetic algorithm (GA) is a stochastic search and optimization technique which attempts to capture the power of natural selection by evolving a population of candidate solutions by a process of selection and reproduction [4]. In keeping with the evolutionary analogy, the solutions are called chromosomes with each chromosome containing a number of genes. Chromosomes are commonly simple binary strings, the bits being the genes.

Examining random number generators used in stochastic iteration algorithms

This paper investigates random number generators in stochastic iteration algorithms that require infinite uniform sequences. We take a simple model of the general transport equation and solve it with the application of a linear congruential generator, the Mersenne twister, the mother-of-all generators, and a true random number generator based on quantum effects. With this simple model we show that for reasonably contractive operators the theoretically not infinite-uniform sequences perform also well. Finally, we demonstrate the power of stochastic iteration for the solution of the light transport problem.

Random-walk-based characterisation of multiple access interference in a DS/SSMA system

The problem of calculating the probability of error in a DS/SSMA system has been extensively studied for more than two decades. When random sequences are employed some conditioning must be done before the application of the central limit theorem is attempted, leading to a Gaussian distribution. The authors seek to characterise the multiple access interference as a random-walk with a random number of steps, for random and deterministic sequences. Using results from random-walk theory, they model the interference as a K-distributed random variable and use it to calculate the probability of error in the form of a series, for a DS/SSMA system with a coherent correlation receiver and BPSK modulation under Gaussian noise. The asymptotic properties of the proposed distribution agree with other analyses. This is, to the best of the authors' knowledge, the first attempt to propose a non-Gaussian distribution for the interference. The modelling can be extended to consider multipath fading and general modulation

A structure-dynamic approach to cortical organization: Number of paths and accessibility

A structure-dynamic approach to cortical systems is reported which is based on the number of paths and the accessibility of each node. The latter measurement is obtained by performing self-avoiding random walks in the respective networks, so as to simulate dynamics, and then calculating the entropies of the transition probabilities for walks starting from each node. Cortical networks of three species, namely cat, macaque and humans, are studied considering structural and dynamical aspects. It is verified that the human cortical network presents the highest accessibility and number of paths (in terms of z-scores). The correlation between the number of paths and accessibility is also investigated as a mean to quantify the level of independence between paths connecting pairs of nodes in cortical networks. By comparing the cortical networks of cat, macaque and humans, it is verified that the human cortical network tends to present the largest number of independent paths of length larger than four. These results suggest that the human cortical network is potentially the most resilient to brain injures. (C) 2009 Elsevier B.V. All rights reserved.

The number of open paths in an oriented rho-percolation model

We study the asymptotic properties of the number of open paths of length n in an oriented rho-percolation model. We show that this number is e(n alpha(rho)(1+o(1))) as n ->infinity. The exponent alpha is deterministic, it can be expressed in terms of the free energy of a polymer model, and it can be explicitly computed in some range of the parameters. Moreover, in a restricted range of the parameters, we even show that the number of such paths is n(-1/2)We (n alpha(rho))(1+o(1)) for some nondegenerate random variable W. We build on connections with the model of directed polymers in random environment, and we use techniques and results developed in this context.