text:
# Change-Point Detection on Hierarchical Circadian Models

This paper addresses the problem of change-point detection on sequences of high-dimensional and heterogeneous observations, which also possess a periodic temporal structure. Due to the dimensionality problem, when the time between change-points is on the order of the dimension of the model parameters, drifts in the underlying distribution can be misidentified as changes. To overcome this limitation we assume that the observations lie in a lower dimensional manifold that admits a latent variable representation. In particular, we propose a hierarchical model that is computationally feasible, widely applicable to heterogeneous data and robust to missing instances. Additionally, to deal with the observations' periodic dependencies, we employ a circadian model where the data periodicity is captured by non-stationary covariance functions. We validate the proposed technique on synthetic examples and we demonstrate its utility in the detection of changes for human behavior characterization.

• 10 publications
• 7 publications
• 17 publications
07/24/2020

### Multinomial Sampling for Hierarchical Change-Point Detection

Bayesian change-point detection, together with latent variable models, a...
10/22/2019

### Continual Learning for Infinite Hierarchical Change-Point Detection

Change-point detection (CPD) aims to locate abrupt transitions in the ge...
08/24/2012

### Changepoint detection for high-dimensional time series with missing data

This paper describes a novel approach to change-point detection when the...
11/18/2020

### Detecting Hierarchical Changes in Latent Variable Models

This paper addresses the issue of detecting hierarchical changes in late...
09/25/2018

### Optimal Change Point Detection and Localization in Sparse Dynamic Networks

We study the problem of change point detection and localization in dynam...
07/05/2019

### An Approximate Bayesian Approach to Surprise-Based Learning

Surprise-based learning allows agents to adapt quickly in non-stationary...
12/05/2021

### Another look at synthetic-type control charts

During the last two decades, in statistical process monitoring plentiful...

## Code Repositories

### HierCPD

Hierarchical Change-Point Detection

## 1 Introduction

Change-point detection (CPD) consists in locating abrupt transitions in the generative model of a set of observations. This problem has been long studied and appears in a vast amount of real-world scenarios such as finance (Andersson et al., 2006; Berkes et al., 2004), social networks (Raginsky et al., 2012; Krishnamurthy, 2012), control (Lai, 1995) or behavioral sciences (Park et al., 2017)

, to name a few. Regarding the type of data to be modeled, the general assumption is to consider low-dimensional and homogenous datasets where observations are also assumed to be independent and identically distributed (i.i.d.). However, in many current applications the problem becomes much more challenging because the data is usually high-dimensional and heterogeneous, that is, we observe a mix of continuous, categorical, binary, or discrete variables. The reason is that high-dimensional and heterogeneous observations result in more complicated pre-change and post-change distributions, which need to be estimated (explicitly or implicitly) to identify change points.

The CPD problem becomes even more difficult when the observations deviate from the i.i.d. assumption, that is, when they present some temporal structure. Concretely, this work focuses on data with periodic temporal structure. This particular structure appears in scenarios dealing with humans. Since we are strictly conditioned by 24-hours periods, almost any data generated by humans will present such underlying periodicities, which are related to the circadian rhythm in human behavior (Pentland and Liu, 1999; Eagle and Pentland, 2009).

Additionally, the CPD problem is also difficult because we have to deal with online data streams. Many methods proposed in the literature focus on the segmentation of a complete time-series in a fixed number of segments. This differs from the inference and estimation in streaming datasets because they need to be incrementally updated in real-time (as new input data comes in). This issue is particularly important for high-dimensional signals due to memory and computational costs, which cannot be handled easily with standard batch methods. Another challenge appears when sequences are incomplete or cannot be fully observed. In those cases, the first step is to obtain accurate estimates of the missing values in order to improve the detection performance.

The limited applicability of state-of-art methods to the aforementioned problems motivates this work, where we present a novel solution for performing change-point detection in the presence of such problems. Our model is robust to missing data and able to detect changes in heterogeneous and high-dimensional data with periodic temporal structure. Inspired in

Adams and MacKay (2007), we propose a generalization thereof that considers a latent-variable model, which addresses the high dimensionality and heterogeneity of the observations, as well as the periodic temporal structure. The main contribution of this work is to introduce a hierarchy in the underlying probabilistic model of the detector, which admits multiple heterogeneities, high dimensionality and periodic dependencies at several time scales. To the best of our knowledge, these problems have not been treated together by any change-point detection technique.

### 1.1 Related Work

Typical approaches to change-point detection focus on batch settings (Fearnhead, 2006; Harchaoui et al., 2009), where the number of changes is often unknown. In contrast, online methods were also introduced via particle filtering models (Fearnhead and Liu, 2007) and the Bayesian Online CPD algorithm (BOCPD) (Adams and MacKay, 2007). Both works infer the location of change points for univariate time series using maximum-a-posteriori (MAP) estimation. A different approach is developed in Li et al. (2015), where the changes are detected for sequences of samples whose time horizon can be either fixed or not.

There has been a considerable effort to estimate change points on different domains. For example, Höhle (2010) introduced an online cumulative sum detector that finds changes on categorical time series. Other approaches are able to model multivariate real data using undirected Gaussian graphical models (GGMs) (Xuan and Murphy, 2007) or mixture models (Alippi et al., 2015; Kuncheva, 2013) together with log-likelihood ratios or divergences. Following the Bayesian perspective, several extensions of the BOCPD have been developed, including adaptative sequential methods (Turner et al., 2009) or the Gaussian Process CPD model (Saatçi et al., 2010). This last work extends the BOCPD algorithm to locate change points from observations with arbitrary temporal structure. Additionally, unlike previous approaches, the non-exponential CPD model (Turner et al., 2013)

explored applications to new families of distributions, where computing posterior probabilities is intractable and variational inference is therefore required. However, there is a lack of methods that account for change-point detection on heterogeneous datasets where observations may contain several statistical data types.

Besides the heterogeneity problem, there is another key challenge in the state-of-art to scale up CPD methods for high-dimensional data, which has not been considered much in the past. One exception is the work of Xie et al. (2013), which approaches the problem by considering that the data belongs to a low-dimensional manifold embedded in some high-dimensional ambient space. This idea is similar to our approach since it reduces the complexity problem by focusing the change-point analysis to some latent space.

## 2 Change-Point Detection on Hierarchical Models

Based on Adams and MacKay (2007), we consider that the sequence of heterogeneous and high-dimensional observations, , may be divided into non-overlapping partitions separated by change points. We assume that the data within each partition is independent and identically distributed (i.i.d.) for some distribution . We also define the run-length as the number of time steps since the last change point appeared.

The objective of the BOCPD method is to perform the recursive estimation of . However, when the time between change points becomes of the order of magnitude (or less) of the number of the model parameters, the algorithm is unable to accumulate enough probability mass on low values of . This causes that drifts in the underlying distribution can be misidentified as changes. To overcome this limitation, we further assume that even if the data is high-dimensional, it belongs to a low-dimensional manifold, admitting a latent variable model of the form

 p(xt)=∫p(xt|zt)p(zt)dzt, (1)

where

is a vector of latent variables associated with the observation

. For the time being, we consider that is fixed and known a priori. Even for this latent variable model, we are still interested in the posterior , and we therefore need to extend the recursive estimation to account for the sequence of latent variable vectors,

. To compute this posterior distribution, we start with the joint distribution

, where is the vector of unknown parameters that modulates the distribution of the latent variables. From the joint distribution, may be directly obtained as

 p(rt|X1:t)=p(rt,X1:t)∑rtp(rt,X1:t), (2)

where

 p(rt,X1:t)=∫∫p(rt,Z1:t,X1:t,θt) dθtdZ1:t. (3)

This approach can be involved, mainly due to the integrals in (3), and also requires some manipulations to achieve a recursive expression. The first step is to factorize the joint distribution as

 p(rt,Z1:t,X1:t,θt)=p(X1:t|Z1:t)p(rt,Z1:t,θt), (4)

where we have exploited the assumption that is fixed and known a priori. Now, we continue by marginalizing out the parameters as

 (5)

where

 p(rt,Z1:t)=∫p(rt,Z1:t,θt) dθt. (6)

The recursive nature of the algorithm is a consequence of the factorization (see Appendix A)

 p(rt,Z1:t,θt)=∑rt−1p(rt|rt−1)p(zt|θt)p(θt|rt−1,Z(r)1:t−1)p(rt−1,Z1:t−1), (7)

where is the likelihood of the latent variables and denotes the subset of latent variables for a given partition (Adams and MacKay, 2007). Moreover, the last term in right-hand side of (7) can be obtained by marginalizing over the previous likelihood parameters, that is,

 p(rt−1,Z1:t−1)=∫p(rt−1,Z1:t−1,θt−1)dθt−1, (8)

