A Markov chain Monte Carlo Algorithm for Approximating Exact Conditional Probabilities

Conditional inference eliminates nuisance parameters by conditioning on their sufficient statistics. For contingency tables conditional inference entails enumerating all tables with the same sufficient statistics as the observed data. For moderately sized tables and/or complex models, the computing time to enumerate these tables is often prohibitive. Monte Carlo approximations offer a viable alternative provided it is possible to obtain samples from the correct conditional distribution. This article presents an MCMC extension of the importance sampling algorithm, using a rounded normal candidate to update randomly chosen cells while leaving the remainder of the table fixed. This local approximation can greatly increase the efficiency of the rounded normal candidate. By choosing the number of cells to be updated at random, a balance is struck between dependency in the Markov chain and accuracy of the candidate.     

A robust implementation of a sequential quadratic programming algorithm with successive error restoration

We consider sequential quadratic programming methods for solving constrained nonlinear programming problems. It is generally believed that these methods are sensitive to the accuracy by which partial derivatives are provided. One reason is that differences of gradients of the Lagrangian function are used for updating a quasi-Newton matrix, e.g., by the BFGS formula. The purpose of this paper is to show by numerical experimentation that the method can be stabilized substantially. The algorithm applies non-monotone line search and internal and external restarts in case of errors due to inaccurate derivatives while computing the search direction. Even in case of large random errors leading to partial derivatives with at most one correct digit, termination subject to an accuracy of 10⁻⁷ can be achieved in 90% of 306 problems of a standard test suite. On the other hand, the original version with monotone line search and without restarts solves only 30% of these problems under the same test environment. In addition, we show how initial and periodic scaled restarts improve the efficiency in situations with slow convergence.     

Invariant imbedding,iterative linearization,and multistage countercurrent processes. VI. Complex distillation column and multipoint boundary value problem

The complex distillation column problem is formulated as a multipoint boundary value problem in difference equations. It is shown that this nonlinear multipoint boundary value problem can be solved easily by the quasilinearization technique. With very rough initial approximations, only ten iterations are needed to obtain a four digit accuracy in concentrations. The advantage of this approach is that the complex column can be solved in essentially the same way as the simple column with approximately the same computation requirements.     

Structure of planar integral self‐affine tilings

For a self‐affine tile in $\mathbf {R}^2$ generated by an expanding matrix $A\in M_2(\mathbf {Z})$ and an integral consecutive collinear digit set ${\mathcal D}$, Leung and Lau [Trans. Amer. Math. Soc. 359 , 3337–3355 (2007).] provided a necessary and sufficient algebraic condition for it to be disklike. They also characterized the neighborhood structure of all disklike tiles in terms of the algebraic data A and ${\mathcal D}$. In this paper, we completely characterize the neighborhood structure of those non‐disklike tiles. While disklike tiles can only have either six or eight edge or vertex neighbors, non‐disklike tiles have much richer neighborhood structure. In particular, other than a finite set, a Cantor set, or a set containing a nontrivial continuum, neighbors can intersect in a union of a Cantor set and a countable set.     

Language Influence on Children's Cognitive Number Representation

This study examined the effect of language on children's cognitive representation of number. The sample for the study consisted of 90 Arabic speaking children with a mean age of 80 months. Children were interviewed individually and asked to represent written two‐digit numbers using base‐10 blocks. A new approach for testing the linguistic relativity hypothesis was used. The results of the study revealed that language played an important role in children's cognitive number representation. On the other hand, the results support the argument that the instructions given with the task alter children's performance on it. This study suggests that language may explain the cross‐cultural differences in mathematics achievement. However, the disadvantage that the language might place on children can be overcome with well‐planned instruction.     

Components of Place Value Understanding: Targeting Mathematical Difficulties When Providing Interventions

Place value understanding requires the same activity that students use when developing fractional and algebraic reasoning, making this understanding foundational to mathematics learning. However, many students engage successfully in mathematics classrooms without having a conceptual understanding of place value, preventing them from accessing mathematics that is more sophisticated later. The purpose of this exploratory study is to investigate how upper elementary students' unit coordination related to difficulties they experience when engaging in place value tasks. Understanding place value requires that students coordinate units recursively to construct multi‐digit numbers from their single‐digit number understandings through forms of unit development and strategic counting. Findings suggest that students identified as low‐achieving were capable of only one or two levels of unit coordination. Furthermore, these students relied on inaccurate procedures to solve problems with millennial numbers. These findings indicate that upper elementary students identified as low‐achieving are not to yet able to (de)compose numbers effectively, regroup tens and hundreds when operating on numbers, and transition between millennial numbers. Implications of this study suggest that curricula designers and statewide standards should adopt nuances in unit coordination when developing tasks that promote or assess students' place value understanding.     

Asymptotic properties of digit sequences of random numbers

