walkr: The walkr package.

In walkr: Random Walks in the Intersection of Hyperplanes and the N-Simplex

Description

Package	walkr
Type:	Package
Version:	0.3.1
Date:	2015-07-14
License:	GPL-3

Given Ax = b, walkr samples points from the intersection of Ax = b with the n-simplex (∑ x = 1, x_i ≥ 0). The Ax = b must be underdetermined, otherwise there is an unique solution and there will be no sampling.

Usage

walkr(A, b, points, method = "dikin", thin = 1, burn = 0.5,
  chains = 1, ret.format = "matrix")

Arguments

A	is the lhs of the matrix equation A
b	is the rhs of the matrix equation b
points	is the number of points we want to sample
method	is the MCMC sampling method. Please enter "hit-and-run", "dikin", or " optimized-dikin"
thin	every thin-th point is stored
burn	the first burn points are deleted
chains	is the number of chains we run
ret.format	is the format in which walkr returns the answer. Please enter "list" (of chains) or "matrix".

Details

The walkr package samples points using MCMC random walks from the intersection of the N-Simplex with M hyperplanes. Mathematically speaking, the sampling space is all vectors x that satisfy Ax = b, ∑ x = 1, and x_i ≥ 0. The sampling algorithms implemented are hit-and-run and Dikin Walk. walkr also provides tools to examine and visualize the convergence properties of the random walks.

The main function of the package is walkr. The user specifies A and b in Ax = b, and the walkr function samples points from the complete solution to Ax=b intersected with the N-simplex. The user can choose either "dikin" or "hit-and-run" as the sampling method, and the function also provides other MCMC parameters such as thinning and burning.

Before the sampling, walkr internally performs the affine transformation which takes the complete solution of Ax = b and that intersected with the unit simplex into a space parametrized by coefficients, which we call the "alpha-space". The specific set of procedures taken is written in detail in the vignette. Essentially, the space is transformed, the sampling takes place in the transformed space, and in the end walkr transforms back into the original coordinate system and returns the result. This transformation is affine, so the uniformity and mixing properties of the MCMC algorithms are not affected. The current MCMC sampling methods supported are "hit-and-run", "dikin" and "optimized-dikin" (a Rcpp boosted version for speed).

1) Hit-and-run is computationally less expensive and also guarantees uniformity asympotically with complexity of O(n^3) points with respect to dimension n. However, in real practice, as dimensions ramp up, the mixing of hit-and-run is poor compared to Dikin. Thus, a lot of thinning would be needed as dimension ramps up.

2) Dikin Walk is a nearly uniform method known for its very strong mixing properties. However, each Dikin step is much more computationally expensive than hit-and-run, so it takes more time to sample every point. Thus, the "dikin" method uses RcppEigen to speed up the core computationally expensive operations in the algorithm.

Value

Either a list of chains (with each chain as a matrix of points) or a matrix containing all the points. Each column is a point sampled.

Examples

## 4D constraint
A <- matrix(c(2,0,1,3), ncol = 4)
b <- 0.5
sampled_points <- walkr(A = A, b = b, points = 100, method = "dikin")                
                                               

walkr documentation built on June 29, 2019, 9:02 a.m.