and the prior of conditioned to , also known as the change-point prior, is given by

 p(rt|rt−1)={H(rt−1+1),rt=0,1−H(rt−1+1),rt=rt−1+1. (9)

Here, is the hazard

function, which we take to be constant with a given time-scale hyperparameter

. Finally, is the posterior of the parameters at time given the previous run-length and the corresponding partition of the latent variables .

Plugging now (7) into (6), the probability becomes

 p(rt,Z1:t)=∑rt−1p(rt|rt−1)π(r)tp(rt−1,Z1:t−1), (10)

where the predictive posterior (Adams and MacKay, 2007; Turner et al., 2009) is given by

 π(r)t=p(zt|rt−1,Z(r)1:t−1)=∫p(zt|θt)p(θt|rt−1,Z(r)1:t−1)dθt. (11)

So far, we have obtained a recursive expression, but we now face the first problem due to the marginalization. Concretely, the exact evaluation of is often intractable for non-Gaussian likelihoods and may require numerical solutions or approximate inference. This issue will be addressed later in Section 2.3.

The marginalization over the latent variables also poses a major problem. Additionally, the dimension of the latent space, and as a consequence that of the parameters , raises two issues. First, as we have already stated, the detector’s performance directly depends on this dimension and, second, the computation complexity of (11) also varies. Hence, we propose to use a simple latent class model, where the latent variables are given by a set of discrete values , with being the number of classes. Each observable object has therefore a single representation , which indicates the class where it belongs to. In practice, this means that we now need to compute , where is a univariate sequence of latent class indicators. This selection yields a (relatively) simpler marginalization and, since the latent variables are just class indicators, the parameter space is greatly reduced.

Based on this selection for the latent variable model, (3) becomes

 p(rt,X1:t)=∑z1:tp(rt,z1:t,X1:t)=∑rt−1p(rt|rt−1)∑ztp(xt|zt)∑z1:t−1ψ(r)t, (12)

where

 ψ(r)t=p(zt|rt−1,z(r)1:t−1)p(rt−1,z1:t−1)p(X1:t−1|z1:t−1), (13)

and we have factored

 p(X1:t|z1:t)=p(xt|zt)p(X1:t−1|z1:t−1). (14)

The values represent a function parametrized at each time step by all previous latent classes for a given run-length . Due to the recursive dependence in (12), marginalizing this whole function results in a combinatorial problem that can be computationally challenging. Concretely, for some sequence of length and with classes, the evaluation of requires operations. Thus, despite (12) provides certain advantage with respect to (3), it may not be possible to compute. This problem is further simplified next. Finally, Figure 1 depicts the proposed hierarchical model.

### 2.1 Simplified Hierarchical Models

We have shown how the computational complexity of the hierarchical model grows exponentially as the signal length, , and the number of categories, , increase, which becomes prohibitive very quickly. The main factor of this computationally complexity is the marginalization of , since it requires summing over all combinations of the latent classes . To overcome this issue, we simplify the previous model by considering alternative strategies. When dealing with latent variables, if collapsing the entire latent domain is too costly, we can directly observe it. That is, we may explicitly observe the values taken by the class indicators , which before were hidden. This sort of observation model has been previously explored by Nazábal et al. (2016)

for the combination of classifiers and it offers several ways to overcome computational costly operations.

#### 2.1.1 Full Posterior Observation

As a first approximation to the hierarchical model, we can use the full posterior probability as the input observation to the change-point detector. If we assume that the distribution over the complete sequence has been previously inferred (See Section 3

), we may take these probabilities as random variables similarly to

Nazábal et al. (2016). Thus, the new observations are , with since . Here, denotes the -dimensional simplex.

The main advantage of this approach is that even if the true classes are unknown, we can detect change points directly from the full posterior probability, which avoids the marginalization of the entire latent sequence. In particular, we show how this form allows to perform reliable detections similarly to the original hierarchical model in Section 2.3. The graphical representation of the posterior observation model can be seen in Figure 2.

#### 2.1.2 Point Estimate Observation

For the scenarios where the above approach is still too computationally demanding, another option appears if we are able to obtain good point estimates, , of the class indicators, . We can use them as an accurate approximation of the latent sequence instead of marginalizing . To adapt the hierarchical model to this new observed latent variables, we take the set of point estimates also as an input sequence to the detector. Note that we further assume the likelihood to be , so we are directly modeling changes on the observed point-estimates. In particular, we compute the point estimates using the maximum a posteriori criterion. That is . In practice, to infer the class posterior distribution , we will use the circadian model presented in Section 3.

### 2.2 Missing Temporal Data

Another important contribution of this work is that the proposed method is able to handle missing data. Concretely, the missing observations follow the model completely at random (MCAR) (Rubin, 1976), and are denoted by . Moreover, the samples that are fully observed are . Dividing the observations in two sets also translates to the sequence of latent variables, which are divided in lost observations , where all components of are missing, and observed variables that correspond to . The case where only some components of are missing is addressed in Section 3 from a different perspective.

For the missing latent variables, following a fully Bayesian approach, we marginalize them out in our hierarchical model. The corresponding predictive probability is therefore reduced to . The main advantage of this marginalization is that the detection algorithm is able to compute probabilities even when is missing. Moreover, the recursiveness remains unaltered since the conditional change-point prior, , is always evaluated sequentially. That is, the uncertainty is still propagated forwards as (6) becomes

 p(rt,Z1:t)=∑rt−1p(rt−1,Z1:t−1)p(rt|rt−1). (15)

This approach for incomplete sequences presents good performance if the missing entries do not appear as long bursts. If that were the case, the lack of randomness induced by the missing data may ruin the estimation of change points since would be computed from very old data.

In Figure 3 we compare the simplified detection model, the PEO model, for both complete and incomplete data sequences. First, this figure shows the MAP estimates of for the complete sequence (top row) and the incomplete one (middle row). Additionally, in the bottom row we plot the MAP estimate of for the cases of missing and non-missing data, as well as the ground truth. As can be seen, the performance with missing data is almost identical to the case of non-missing data.

### 2.3 Inference

In this section, we describe the inference procedures for the two simplified hierarchical models (see FPO and PEO in Figure 2).

#### 2.3.1 Approximate Inference for Full Posterior Observations

Under this model the likelihood function is and we take it as a Dirichlet distribution. Thus, our objective is to find , for which the hierarchical model described before must be reformulated, as well as the recursiveness in (7), which needs to be updated to accept the new sequence of observed latent probabilities . This is equivalent to using the BOCPD algorithm with inputs . As we will see later, conjugacy is unavailable in this case and, to simplify the inference process, we decompose the natural parameter of the Dirichlet distribution as

with inverse variance

and mean . This decomposition allows us to choose a Gamma prior for and a Dirichlet one with single natural parameter for the mean . Under this construction, we write the probability model as

 ~zt∼Dir(η,λ), (16)

where

 η ∼Ga(κ,ν), λ ∼Dir(β), (17)

with and .

We now need to obtain in a similar way as in (2). Hence, it is necessary to compute the predictive integral , which is given by an expression equivalent to (11). To compute this integral, we need , which reads as

 p(ηt,λt|rt−1,~Z(r)1:t−1)∝p(ηt)p(λt)rt−1∏τ=1p(~zτ|ηt,λt)=Ga(ηt|κ,ν)Dir(λt|β)rt−1∏τ=1Dir(~zτ|ηt,λt), (18)

where we have used the prior distributions defined above and considered the hyperparameters and fixed. Thus, the predictive integral becomes

 p(~zt|rt−1,~Z(r)1:t−1)=∫p(~zt|ηt,λt)p(ηt,λt|rt−1,~Z(r)1:t−1)dηtdλt. (19)

However, as we already pointed out, this integral is analytically intractable. Instead, we propose to solve it via Markov chain Monte Carlo (MCMC) methods, yielding

 p(~zt|rt−1,~Z(r)1:t−1)≈1SS∑s=1p(~zt|ηs,λs), (20)

where and are the th sample of and , with being the total number of samples. In particular, we use a Gibbs sampler to draw realizations from . The equations for the conditional probabilities are

 p(ηt|rt−1,~Z(r)1:t−1,λs−1t)∝p(ηt)p(~Z(r)1:t−1|rt−1,ηs−1t,λs−1t)=Ga(ηt|κ,ν)rt−1∏τ=1Dir(~zτ|ηs−1t,λs−1t), (21)

and

 p(λt|rt−1,~Z(r)1:t−1,ηs−1t)∝p(λt)p(~Z(r)1:t−1|rt−1,ηs−1t,λs−1t)=Dir(λt|β)rt−1∏τ=1Dir(~zτ|ηs−1t,λs−1t), (22)

where and are the realizations drawn in the previous iteration of the Gibbs sampler. Moreover, we propose to use the Gibbs-within-Metropolis Hastings sampler presented in Martino et al. (2015, 2018) since there is not direct way to get samples from the conditional distributions in (21) and (22). The main idea is to use the random-walk (RW) Metropolis-Hastings (MH) algorithm (Martino and Elvira, 2017) to generate samples from (22) since the distribution becomes very narrow when the number of latent classes, , is large. On the other hand, for the conditional in (21), it is possible to use a standard MH sampler with a Gamma proposal.

The complete change-point detection algorithm for the FPO simplified model, including the Gibbs sampler, is summarized in Algorithm 1.

#### 2.3.2 Exact Inference for Observed Point Estimates

To perform change-point detection for the second simplified model, we choose the likelihood function to be a categorical distribution with natural parameter . Similarly to the previous strategy, we place a Dirichlet prior on but with a single hyperparameter , that is,

 z⋆t∼Cat(π),π∼Dir(γ),

where and . Based on these priors, the predictive probabilities may be computed in closed form, which provides a significant reduction in the computational complexity and results in a simple method (See Algorithm 2). Actually, the simplified model is the most effective one in terms of computational cost, while at the same time the performance degradation is minimal. This is illustrated in Figure 4. Concretely, this figure shows the posterior probabilities of the latent variable (top row), the MAP estimates (middle row), and the outputs of the two simplified algorithms, as well as the ground truth. As can be seen in this example, the PEO algorithm detects the same change points, just with a slightly larger delay, but with a reduced computational complexity. The computational cost of the sampler also becomes prohibitive when the dimension of the latent space is large.

A final comment is in order. For the cases where is partially observed (e.g., only a few components of are lost), we are still able to compute the probabilities from the latent model, that is, the simplified models can still be used. Note that this differs from the previous scenario where the entire observation is missing. In this work, we assume that both types of incomplete values may appear for any dataset where we want to perform change-point detection. More details about the inference under missing entries on the set of observations are given in Section 3.

This section studies how to embed heterogeneous models into the hierarchical BOCPD technique presented before, as well as to handle periodic temporal structures. Concretely, it will become clear that this step addresses the issues regarding the heterogeneity and the unknown temporal structures of the data. We pay special attention to the application on human behavior characterization, where a ubiquitous circadian periodicity (24 hours) underlies every observation, but the ideas are valid for any dataset with known periodicity. In this context, there exists significant work related to capturing such circadian rhythms at different scales in time series. For example, its application to gene expression modeling (Hensman et al., 2013; Durrande et al., 2016) aims to identify the periodic dynamic cycles of cellular mechanisms in nature, a key point for the understanding of their hidden correlations.

To address all periodic dependencies, we shall arrange the data such that each sample for a given time step corresponds to the subset of observations in one period. Moreover, we allow our model to work with heterogenous objects by simply stacking observations from different statistical types on larger vectors , with being the number of heterogeneous data types. This essentially means that the sequence of observations summarizes consecutive periods of different heterogeneous measurements. Thus, for the description of one day, , we propose a heterogeneous mixture model for the likelihood of the form

 p(xt|zt,{ϕ1k,…,ϕMk}Kk=1)=K∏k=1M∏j=1p(xjt|ϕjk)I{zt=k}, (23)

which is formed by components, each one with its own parameters for every type of data with a given likelihood function , and the latent variables indicating which component is active. As can be seen in (23), we assume that given the class and the parameters, the different types observations, are independent. This representation is illustrated in Figure 5.

### 3.1 Circadian Gaussian-Bernoulli Mixture Model

Among heterogeneous statistical data types that may be incorporated to the daily representation , we consider two representative cases. We assume that each observation is composed by binary and real values, that is, where and . Here, denotes the dimensionality of each kind of observation and is given by a function of the period. For instance, if each component of represents the traveled distance during every hour, , which corresponds to one day, the period induced by the circadian rhythm.

As an example, in the following we focus on two types of observations, but the method is easily extended to more types of observations. Specifically, for the application that we have in mind in this paper, we propose to choose the composed likelihood

to be a mixture of Bernoulli and multivariate Gaussian distributions, that is,

 p(xt|zt=k,{ϕk}Kk=1)=p(xbint,xrealt|ϕk)=Ber(x%bint|μk)N(xrealt|0,Kk+D), (24)

where is the set of likelihood parameters for each latent class value . Note that we are exploiting the conditional independence of and to factorize across the two types of data. Here, are the means of the Bernoulli variables, is a common diagonal matrix to all latent clases, which is given by with , and is a positive-definite covariance matrix that corresponds to class . It is important to point out that the diagonal matrix

provides some heteroscedasticity to the model since we are assuming that the noise may vary within time inputs.

To capture the periodic (circadian) feature of , we employ a periodic covariance function, similar to the works in Durrande et al. (2016) and Solin and Särkkä (2014). The covariance matrix is therefore generated by a non-stationary periodic kernel, i.e., , where the time is assumed to be equally spaced (e.g, ). Further details about this function are provided in the following. Moreover, to obtain interesting insights, we propose that the distribution is generated using a hierarchy similarly to Hensman et al. (2013, 2015). Concretely, the mean is drawn from a zero-mean Gaussian, which yields

 f ∼N(0,Kk), xrealt|f ∼N(f,D). (25)

Note that the computation of can be avoided by marginalizing it out, and therefore, both expressions would be reduced to .

Following the standard approach used in mixture models, we need to compute the complete likelihood, which includes the prior probability on latent class indicators. By defining the prior distribution on class assignments

, (e.g., ), the complete likelihood at time is

 p(xt,zt=k|{ϕk}Kk=1)=p(zt=k)p(xt|zt=k,ϕk)=πkp(xt|ϕk).

Taking into account that observations are conditionally i.i.d., the complete joint log-likelihood becomes

 Lz,ϕ=logp(X1:t,z1:t|{ϕk,πk}Kk=1)=T∑t=1K∑k=1I{zt=k}logπk+T∑t=1K∑k=1I{zt=k}logp(xbint|μk)+T∑t=1K∑k=1I{zt=k}logp(xrealt|Kk,D). (26)

One key point of this circadian model is that if we needed to take observations at non-uniformly separated inputs , this approach would accept different for each in a straightforward manner.

### 3.2 Periodic Non-stationary Covariance Functions

The proposed model captures the circadian feature of data for each class through the temporal embedding and the periodic covariance functions , which must be non-stationary in our case. One possible solution to achieve non-stationarity in kernels is using an input-dependent mapping similar to the one used in Heinonen et al. (2016). Here, we have , where is a stationary periodic covariance function associated to class . Concretely, we take the periodic version of the exponential kernel (MacKay, 1998), which is given by

 ~kk(t−t′)=σ2akexp(−2sin2(π(|t−t′|/D)ℓ2k), (27)

and for , we use a squared Fourier series of order , with . This constraint imposes a limit on the smoothness and avoids overfitting. Thus, is

 sk(t)=(ak,02+C∑c=1[ak,ccos(2πcDt)+bk,csin(2πcDt)])2, (28)

where and are Fourier coefficients that parametrize the covariance matrix of the class, , together with the parameters of the exponential kernel, and .

To sum up, it is important to note that the defined positive function

allows multimodality along time. Moreover, we are simultaneously modeling the correlation among daily hours, which is presumed to be non-stationary, and, at the same time, capturing the individual variance of data along different moments of the period. This is confirmed by the experimental results presented in Section

4.

### 3.3 EM Algorithm for Heterogeneous Circadian Models with Missing Data

In this section we present an inference technique for the model described above. In particular, given the model and the complete log-likelihood in (26), we need to infer the assignments and the set of model parameters and hyperparameters , with .

Obtaining maximum likelihood estimates of our Gaussian-Bernoulli mixture-model parameters under heterogeneous likelihoods can be done through the expectation-maximization (EM) algorithm

(Dempster et al., 1977). However, there is a slight difference in our model. While the expectation step is computed from the complete mixture distribution, in the maximization step, it is possible to factorize and therefore to estimate the parameters of the Bernoulli and Gaussian distributions separately. This is a key point of the inference process, since as long as we introduce new likelihoods to the model, getting uncertainty measures about parameters will be always a set of independent tasks. Additionally, one important matter of using the EM algorithm here is that it allows us to handle missing components in any observation (Ghahramani and Jordan, 1994).

As previously mentioned, rather than dealing with sequences where we may find complete missing observations, sometimes we have to deal with just a few lost features, i.e., only a few components of are missing, making the vector incomplete. The proposed technique estimates the probabilities even if is only partially observed. Hence, we are interested in adapting the mixture model for dealing with missing data following a similar approach to Ghahramani and Jordan (1994), which computes expectations not only over latent variables but over missing values.

Concretely, the algorithm iterates between the following steps

 E-step: compute Q=Ez1:t,Xm1:t[Lz,ϕ] M-step: maximize Q w.r.t. ak,bk,σak,ℓk,σ maximize Q w.r.t. μ,π

where

denotes the matrix that collects the missing values of every observation. It is important to point out that there are no closed form expressions for the maximization w.r.t. the parameters of the Gaussian distribution. Thus, we use the conjugate gradient (CG) ascent method (See Appendix C). Finally, contrary to standard EM techniques, the proposed approach must combine closed-form estimators for the Bernoulli distribution parameters and numerical optimization for the hyperparameters of the periodic covariance function. Since the latter problem is highly non-convex, several initializations of the hyperparameters are required achieve a good (local) maximum.

## 4 Experiments

In this section, we demonstrate that our approach is capable of estimating change points properly in two different scenarios (one synthetic and one real) with heterogeneous datasets and high-dimensional observations in presence of strong periodic dependencies between samples. Concretely, only the algorithm based on the PEO model is used since the computational complexities of the full hierarchical approach and the FPO model are prohibitive.

### 4.1 Synthetic data

In our first experiment, we want to validate our hierarchical change-point detector on the embedded circadian model for a set of controlled synthetic data. Setting a categorical distribution as the likelihood distribution, that is, using the PEO simplified model, we generate a discrete sequence with instances and categorical values (future assignments) where four change points were introduced. Notice that this means that the sequence is divided into five partitions. Then, the generative parameters for each partition are generated by sampling where we fixed .

The resulting sequence corresponds to the latent classes in the corresponding hierarchical structure. Consequently, we generate pairs of multivariate Bernoulli-Gaussian samples where the covariance matrices are given by the non-stationary periodic kernel described in Section 3.2 and also considering a random selection of hyperparameters.

Note that, in our experiment we only observe the given stream of binary and real observations, never the sequence of latent classes . Then, assuming the Gaussian-Bernoulli mixture model from Section 3.1, we infer the posterior probabilities over class assignments by applying the EM algorithm previously described. For experimental purposes, we have truncated the number of Fourier coefficients to , while the data was generated with .

Once the resulting sequence of posterior probability vectors was obtained, we translated it into point-estimates by using a MAP estimator. Again, using the PEO simplified model, we performed hierarchical change-point detection as in Algorithm 2. We run the whole process for several classes in the Gaussian-Bernoulli mixture model and multiple initializations. Figure 6 shows how our approach detects change-points depending on the number of latent classes selected. Note that, as the number of categories decreases, we find a bit more delay mainly in the last two partitions. Our hypothesis is that as long as the circadian model gets larger amounts of latent classes (i.e., it is more representative), the change-point detection can differ better between adjacent partitions.

The interpretability of change-point detection diagrams is a key point of this paper (see Figures 3, 4 and 6). Usually, we represent the run length with highest probability at each time step . The resulting diagram shows ever-increasing run lengths while change-points are not detected. Note that ground truth plots always represent the exact instant of time when the change occurs. This is generally difficult to be detected without any sort of delay (i.e., a few samples from the post-change sequence must be observed to update the new distribution and then compare with the pre-change distribution). The usual case where this delay could be mostly reduced is given by the predictive probabilities in (11), that is, under extremely abrupt changing conditions, a new sample that does not fit with the old distribution (i.e. probability ), will give a very low probability and therefore will force the run-length to be zero, , immediately. In most cases, this does not occur so we look to the lowest value taken by that is usually a bit higher than zero. For example, in the last change-point detected in Figure 6, the maximum probability of at indicates , that is, there was a change-point 20 time steps before, at .

### 4.2 Anomalous Human Behavior

In this experiment, we evaluate our model on real data for medical applications. Since our work is highly motivated by the problem of change-point detection for personalized medicine, it is important to mention why detecting abnormal changes is a key milestone for the future of modern psychiatry.

#### 4.2.1 Change-point Detection in Psychiatry

Nearly all patients with one of the most prevalent mental health disorders such as schizophrenia or chronic depression are likely to suffer some sort of relapse in the next five years after their first episode. Despite the fact that significant early indicators may appear before an abrupt relapse, when recognizable symptoms are already present, it is usually too late for any preventive treatment.

The majority of these previous signs and triggering effects can be identified by continually monitoring changes in the patient’s behavior. Here, we refer to human behavior as the set of routines and patterns that are persistent during our daily life. In Eagle and Pentland (2009), it was demonstrated how these behavioral patterns are projected in the set of signals that we generate every day (i.e., mobility data, phone communications and logs of social interactions, etc.) and are mainly recognizable through the appearance of circadian features and periodicities. In this sense, the ubiquitous condition of smartphones and wearables, whose recording and memory capabilities are able to perform continuous monitoring of the aforementioned domains, opened a new window for analysing all these sources of information in chronic patients without the need of direct medical interventions. Our primary goal is to provide a robust solution to this paradigm by applying change-point detection on behavioral data obtained from monitored psychiatric patients.

#### 4.2.2 Mobility metrics

In our experiment, we used data which consists of location traces (latitude-longitude) recorded via smartphone during 275 consecutive days. It contains a bit more than 100,000 instances that corresponds to the user’s GPS coordinates every 3 minutes on average. We investigated how to obtain reliable metrics from these traces. Based on Canzian and Musolesi (2015), we considered two types of metrics: 1) a real-valued signal of the log-distance travelled per hour and 2) daily binary vectors of presence or absence at home.