We consider several aspects of the relationship between a [0, 1]‐valued random variable X and the random sequence of digits given by its m‐ary expansion. We present results for three cases: (a) independent and identically distributed digit sequences; (b) random variables X with smooth densities; (c) stationary digit sequences. In the case of i.i.d. an integral limit thorem is proved which applies for example to relative frequencies, yielding asymptotic moment identities. We deal with occurrence probabilities of digit groups in the case that X has an analytic Lebesgue density. In the case of stationary digits we determine the distribution of X in terms of their transition functions. We study an associated [0, 1]‐valued Markov chain, in particular its ergodicity, and give conditions for the existence of stationary digit sequences with prespecified transition functions. It is shown that all probability measures induced on [0, 1] by such sequences are purely singular except for the uniform distribution. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimum Spanning Table and Optimal Expansion of Competence Set

Each directed graph with asymmetric costs defined over its arcs can be represented by a matrix or table, called an expansion table. We explore first the basic properties of cycles and spanning tables of expansion tables, which correspond to the cycles and spanning trees of the directed graph. Then, we derive an algorithm to find a minimum spanning table which corresponds to a minimum spanning tree in the directed graph. Finally, we discuss how to use the algorithm to find the optimal competence set expansion and also discuss related problems.     

Knowing and Teaching Middle School Mathematics: A Professional Development Course for In‐Service Teachers

This article describes a professional development course intended to improve the content understanding of middle school mathematics teachers. The design of the course included three professional learning strategies: problem solving, examination of student thinking, and discussion of research. The concepts studied in the course included multi‐digit subtraction, multi‐digit multiplication, operations with fractions, and concepts of area and perimeter. Results from pre‐ and post‐tests administered to the nineteen participants indicate a significant increase in the mean score for each concept and document growth in the teachers' content understanding. In particular, their solutions moved from primarily procedural to more conceptual. Responses to an open‐ended survey indicate other important aspects of the professional development. Examples of teachers' work and comments are included.     

On roots and squares – estimation,intuition and creativity

The paper presents findings of a small scale study of a few items related to problem solving with squares and roots, for different teacher groups (pre-service and in-service mathematics teachers: elementary and junior high school). The research participants were asked to explain what would be the units digit of a natural number to be squared in order to obtain a certain units digit as a result. They were also asked to formulate a rule – an algorithm for calculating the square of a 2-digit number which is a multiple of 5. Based on this knowledge and estimation capability, they were required to find, without using calculators, the square roots of given natural numbers. The findings show that most of the participants had only partial intuition regarding the units’ digit of a number which is squared when the units’ digit of the square is known. At the same time, the participants manifested some evidence of creativity and flow of ideas in identifying the rule for calculating the square of a natural number whose units digit is 5. However, when asked to identify, by means of estimation and based on knowledge from previous items, the square roots of three natural numbers, only few of them managed to find the three roots by estimation.     

Developing the concept of linear function: one student’s experiences with dynamic physical models

Developing a view of functions as systematic processes involving co-variation among variables has been identified as a goal for mathematics learners at the pre-university level. In this investigation I examined the processes used by an eighth-grade student to interpret linear functions originating in dynamic physical models and the processed he used to link his interpretations to tables, equations, and graphs. The student deepened his understanding of functions by generalizing his view of multiplication beyond that of products resulting from the multiplication of individual factors or from repeated addition. He was enabled to do this by building links between graphic and tabular representations of the functions generated from his exploration with dynamic physical models and by comparing tables of different linear functions. This paper suggests that the development of a student’s reasoning about functions originating in dynamic physical models can be interpreted in terms of generalized multiplicative processes that may occur thorough mapping variations and that a student who interprets such functions as generalized multiplicative processes may use notational variations to generate representing equations.     

Solving hyperbolic conservation laws using multiquadric quasi‐interpolation

In this article, we apply the univariate multiquadric (MQ) quasi‐interpolation to solve the hyperbolic conservation laws. At first we construct the MQ quasi‐interpolation corresponding to periodic and inflow‐outflow boundary conditions respectively. Next we obtain the numerical schemes to solve the partial differential equations, by using the derivative of the quasi‐interpolation to approximate the spatial derivative of the differential equation and a low‐order explicit difference to approximate the temporal derivative of the differential equation. Then we verify our scheme for the one‐dimensional Burgers' equation (without viscosity). We can see that the numerical results are very close to the exact solution and the computational accuracy of the scheme is ??(τ), where τ is the temporal step. We can improve the accuracy by using the high‐order quasi‐interpolation. Moreover the methods can be generalized to the other equations. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

On Markov chain Monte Carlo Algorithms for Computing Conditional Expectations Based on Sufficient Statistics