The preprocessing step was particularly different for each one of the metrics. In the first case, we collected all location traces separately for every hour and every day. Once this was done, we calculated the approximated distance wandered between consecutive latitude-longitude pairs. It is important to remark that if the the maximum time without any location point (30 minutes) was exceeded for some hour, the total distance was considered as a missing value. For the binary case, we preprocessed all the locations in order to estimate patients home location, that is, the most usual latitude-longitude pair during noctural hours. To decide whether a patient was or not at home, we established a maximum distance range of 50 m. When one or more location traces show a relative distance to the estimated home position equal or lower than this range, then we assume that at this hour the patient was at home. For the hours with no location traces, we considered them also as missing data.

After the preprocessing step, we can see both signals in Figure 7 (upper plots), which correspond to the observations in the circadian model. For the binary metric, we have 24 hours length vectors for each day where at-home (black) and not-at-home (white) indicators are showed in contrast to the missing values (red). Note that it is especially easy to identify patterns and routines in this type of representations (Eagle and Pentland, 2009). An important detail to remark is that missing traces are mainly concentrated around night hours. This may occur when sensors run out of battery during night, which a priori could make sense. Moreover, visualizing segments of diurnal features across the sequence of days is interesting as long as we can infer the routine structure of consecutive working days and weekend periods.

#### 4.2.3 Detection of Behavioral changes

The results of the EM algorithm after observing the sequence of heterogeneous observations is shown in Figure 7. Similarly to the previous synthetic experiment presented in Section 4.1, the main objective is to obtain posterior probabilities . Following the simplied PEO model, we set point-estimates as the sequence of observed latent variables, see third row in Figure 7.

Results using classes, this is, a large number of day profiles, show that the second and fourth profiles are the most frequent. Looking at the detected change points with the PEO simplified model, we can see that abrupt transitions are produced by sudden changes in the proportions of latent classes. The hierarchical detector is capturing that in the first partition, the natural parameters indicate that the fourth and fifth profiles mainly dominate the routine. However, after a small secondary partition given by an unusual combination of classes, the third partition shows a new pattern of behavior where the second profile is the most frequent one.

One of the strengths of the proposed latent model is its ability to identify the 24 hours periodic cycles from the set of mobility metrics, mainly by estimating the Fourier coefficients of the covariance functions for the wandered distance values. In this process, after fitting all hyperparameters in the maximization step during the inference, we are able to reproduce the patterns that describe how a person usually behaves during each type of day. In the left column of Figure 8, we represent the set of (multimodal) periodic functions generated from the squared Fourier series, , for every profile, that is, each latent class . Moreover, we plot in the right-hand side column of the same figure the estimated vectors of probability of the Bernoulli likelihood, i.e., the probability of being at home for every type of day at different hourly frames.

The input dependent mapping can be understood by the reader as a periodic function that models mobility fluctuations during the whole day. That is, we may assume that large values of correspond to patterns with larger displacements and, on the contrary, values near zero mean no mobility at the given hour for that particular profile. We want to remark the interesting connection between resting states (at home) and profiles of wandered distance. Despite the fact that binary observations suffer from extremely high percentages of missing values during nocturnal hours, it is possible to infer if the patient’s mobility variance correspond or not to places near his/her home.

This circadian phenotypes also provide interesting information for psychiatric use. On one hand, the most likely profiles, such as and (see Figure 7, third row), are easily interpreted as routine days, probably working type ones, as can be seen in Figure 8. For instance, Profile 2 has most of its activity at commuting hours. On the other, other profiles, such as or , may be considered as leisure patterns since the activity is distributed more evenly during the day, as shown in Figure 8. This sort of analysis is particularly important because it demonstrates that heterogeneous circadian models are able to capture the circadian cycles of individuals during their daily life.

## 5 Conclusions

In this paper we have proposed a novel generalization of the Bayesian change-point algorithm (Adams and MacKay, 2007) to handle heterogeneous high-dimensional observations with unknown periodic structure. The main contribution is to introduce a hierarchical model for the underlying probabilities of the detector.

Additionally, we present a new probabilistic approach for detecting change-points from sequences with multiple missing values. This solution can be used in any variation of the BOCPD method (Saatçi et al., 2010; Turner et al., 2009, 2013) and is specially useful when using latent variable models. In addition, we include a circadian model that captures the periodic structure of the data, mainly focusing on the circadian rhythm.

The code is publicly available in the repository https://github.com/pmorenoz/HierCPD and it is fully written in Python. Thus, we expect the hierarchical detector to be utilised by researchers to detect change points for any possible latent variable model. In addition, we also include the heterogeneous circadian mixture model as well as the EM inference and the periodic non-stationary covariance functions.

The authors would like to thank Luca Martino for his useful comments and discussion. This work has been partly supported by Ministerio de Economía of Spain under projects: OTOSIS (TEC2013-41718-R), AID (TEC2014-62194-EXP), and the COMONSENS Network (TEC2015-69648-REDC), by the Ministerio de Economía of Spain jointly with the European Commission (ERDF) under projects ADVENTURE (TEC2015-69868-C2-1-R) and CAIMAN (TEC2017-86921-C2-2-R), and by the Comunidad de Madrid under project CASI-CAM-CM (S2013/ICE-2845). The work of P. Moreno-Muñoz has been supported by FPI grant BES-2016-077626.

## Appendix A. Hierarchical BOCPD Algorithm

The recursive decomposition of the joint probability distribution

is based on the original derivation of Adams and MacKay (2007) and can obtained as follows.

The joint distribution can be easily expanded by marginalizing over all values of the previous run length , that is,

 p(rt,Z1:t,X1:t,θt) = ∑rt−1p(rt,rt−1,Z1:t,X1:t,θt) (29) = ∑rt−1p(rt,rt−1,zt,Z1:t−1,xt,X1:t−1,θt),

where we have separated and to simplify the derivation. The last term can be also expressed as

 p(rt,rt−1,zt,Z1:t−1,xt,X1:t−1,θt)=p(rt,zt,xt,θt|rt−1,Z1:t−1,X1:t−1)p(rt−1,z1:t−1,X1:t−1).

where the right-hand side term may be obtained as

 p(rt−1,Z1:t−1,X1:t−1)=∫p(rt−1,Z1:t−1,X1:t−1,θt−1)dθt−1,

with being the factorized joint probability distribution at .

Since the current run length is only conditioned by its previous value , the previous expression can be written down as

 p(rt,z1:t,X1:t,θt)=∑rt−1p(rt|rt−1)p(zt,xt,θt|rt−1,Z1:t−1,X1:t−1)p(rt−1,z1:t−1,X1:t−1),

where the conditional distribution is the change-point prior (see Section 2). Note that useless conditioned variables have been omitted. At the same time, we may decompose

 p(zt,xt,θt|rt−1,Z1:t−1,X1:t−1)=p(xt|zt)p(zt|θt)p(θt|rt−1,Z1:t−1),

where we have taken into account that heterogeneous high-dimensional observations are only conditioned by its latent representation , which is modeled by the likelihood term given the posterior distribution on the parameters.

The resulting recursive expression is

 p(rt,z1:t,X1:t,θt)=∑rt−1p(rt|rt−1)p(xt|zt)p(zt|θt)p(θt|rt−1,Z1:t−1)p(rt−1,z1:t−1,X1:t−1),

and can be calculated sequentially at each time step .

## Appendix B. Heterogeneous Circadian Mixture Model

#### Gaussian Likelihood with Missing Data