Much work has focused on developing exact tests for the analysis of discrete data using log linear or logistic regression models. A parametric model is tested for a dataset by conditioning on the value of a sufficient statistic and determining the probability of obtaining another dataset as extreme or more extreme relative to the general model, where extremeness is determined by the value of a test statistic such as the chi-square or the log-likelihood ratio. Exact determination of these probabilities can be infeasible for high dimensional problems, and asymptotic approximations to them are often inaccurate when there are small data entries and/or there are many nuisance parameters. In these cases Monte Carlo methods can be used to estimate exact probabilities by randomly generating datasets (tables) that match the sufficient statistic of the original table. However, naive Monte Carlo methods produce tables that are usually far from matching the sufficient statistic. The Markov chain Monte Carlo method used in this work (the regression/attraction approach) uses attraction to concentrate the distribution around the set of tables that match the sufficient statistic, and uses regression to take advantage of information in tables that “almost” match. It is also more general than others in that it does not require the sufficient statistic to be linear, and it can be adapted to problems involving continuous variables. The method is applied to several high dimensional settings including four-way tables with a model of no four-way interaction, and a table of continuous data based on beta distributions. It is powerful enough to deal with the difficult problem of four-way tables and flexible enough to handle continuous data with a nonlinear sufficient statistic.     

Invariant imbedding,iterative linearization,and multistage countercurrent processes. V. Temperature as one unknown variable in distillation column calculations

Quasilinearization is used to solve multicomponent distillation problems with temperature and (m ? 1) concentration variables as the unknowns, where m is the number of components. By including temperature as one unknown, implicit differentiation is no longer necessary, and thus the difficulty encountered in an earlier paper can be avoided. Since all the functions and variables are linearized, the quadratic convergence property of quasilinearization is obtained. A five digit accuracy in concentration is obtained in four iterations with very rough starting values.     

Conditional Inference on Tables With Structural Zeros

We develop a set of sequential importance sampling (SIS) strategies for sampling nearly uniformly from two-way zero-one or contingency tables with fixed marginal sums and a given set of structural zeros. The SIS procedure samples tables column by column or cell by cell by using appropriate proposal distributions, and enables us to approximate closely the null distributions of a number of test statistics involved in such tables. When structural zeros are on the diagonal or follow certain patterns, more efficient SIS algorithms are developed which guarantee that every generated table is valid. Examples show that our methods can be applied to make conditional inference on zero-one and contingency tables, and are more efficient than other existing Monte Carlo algorithms.     

Strategic and operational decisions in restaurant revenue management

The paper addresses restaurant revenue management from both a strategic and an operational point of view. Strategic decisions in restaurants are mainly related to defining the most profitable combination of tables that will constitute the restaurant. We propose new formulations of the so-called “Tables Mix Problem” by taking into account several features of the real setting. We compare the proposed models in a computational study showing that restaurants, with the capacity of managing tables as renewable resources and of combining different-sized tables, can improve expected revenue performances. Operational decisions are mainly concerned with the more profitable assignment of tables to customers. Indeed, the “Parties Mix Problem” consists of deciding on accepting or denying a booking request from different groups of customers, with the aim of maximizing the total expected revenue. A dynamic formulation of the “Parties Mix Problem” is presented together with a linear programming approximation, whose solutions can be used to define capacity control policies based on booking limits and bid prices. Computational results compare the proposed policies and show that they lead to higher revenues than the traditional strategies used to support decision makers.     

在粘性流体中船行波的速度场

从Navier-Stokes方程出发,导得了水上运动物体船行波的波高和水平速度二重积分的表达式.其次采用Lighthill两步法将上述的积分表达式化为代数表达式.与海水作为理想流体所得的结果相比,消除或减弱了原有的奇性,提高了船行波的数字资料的精度.     

Exact Cumulant Calculations for Pearson X2 and Zelterman Statistics for r-Way Contingency Tables

Abstract

We present a computer algebra procedure that calculates exact cumulants for Pearson X ² and Zelterman statistics for r-way contingency tables. The algorithm is an example of how an overwhelming algebraic problem can be solved neatly through computer implementation by emulating tactics that one uses by hand. For inference purposes the cumulants may be used to assess chi-square approximations or to improve this approximation via Edgeworth expansions. Edgeworth approximations are compared to the computerintensive techniques of Mehta and Patel that provide exact and arbitrarily close results. Comparisons to approximations that utilize the gamma distribution (Mielke and Berry) are also made.     

Exact and heuristic methods for cell suppression in multi-dimensional linked tables

The increasing demand for information, coupled with the increasing capability of computer systems, has compelled information providers to reassess their procedures for preventing disclosure of confidential information. This paper considers the problem of protecting an unpublished, sensitive table by suppressing cells in related, published tables. A conventional integer programming technique for two-dimensional tables is extended to find an optimal suppression set for the public tables. This can be used to protect the confidentiality of sensitive data in three- and higher-dimensional tables. More importantly, heuristics that are intimately related to the structure of the problem are also presented to mitigate the computational difficulty of the integer program. An example is drawn from healthcare management. Data tables are randomly generated to assess the computational time/space restrictions of the IP model, and to evaluate the heuristics.     

Invariant imbedding,iterative linearization,and multistage countercurrent processes. VII. Distillation column at minimum reflux and nonlinear boundary value problems

The concept of treating multicomponent distillation problems as nonlinear boundary value problems in difference equations is used to solve columns at minimum reflux. Various computational algorithms are formulated based on the choice of different unknown variables and different boundary conditions. To show the quadratic convergence some typical algorithms are illustrated by numerical examples. It is shown that using very rough initial approximations or starting values, four to five digit accuracy is obtained in five to seven iterations.