The Gaussian distribution requires to handle missing or partial observations in this problem, based on Ghahramani and Jordan (1994), the likelihood is as follows,

 p(xreali|θk)=p(xo,reali,xm,reali|θk)=N(</


text:
for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> MATHEMATICS (Total: 978 journals)     - APPLIED MATHEMATICS (81 journals)    - GEOMETRY AND TOPOLOGY (20 journals)    - MATHEMATICS (723 journals)    - MATHEMATICS (GENERAL) (41 journals)    - NUMERICAL ANALYSIS (22 journals)    - PROBABILITIES AND MATH STATISTICS (91 journals) MATHEMATICS (723 journals)                  1 2 3 4 | Last

1 2 3 4 | Last

 Archive for Mathematical LogicJournal Prestige (SJR): 0.909 Citation Impact (citeScore): 1Number of Followers: 3      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1432-0665 - ISSN (Online) 0933-5846 Published by Springer-Verlag  [2351 journals]
• Some remarks on Baire’s grand theorem
• Authors: Riccardo Camerlo; Jacques Duparc
Pages: 195 - 201
Abstract: We provide a game theoretical proof of the fact that if f is a function from a zero-dimensional Polish space to $$\mathbb N^{\mathbb N}$$ that has a point of continuity when restricted to any non-empty compact subset, then f is of Baire class 1. We use this property of the restrictions to compact sets to give a generalisation of Baire’s grand theorem for functions of any Baire class.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0563-6
Issue No: Vol. 57, No. 3-4 (2018)

• l -Groups C ( X ) in continuous logic
• Authors: Philip Scowcroft
Pages: 239 - 272
Abstract: In the context of continuous logic, this paper axiomatizes both the class $$\mathcal {C}$$ of lattice-ordered groups isomorphic to C(X) for X compact and the subclass $$\mathcal {C}^+$$ of structures existentially closed in $$\mathcal {C}$$ ; shows that the theory of $$\mathcal {C}^+$$ is $$\aleph _0$$ -categorical and admits elimination of quantifiers; establishes a Nullstellensatz for $$\mathcal {C}$$ and $$\mathcal {C}^+$$ ; shows that $$C(X)\in \mathcal {C}$$ has a prime-model extension in $$\mathcal {C}^+$$ just in case X is Boolean; and proves that in a sense relevant to continuous logic, positive formulas admit in $$\mathcal {C}^+$$ elimination of quantifiers to positive formulas.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0566-3
Issue No: Vol. 57, No. 3-4 (2018)

• The subcompleteness of Magidor forcing
• Authors: Gunter Fuchs
Pages: 273 - 284
Abstract: It is shown that the Magidor forcing to collapse the cofinality of a measurable cardinal that carries a length $$\omega _1$$ sequence of normal ultrafilters, increasing in the Mitchell order, to $$\omega _1$$ , is subcomplete.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0568-1
Issue No: Vol. 57, No. 3-4 (2018)

• Countable OD sets of reals belong to the ground model
• Authors: Vladimir Kanovei; Vassily Lyubetsky
Pages: 285 - 298
Abstract: It is true in the Cohen, Solovay-random, dominaning, and Sacks generic extension, that every countable ordinal-definable set of reals belongs to the ground universe. It is true in the Solovay collapse model that every non-empty OD countable set of sets of reals consists of $$\text {OD}$$ elements.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0569-0
Issue No: Vol. 57, No. 3-4 (2018)

• Quasiminimal abstract elementary classes
• Authors: Sebastien Vasey
Pages: 299 - 315
Abstract: We propose the notion of a quasiminimal abstract elementary class (AEC). This is an AEC satisfying four semantic conditions: countable Löwenheim–Skolem–Tarski number, existence of a prime model, closure under intersections, and uniqueness of the generic orbital type over every countable model. We exhibit a correspondence between Zilber’s quasiminimal pregeometry classes and quasiminimal AECs: any quasiminimal pregeometry class induces a quasiminimal AEC (this was known), and for any quasiminimal AEC there is a natural functorial expansion that induces a quasiminimal pregeometry class. We show in particular that the exchange axiom is redundant in Zilber’s definition of a quasiminimal pregeometry class.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0570-7
Issue No: Vol. 57, No. 3-4 (2018)

• On Katětov and Katětov–Blass orders on analytic P-ideals
and Borel ideals
• Authors: Hiroshi Sakai
Pages: 317 - 327
Abstract: Minami–Sakai (Arch Math Logic 55(7–8):883–898, 2016) investigated the cofinal types of the Katětov and the Katětov–Blass orders on the family of all $$F_\sigma$$ ideals. In this paper we discuss these orders on analytic P-ideals and Borel ideals. We prove the following: The family of all analytic P-ideals has the largest element with respect to the Katětov and the Katětov–Blass orders. The family of all Borel ideals is countably upward directed with respect to the Katětov and the Katětov–Blass orders. In the course of the proof of the latter result, we also prove that for any analytic ideal $$\mathcal {I}$$ there is a Borel ideal $$\mathcal {J}$$ with $$\mathcal {I} \subseteq \mathcal {J}$$ .
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0572-5
Issue No: Vol. 57, No. 3-4 (2018)

• Continuous reducibility and dimension of metric spaces
• Authors: Philipp Schlicht
Pages: 329 - 359
Abstract: If (X, d) is a Polish metric space of dimension 0, then by Wadge’s lemma, no more than two Borel subsets of X are incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space (X, d) of positive dimension, there are uncountably many Borel subsets of (X, d) that are pairwise incomparable with respect to continuous reducibility. In general, the reducibility that is given by the collection of continuous functions on a topological space $$(X,\tau )$$ is called the Wadge quasi-order for $$(X,\tau )$$ . As an application of the main result, we show that this quasi-order, restricted to the Borel subsets of a Polish space $$(X,\tau )$$ , is a well-quasiorder if and only if $$(X,\tau )$$ has dimension 0. Moreover, we give further examples of applications of the construction of graph colorings that is used in the proofs.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0571-6
Issue No: Vol. 57, No. 3-4 (2018)

• Expressivity in chain-based modal logics
• Authors: Michel Marti; George Metcalfe
Pages: 361 - 380
Abstract: We investigate the expressivity of many-valued modal logics based on an algebraic structure with a complete linearly ordered lattice reduct. Necessary and sufficient algebraic conditions for admitting a suitable Hennessy–Milner property are established for classes of image-finite and (appropriately defined) modally saturated models. Full characterizations are obtained for many-valued modal logics based on complete BL-chains that are finite or have the real unit interval [0, 1] as a lattice reduct, including Łukasiewicz, Gödel, and product modal logics.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0573-4
Issue No: Vol. 57, No. 3-4 (2018)

• A weak variant of Hindman’s Theorem stronger than Hilbert’s
Theorem
• Authors: Lorenzo Carlucci
Pages: 381 - 389
Abstract: Hirst investigated a natural restriction of Hindman’s Finite Sums Theorem—called Hilbert’s Theorem—and proved it equivalent over $$\mathbf {RCA}_0$$ to the Infinite Pigeonhole Principle for all colors. This gave the first example of a natural restriction of Hindman’s Theorem provably much weaker than Hindman’s Theorem itself. We here introduce another natural restriction of Hindman’s Theorem—which we name the Adjacent Hindman’s Theorem with apartness—and prove it to be provable from Ramsey’s Theorem for pairs and strictly stronger than Hirst’s Hilbert’s Theorem. The lower bound is obtained by a direct combinatorial implication from the Adjacent Hindman’s Theorem with apartness to the Increasing Polarized Ramsey’s Theorem for pairs introduced by Dzhafarov and Hirst. In the Adjacent Hindman’s Theorem homogeneity is required only for finite sums of adjacent elements.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0576-1
Issue No: Vol. 57, No. 3-4 (2018)

• Implicational (semilinear) logics III: completeness properties
• Authors: Petr Cintula; Carles Noguera
Pages: 391 - 420
Abstract: This paper presents an abstract study of completeness properties of non-classical logics with respect to matricial semantics. Given a class of reduced matrix models we define three completeness properties of increasing strength and characterize them in several useful ways. Some of these characterizations hold in absolute generality and others are for logics with generalized implication or disjunction connectives, as considered in the previous papers. Finally, we consider completeness with respect to matrices with a linear dense order and characterize it in terms of an extension property and a syntactical metarule. This is the final part of the investigation started and developed in the papers (Cintula and Noguera in Arch Math Logic 49(4):417–446, 2010; Arch Math Logic 53(3):353–372, 2016).
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0577-0
Issue No: Vol. 57, No. 3-4 (2018)

• Maximal trees
• Authors: Jörg Brendle
Pages: 421 - 428
Abstract: We show that, consistently, there can be maximal subtrees of $$\mathcal{P}(\omega )$$ and $$\mathcal{P}(\omega ) / {\mathrm {fin}}$$ of arbitrary regular uncountable size below the size of the continuum $${\mathfrak c}$$ . We also show that there are no maximal subtrees of $$\mathcal{P}(\omega ) / {\mathrm {fin}}$$ with countable levels. Our results answer several questions of Campero-Arena et al. (Fund Math 234:73–89, 2016).
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0575-2
Issue No: Vol. 57, No. 3-4 (2018)

• Decidability of the AE-theory of the lattice of $${\varPi }_1^0$$ Π 1 0
classes
• Authors: Linda Lawton
Pages: 429 - 451
Abstract: An AE-sentence is a sentence in prenex normal form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. We show that the AE-theory of $$(\mathscr {L}({\varPi }_1^0), \cap , \cup , 0, 1)$$ is decidable by giving a procedure which, for any AE-sentence in the language, determines the truth or falsity of the sentence in our structure.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0564-5
Issue No: Vol. 57, No. 3-4 (2018)

• Scott sentences for certain groups
• Authors: Julia F. Knight; Vikram Saraph
Pages: 453 - 472
Abstract: We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple as possible. We consider finitely generated groups and torsion-free abelian groups of finite rank. For both kinds of groups, the computable ones all have computable $$\varSigma _3$$ Scott sentences. Sometimes we can do better. In fact, the computable finitely generated groups that we have studied all have Scott sentences that are “computable d- $$\varSigma _2$$ ” (the conjunction of a computable $$\varSigma _2$$ sentence and a computable $$\varPi _2$$ sentence). In [9], this was shown for the finitely generated free groups. Here we show it for all finitely generated abelian groups, and for the infinite dihedral group. Among the computable torsion-free abelian groups of finite rank, we focus on those of rank 1. These are exactly the additive subgroups of $$\mathbb {Q}$$ . We show that for some of these groups, the computable $$\varSigma _3$$ Scott sentence is best possible, while for others, there is a computable d- $$\varSigma _2$$ Scott sentence.
PubDate: 2018-05-01
DOI: 10.1007/s00153-017-0578-z
Issue No: Vol. 57, No. 3-4 (2018)

• A model of the generic Vopěnka principle in which the ordinals are
not Mahlo
• Authors: Victoria Gitman; Joel David Hamkins
Abstract: The generic Vopěnka principle, we prove, is relatively consistent with the ordinals being non-Mahlo. Similarly, the generic Vopěnka scheme is relatively consistent with the ordinals being definably non-Mahlo. Indeed, the generic Vopěnka scheme is relatively consistent with the existence of a $$\Delta _2$$ -definable class containing no regular cardinals. In such a model, there can be no $$\Sigma _2$$ -reflecting cardinals and hence also no remarkable cardinals. This latter fact answers negatively a question of Bagaria, Gitman and Schindler.
PubDate: 2018-05-14
DOI: 10.1007/s00153-018-0632-5

• Selfextensional logics with a distributive nearlattice term
• Authors: Luciano J. González
Abstract: We define when a ternary term m of an algebraic language $$\mathcal {L}$$ is called a distributive nearlattice term ( $$\mathrm {DN}$$ -term) of a sentential logic $$\mathcal {S}$$ . Distributive nearlattices are ternary algebras generalising Tarski algebras and distributive lattices. We characterise the selfextensional logics with a $$\mathrm {DN}$$ -term through the interpretation of the DN-term in the algebras of the algebraic counterpart of the logics. We prove that the canonical class of algebras (under the point of view of Algebraic Logic) associated with a selfextensional logic with a $$\mathrm {DN}$$ -term is a variety, and we obtain that the logic is in fact fully selfextensional.
PubDate: 2018-05-11
DOI: 10.1007/s00153-018-0628-1

• A completeness theorem for continuous predicate modal logic
• Authors: Stefano Baratella
Abstract: We study a modal extension of the Continuous First-Order Logic of Ben Yaacov and Pedersen (J Symb Logic 75(1):168–190, 2010). We provide a set of axioms for such an extension. Deduction rules are just Modus Ponens and Necessitation. We prove that our system is sound with respect to a Kripke semantics and, building on Ben Yaacov and Pedersen  (2010), that it satisfies a number of properties similar to those of first-order predicate logic. Then, by means of a canonical model construction, we get that every consistent set of formulas is satisfiable. From the latter result we derive an Approximated Strong Completeness Theorem, in the vein of Continuous Logic, and a Compactness Theorem.
PubDate: 2018-05-10
DOI: 10.1007/s00153-018-0630-7

• The binary expansion and the intermediate value theorem in constructive
reverse mathematics
• Authors: Josef Berger; Hajime Ishihara; Takayuki Kihara; Takako Nemoto
Abstract: We introduce the notion of a convex tree. We show that the binary expansion for real numbers in the unit interval ( $$\mathrm {BE}$$ ) is equivalent to weak König lemma ( $$\mathrm {WKL}$$ ) for trees having at most two nodes at each level, and we prove that the intermediate value theorem is equivalent to $$\mathrm {WKL}$$ for convex trees, in the framework of constructive reverse mathematics.
PubDate: 2018-05-10
DOI: 10.1007/s00153-018-0627-2

• Uniform interpolation and sequent calculi in modal logic
• Authors: Rosalie Iemhoff
Abstract: A method is presented that connects the existence of uniform interpolants to the existence of certain sequent calculi. This method is applied to several modal logics and is shown to cover known results from the literature, such as the existence of uniform interpolants for the modal logic $$\mathsf{K}$$ . New is the result that $$\mathsf{KD}$$ has uniform interpolation. The results imply that for modal logics $$\mathsf{K4}$$ and $$\mathsf{S4}$$ , which are known not to have uniform interpolation, certain sequent calculi cannot exist.
PubDate: 2018-05-10
DOI: 10.1007/s00153-018-0629-0

• An extension of Shelah’s trichotomy theorem
Abstract: Shelah (Algorithms Comb 14:420–459, 1997) develops the theory of $$\mathrm {pcf}_I(A)$$ without the assumption that $$A <\min (A)$$ , going so far as to get generators for every $$\lambda \in \mathrm {pcf}_I(A)$$ under some assumptions on I. Our main theorem is that we can also generalize Shelah’s trichotomy theorem to the same setting. Using this, we present a different proof of the existence of generators for $$\mathrm {pcf}_I(A)$$ which is more in line with the modern exposition. Finally, we discuss some obstacles to further generalizing the classical theory.
PubDate: 2018-05-09
DOI: 10.1007/s00153-018-0631-6

• Sequent calculus for classical logic probabilized
• Authors: Marija Boričić
Abstract: Gentzen’s approach to deductive systems, and Carnap’s and Popper’s treatment of probability in logic were two fruitful ideas that appeared in logic of the mid-twentieth century. By combining these two concepts, the notion of sentence probability, and the deduction relation formalized in the sequent calculus, we introduce the notion of ’probabilized sequent’ $$\Gamma \vdash _a^b\Delta$$ with the intended meaning that “the probability of truthfulness of $$\Gamma \vdash \Delta$$ belongs to the interval [a, b]”. This method makes it possible to define a system of derivations based on ’axioms’ of the form $$\Gamma _i\vdash _{a_i}^{b_i}\Delta _i$$ , obtained as a result of empirical research, and then infer conclusions of the form $$\Gamma \vdash _a^b\Delta$$ . We discuss the consistency, define the models, and prove the soundness and completeness for the defined probabilized sequent calculus.
PubDate: 2018-05-07
DOI: 10.1007/s00153-018-0626-3

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327

Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs

format: plain


text:
# Help to prove the existance of a function

Let $f:X \rightarrow Y$ be a function. Prove that there exists a function $g:Y \rightarrow X$ such that $f \circ g = I_Y$ if and only if $f$ is a surjection.

I need help on proving the following:

$f$ is a surjection $\Rightarrow \exists g:Y \rightarrow X, f \circ g = I_y$

What I've tried:

$f$ is a surjection $\Rightarrow \forall y \in Y, \exists x \in X, f(x)=y$, definition of a surjection

From here, I thought of constructing a function, $g:Y \rightarrow X$, since all $y$s have some preimage, $x \in X$ . But this will not be possible if $f$ is not injective. In that case, the codomain of $g$ will need to be appropriately restricted, so that $y_1=y_2 \Rightarrow g(y_1)=g(y_2)$. But I can't restrict the codomain of $g$ since the conclusion requires the codomain of $g$ to be exactly $X$. I don't know what else to do. Also, is my attempt anywhere near a solution or am I thinking about this problem in a wrong way?

• The codomain is different from the range. $g$ needn't take on ALL values in $X$. So, you pretty much have the solution already. It's perfectly fine to write $g:Y \mapsto X$ even when the range of $g$ is not all of $X$. – StrangerLoop Jul 29 '14 at 15:52
• See Left and right inverses in Inverse function. – Mauro ALLEGRANZA Jul 29 '14 at 15:52
• @MauroALLEGRANZA I see that the wikipedia article says that constructing $g$ in general requires axiom of choice. If I have not studied the axiom of choice, would my attempt be acceptable? – mauna Jul 29 '14 at 16:28
• See the answer to this post. If you are at the "elementary" level of set-theory, I think would be acceptable if you do not mention AC. But at some point in your proof you have to say "... and now I choose an y ...". Be aware of this :) – Mauro ALLEGRANZA Jul 29 '14 at 16:31

This is a consequence of AXIOM OF CHOICE

• Could you clarify what you mean here? "This" could refer to multiple concepts... and explaining how it's a consequence would be best. – apnorton Jul 29 '14 at 16:22
• Besides what anorton said, is there a way to prove it without relying on the Axiom of Choice? The text I am using does not cover it at all so I am wondering if there are alternative answers – mauna Jul 29 '14 at 16:26
• For each $y\in Y$, you can choose an element $x$ in $f^{-1}(\{y\})$ (wish is not empty by hypothesis ), and put $x=g(y)$ – Hamou Jul 29 '14 at 16:27
• "This" = "$f$ is a surjection $\Rightarrow \exists g:Y\to X,f\circ g=I_Y$" – Hamou Jul 29 '14 at 17:11
• thanks. Could you please also explain where the axiom of choice comes into play (like what anorton asked?) – mauna Jul 30 '14 at 1:58


text:
### Electronic Research Archive

2021, Issue 6: 3867-3887. doi: 10.3934/era.2021066

# A class of fourth-order hyperbolic equations with strongly damped and nonlinear logarithmic terms

• Received: 01 June 2021 Revised: 01 July 2021 Published: 07 September 2021
• Primary: 35A01, 35L75; Secondary: 35B40, 35B44

• In this paper, we study a class of hyperbolic equations of the fourth order with strong damping and logarithmic source terms. Firstly, we prove the local existence of the weak solution by using the contraction mapping principle. Secondly, in the potential well framework, the global existence of weak solutions and the energy decay estimate are obtained. Finally, we give the blow up result of the solution at a finite time under the subcritical initial energy.

Citation: Yi Cheng, Ying Chu. A class of fourth-order hyperbolic equations with strongly damped and nonlinear logarithmic terms[J]. Electronic Research Archive, 2021, 29(6): 3867-3887. doi: 10.3934/era.2021066

### Related Papers:

• In this paper, we study a class of hyperbolic equations of the fourth order with strong damping and logarithmic source terms. Firstly, we prove the local existence of the weak solution by using the contraction mapping principle. Secondly, in the potential well framework, the global existence of weak solutions and the energy decay estimate are obtained. Finally, we give the blow up result of the solution at a finite time under the subcritical initial energy.

 [1] The existence and the asymptotic behavior of a plate equation with frictional damping and a logarithmic source term. J. Math. Anal. Appl. (2017) 454: 1114-1128. [2] Existence and a general decay result for a plate equation with nonlinear damping and a logarithmic source term. J. Evol. Equ. (2018) 18: 105-125. [3] An elliptic system with logarithmic nonlinearity. Adv. Nonlinear Anal. (2019) 8: 928-945. [4] Inflationary models with logarithmic potentials. Phys. Rev. D (1995) 52: 5576-5587. [5] K. Bartkowski and P. Górka, One-dimensional Klein-Gordon equation with logarithmic nonlinearities, J. Phys. A, 41 (2008), 355201, 11 pp. doi: 10.1088/1751-8113/41/35/355201 [6] Wave equations with logarithmic nonlinearities. Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. (1975) 23: 461-466. [7] A boundary value problem for fourth-order elastic beam equations. J. Math. Anal. Appl. (2008) 343: 1166-1176. [8] On the Sobolev space of functions with derivative of logarithmic order. Adv. Nonlinear Anal. (2020) 9: 836-849. [9] Équations d'évolution avec non-linéarité logarithmique. Ann. Fac. Sci. Toulouse Math. (1980) 2: 21-51. [10] On some fourth-order semilinear elliptic problems in $R^N$. Nonlinear Anal. (2002) 49: 861-884. [11] Initial boundary value problem for a class of semilinear pseudo-parabolic equations with logarithmic nonlinearity. J. Differential Equations (2015) 258: 4424-4442. [12] Global existence and blow-up of solutions for infinitely degenerate semilinear pseudo-parabolic equations with logarithmic nonlinearity. Discrete Contin. Dyn. Syst. (2019) 39: 1185-1203. [13] Global nonexistence for a semilinear Petrovsky equation. Nonlinear Anal. (2009) 70: 3203-3208. [14] Existence and uniform decay estimates for the fourth order wave equation with nonlinear boundary damping and interior source. Electron. Res. Arch. (2020) 28: 221-261. [15] Q-balls and baryogenesis in the MSSM. Phys. Lett. B (1998) 425: 309-321. [16] L. C. Evans, Partial Differential Equations, Second ed., in: Graduate Studies in Mathematics, vol. 19, 2010. doi: 10.1090/gsm/019 [17] Global solutions and finite time blow up for damped semilinear wave equations. Ann. Inst. H. Poincaré Anal. Non Linéaire (2006) 23: 185-207. [18] Logarithmic Klein-Gordon equation. Acth Physica Polonica B (2009) 40: 59-66. [19] Global existence of weak solutions for a logarithmic wave equation arising from Q-ball dynamics. Bull. Korean Math. Soc. (2013) 50: 275-283. [20] Y. Han, Finite time blow up for a semilinear pseudo-parabolic equation with general nonlinearity, Appl. Math. Lett., 99 (2020), 105986, 7 pp. doi: 10.1016/j.aml.2019.07.017 [21] Numerical study of Q-ball formation in gravity mediation. J. Cosmol. Astropart. P. (2010) 6: 008-008. [22] Local existence and blow up of solutions to a logarithmic nonlinear wave equation with delay. Appl. Anal. (2020) 99: 530-547. [23] Some nonexistence and instability theorems for solutions of formally parabolic equations of the form $Pu_t = -Au+ F(u)$. Arch. Ration. Mech. Anal. (1973) 51: 371-386. [24] P. Li and C. Liu, A class of fourth-order parabolic equation with logarithmic nonlinearity, J. Inequal. Appl., (2018), Paper No. 328, 21 pp. doi: 10.1186/s13660-018-1920-7 [25] Global existence and blow up of solution for semilinear hyperbolic equation with logarithmic nonlinearity. Nonlinear Anal. (2019) 184: 239-257. [26] Global existence and blow up of solution for semi-linear hyperbolic equation with the product of logarithmic and power-type nonlinearity. Opuscula Math. (2020) 40: 111-130. [27] Global existence and blow up of solutions for pseudo-parabolic equation with singular potential. J. Differ. Equations (2020) 269: 4914-4959. [28] Global well-posedness of nonlinear wave equation with weak and strong damping terms and logarithmic source term. Adv. Nonlinear Anal. (2020) 9: 613-632. [29] Global existence and energy decay estimates for weak solutions to the pseudo-parabolic equation with variable exponents. Math. Method. Appl. Sci. (2020) 43: 2516-2527. [30] J.-L. Lions, Quelque Méthodes de Résolution des Problemes aux Limites non Linéaires, Dunod, Paris, 1969. [31] The existence, general decay and blow-up for a plate equation with nonlinear damping and a logarithmic source term. Electron. Res. Arch. (2020) 28: 263-289. [32] Initial-boundary value problem for a fourth-order plate equation with Hardy-Hénon potential and polynomial nonlinearity. Electron. Res. Arch. (2020) 28: 599-625. [33] Global existence and nonexistence in a system of petrovsky. J. Math. Anal. Appl. (2002) 265: 296-308. [34] Smooth attractors for strongly damped wave equations. Nonlinearity (2006) 19: 1495-1506. [35] Compact sets in the space $L^p(0, T;B)$. Ann. Mat. Pura Appl. (1987) 146: 65-96. [36] Pointwise gradient bounds for a class of very singular quasilinear elliptic equations. Discrete Contin. Dyn. Syst. (2021) 41: 4461-4476. [37] Global existence and finite time blowup for a nonlocal semilinear pseudo-parabolic equation. Adv. Nonlinear Anal. (2021) 10: 261-288. [38] On global solutions and blow-up of solutions for a nonlinearly damped Petrovsky system. Taiwan. J. Math. (2009) 13: 545-558. [39] Global existence and finite time blow-up for a class of semilinear pseudo-parabolic equations. J. Funct. Anal. (2013) 264: 2732-2763. [40] Global well-posedness of a class of fourth-order strongly damped nonlinear wave equations. Opuscula Math. (2019) 39: 297-313. [41] On the logarithmic Keller-Segel-Fisher/KPP system. Discrete Contin. Dyn. Syst. (2019) 39: 5365-5402. [42] Exponential decay of energy for a logarithmic wave equation. J. Partial Differ. Equ. (2015) 28: 269-277. [43] X. Zhu, B. Guo and M. Liao, Global existence and blow-up of weak solutions for a pseudo-parabolic equation with high initial energy, Appl. Math. Lett., 104 (2020), 106270, 7 pp. doi: 10.1016/j.aml.2020.106270
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

1.604 0.8


text:
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-19
Édouard Bonnet; Tillmann Miltzow

Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The Vertex Guard Art Gallery problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-07-06
Waldo Gálvez; José A. Soto; José Verschae

Online models that allow recourse can be highly effective in situations where classical online models are too pessimistic. One such problem is the online machine covering problem on identical machines. In this setting, jobs arrive one by one and must be assigned to machines with the objective of maximizing the minimum machine load. When a job arrives, we are allowed to reassign some jobs as long as

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-07-06
Surender Baswana; Keerti Choudhary; Moazzam Hussain; Liam Roditty

Let G=(V,E) be an n-vertices m-edges directed graph with edge weights in the range [1,W] for some parameter W, and sϵ V be a designated source. In this article, we address several variants of the problem of maintaining the (1+ε)-approximate shortest path from s to each vϵ V{s} in the presence of a failure of an edge or a vertex. From the graph theory perspective, we show that G has a subgraph H with

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-07-06
Josh Alman; Matthias Mnich; Virginia Vassilevska Williams

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n1+o(1)

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-19
Deeparnab Chakrabarty; Prachi Goyal; Ravishankar Krishnaswamy

In this article, we introduce and study the Non-Uniform k-Center (NUkC) problem. Given a finite metric space (X, d) and a collection of balls of radii { r1 ≥ … ≥ rk}, the NUkC problem is to find a placement of their centers in the metric space and find the minimum dilation α, such that the union of balls of radius α ⋅ ri around the ith center covers all the points in X. This problem naturally arises

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-19

Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? Equivalently, can we remove k obstacles so that there is an obstacle-free path between the two designated points? This is a fundamental NP-hard problem that has undergone a tremendous amount of research work. The problem can be formulated and generalized

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-07-06
Karl Bringmann; Paweł Gawrychowski; Shay Mozes; Oren Weimann

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Ʃ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well-known generalization of string edit distance. The fastest known algorithm for tree edit distance

更新日期：2020-07-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-12
Eden Chlamtáč; Michael Dinitz; Guy Kortsarz; Bundit Laekhanukit

It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin

更新日期：2020-06-12
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Sándor Kisfaludi-Bak; Jesper Nederlof; Erik Jan van Leeuwen

The STEINER TREE problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987{

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Ágnes Cseh; Tamás Fleiner

An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Rodrigo S. V. Martins; Daniel Panario; Claudio Qureshi; Eric Schmutz

Let [n{ = {1, …, n} and let Ωn be the set of all mappings from [n{ to itself. Let f be a random uniform element of Ωn and let T(f) and B(f) denote, respectively, the least common multiple and the product of the length of the cycles of f. Harris proved in 1973 that T converges in distribution to a standard normal distribution and, in 2011, Schmutz obtained an asymptotic estimate on the logarithm of

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Achiya Bar-On; Itai Dinur; Orr Dunkelman; Rani Hod; Nathan Keller; Eyal Ronen; Adi Shamir

The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Daniel Lokshtanov; Fahad Panolan; Saket Saurabh; Roohani Sharma; Meirav Zehavi

We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, the probability that X is a subset of Y is at least (((d+1)kk) . k(d+1))-1. The second is a new (deterministic)

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Martin Grohe; Daniel Neuen; Pascal Schweitzer; Daniel Wiebking

We give a new FPT algorithm testing isomorphism of n-vertex graphs of tree-width k in time 2kpolylog(k)n3, improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2O(k5 log k)n5. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
André Berger; László Kozma; Matthias Mnich; Roland Vincze

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families.

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Antonio Blanca; Zongchen Chen; Daniel Štefankoviè; Eric Vigoda

We study the following structure learning problem for H-colorings. For a fixed (and known) constraint graph H with q colors, given access to uniformly random H-colorings of an unknown graph G=(V,E), how many samples are required to learn the edges of G? We give a characterization of the constraint graphs H for which the problem is identifiable for every G and show that there are identifiable constraint

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Martin E. Dyer; Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum; Eric Vigoda

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d> 1 is added as a “long-range” edge with probability proportional to d-r, where r≥ 0 is a parameter of the model. Kleinberg [33{ studied a close variant of this network model and proved that the (decentralised) routing time is

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Antonios Antoniadis; Krzysztof Fleszar; Ruben Hoeksma; Kevin Schewior

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [27{, which gives rise to studying more tractable special cases of the problem. In this article, we focus on the fundamental

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Marthe Bonamy; Oscar Defrain; Marc Heinrich; Michał Pilipczuk; Jean-Florent Raymond

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for Kt-free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Ori Rottenstreich; Haim Kaplan; Avinatan Hassidim

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications, such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-06-01
Shay Solomon; Nicole Wein

This article studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n1-ε for any ε > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of

更新日期：2020-06-01
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-05-06
Johannes Fischer; Tomohiro I; Dominik Köppl

Given a text T of length n, we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O(c (lg n)½ + m lg m lg n lg* n) time with O(m) words of space under the premise that the space of T is rewritable, where m d n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m d

更新日期：2020-05-06
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-04-30
Cornetto

No abstract available.

更新日期：2020-04-30
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-03-31
David G Harris

The Lov\'{a}sz Local Lemma (LLL) is a probabilistic tool which shows that, if a collection of bad' events $\mathcal B$ in a probability space are not too likely and not too interdependent, then there is a positive probability that no bad-events in $\mathcal B$ occur. Moser \& Tardos (2010) gave sequential and parallel algorithms which transformed most applications of the variable-assignment LLL into

更新日期：2020-03-31
• ACM Trans. Algorithms (IF 0.758) Pub Date : 2020-03-20
Akanksha Agrawal; Daniel Lokshtanov; Pranabendu Misra; Saket Saurabh; Meirav Zehavi

For a family of graphs $\mathcal{F}$, the {\sc Weighted $\mathcal{F}$Vertex Deletion} problem, is defined as follows: given an $n$-vertex undirected graph $G$ and a weight function $w: V(G)\rightarrow\mathbb{R}$, find a minimum weight subset $S\subseteqV(G)$ such that $G-S$ belongs to $\cal{F}$. We devise a recursive scheme to obtain $\mathcal{O}(\log^{\mathcal{O}(1)}n)$-approximation algorithms for

更新日期：2020-03-20
Contents have been reproduced by permission of the publishers.

down
wechat
bug


text:
# American Mathematical Monthly Contents—June/July 2014

The June-July Monthly is loaded with six Articles and six Notes. While the theory of finite cyclic groups is well-known, the corresponding theory for finite cyclic monoids is not. Learn more by reading Alberto Facchini and Giulia Simonetta’s article “Rational numbers, finite cyclic monoids, divisibility rules, and numbers of the type 99…900…0.” You will need a sharp pencil for not only our Problem Section, but for Kevin Ferland’s Note where he constructs a New York Times style crossword puzzle that requires the maximum number of clues (96). We close with James Swenson’s review of Michael Henle’s Which Numbers are Real? Stay tuned in August-September when Erwan Brugalle and Kristin Shaw offer us “A Bit of Tropical Geometry.” —Scott Chapman

Vol. 121, No. 6, pp.471-560.

##### JOURNAL SUBSCRIBERS AND MAA MEMBERS:

To read the full articles, please log in to the member portal by clicking on 'Login' in the upper right corner. Once logged in, click on 'My Profile' in the upper right corner.

## ARTICLES

### Rational Numbers, Finite Cyclic Monoids, Divisibility Rules, and Numbers of Type 99 . . . 900 . . . 0

Alberto Facchini and Giulia Simonetta

There is a curious connection between decimal representations of rational numbers, the structure of finite cyclic monoids, divisibility rules between integers, and divisors of the numbers of the form 99 . . . 900 . . . 0. In all of these cases, we find not only periodicity from some point on, but also the same type of periodicity.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.471

### On the Solution of Linear Mean Recurrences

David Borwein, Jonathan M. Borwein, and Brailey Sims

Motivated by questions of algorithm analysis, we provide several distinct approaches to determining convergence and limit values for a class of linear iterations.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.486

### MATHBIT: Rejection of Laplace’s Demon

Josef Rukavicka

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.498

### Vertical Projection in a Resisting Medium: Reflections on Observations of Mersenne

C. W. Groetsch and S. A. Yost

This article, inspired by a 17th-century woodcut, validates empirical observations of Marin Mersenne (1588–1648) on timing of vertically-launched projectiles for a general mathematical model of resistance.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.499

### Three Dimensions of Knot Coloring

J. Scott Carter, Daniel S. Silver, and Susan G. Williams

The 1926 paper of J. W. Alexander and G. B. Briggs suggests a simple combinatorial invariant by coloring the crossings of a knot diagram. It is equivalent to the well-known Fox n-coloring of arcs and lesser-known Dehn n-coloring of regions. The equivalence of the three approaches to knot coloring is presented.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.506

### MATHBIT: An Alternate Proof of Sury’s Fibonacci–Lucas Relation

Harris Kwong

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.514

### On Hamilton’s Nearly-Forgotten Early Work on the Relation between Rotations and Quaternions and on the Composition of Rotations

Jose Pujol

In 1844, barely a year after inventing quaternions, Hamilton presented a paper to the Royal Irish Academy in which he introduced the scalar and vector products as used today (except for the sign of the former). He used them to solve the problem of the composition of any number of rotations about successive axes through any angles. Hamilton’s solution is surprisingly simple and includes the extremely important relation between rotations and quaternions. This work, published in 1847, was largely ignored, even to this date. On the other hand, the rotation-quaternion relation was published in 1845 by Cayley, using results derived by Rodrigues in 1840. As a consequence, Hamilton’s 1847 contribution to this problem has been overlooked, to the point that it has been claimed that he did not understand that relation, which is clearly not correct. This article settles this matter by going over Hamilton’s derivation, which is simpler than the Cayley–Rodrigues analysis, and does not require any advanced mathematics. Modern derivations of the equation for the rotation of a vector about an axis are based on a vector decomposition similar to that introduced by Hamilton. To appreciate the significance of Hamilton’s results, they are placed in a historical context.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.515

### MATHBIT: A Heuristic Argument for Hua’s Identity Using Geometric Series

B. Sury

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.522

### Lagrange’s Identity and Congressional Apportionment

Tommy Wright

This note makes use of Lagrange’s Identity to provide a bridge between an insightful motivation and an elementary derivation of the method of equal proportions. The method of equal proportions is the current method for apportioning the 435 seats in the U.S. House of Representatives among the 50 states, following each decennial census.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.523

## NOTES

### Pigeonholes and Repunits

Chai Wah Wu

It is well known that any integer $k$ has a multiple consisting of only the digits 1 and 0. As an extension of this result, we study integers of the form $111\cdots000$ or $111\cdots111$ that are a multiple of $k$. We show that if $k > 2$ and $k$ is not a power of 3, then the multiple can be chosen to have at most $k-1$ digits.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.529

### Record Crossword Puzzles

Kevin K. Ferland

The maximum number of clues possible for a $15\times15$ daily New York Times crossword puzzle is shown to be 96, and all possible puzzle grids with 96 clues are presented. Moreover, a crossword puzzle with 96 clues is given, in the theme of this result.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.534

### A Combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients

Michael Z. Spivey

We give a combinatorial proof of the identity for the alternating convolution of the central binomial coefficients. Our proof entails applying an involution to certain colored permutations and showing that only permutations containing cycles of even length remain.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.537

### A Converse of the Gauss–Lucas Theorem

Nikolai Nikolov and Blagovest Sendov

All linear operators $L:C[z]\rightarrow C[z]$ that decrease the diameter of the zero set of any $p\in C[z]$ are found.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.541

### Finding Your Seat Versus Tossing a Coin

Yared Nigussie

In a classroom of n seats and n students, the first student sits at random, whereas every other student must sit at her/his seat, but may sit randomly if her/his seat is already taken. The probability that a student finds her/his seat is given by a simple formula. Two entertaining proofs are given.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.545

### A Simple Direct Proof of Marden’s Theorem

Erich Badertscher

Marden’s theorem characterizes the critical points of complex polynomials of degree 3 in a nice geometrical way. Our proof of the theorem is based directly on the defining property of ellipses.

To purchase the article from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.547

## PROBLEMS AND SOLUTIONS

Problems 11782-117888
Solutions 11651, 11653, 11654, 11661

To purchase from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.549

## REVIEWS

Which Numbers Are Real? By Michael Henle

Reviewed by James A. Swenson

To purchase from JSTOR: http://dx.doi.org/10.4169/amer.math.monthly.121.06.557


text:
## Osaka Journal of Mathematics

### Infinite Markov particle systems associated with absorbing stable motion on a half space

Seiji Hiraba

#### Abstract

In general, for a Markov process which does not have an invariant measure, it is possible to realize a stationary Markov process with the same transition probability by extending the probability space and by adding new paths which are born at random times. The distribution (which may not be a probability measure) is called a Kuznetsov measure. By using this measure we can construct a stationary Markov particle system, which is called an equilibrium process with immigration. This particle system can be decomposed as a sum of the original part and the immigration part (see [2]). In the present paper, we consider an absorbing stable motion on a half space $H$, i.e., a time-changed absorbing Brownian motion on $H$ by an increasing strictly stable process. We first give the martingale characterization of the particle system. Secondly, we discuss the finiteness of the number of particles near the boundary of the immigration part. (cf. [2], [3], [4].)

#### Article information

Source
Osaka J. Math., Volume 51, Number 2 (2014), 337-359.

Dates
First available in Project Euclid: 8 April 2014

https://projecteuclid.org/euclid.ojm/1396966252

Mathematical Reviews number (MathSciNet)
MR3192545

Zentralblatt MATH identifier
1305.60036

Subjects
Primary: 60G57: Random measures
Secondary: 60G52: Stable processes

#### Citation

Hiraba, Seiji. Infinite Markov particle systems associated with absorbing stable motion on a half space. Osaka J. Math. 51 (2014), no. 2, 337--359. https://projecteuclid.org/euclid.ojm/1396966252

#### References

• S.N. Ethier and T.G. Kurtz: Markov Processes, Wiley, New York, 1986.
• S. Hiraba: Infinite Markov particle systems with singular immigration; martingale problems and limit theorems, Osaka J. Math. 33 (1996), 145–187.
• S. Hiraba: Asymptotic behavior of hitting rates for absorbing stable motions in a half space, Osaka J. Math. 34 (1997), 905–921.
• S. Hiraba: Independent infinite Markov particle systems with jumps, Theory Stoch. Process. 18 (2012), 65–85.
• R.Sh. Liptser and A.N. Shiryayev: Theory of Martingales, Kluwer Acad. Publ., Dordrecht, 1989.
• T. Shiga and Y. Takahashi: Ergodic properties of the equilibrium process associated with infinitely many Markovian particles, Publ. Res. Inst. Math. Sci. 9 (1973/74), 505–516.