# Discrete state space sampeled from a symmetric proposal distribution (monte carlo sampling) in R

I am new to MCMC, but proficient in R.

I want to draw Markov chain Monte Carlo samples for the following scenario:

The state space consists of all combinations of n vectors out of a larger set of m > n vectors. I am searching for one of these combinations s with certain properties. Therefore I need to draw samples of s from a symmetric proposal distribution in a MCMC-type fashion.

To illustrate

Suppose we have m = 4 vectors (one per row), which are binary (my problem has m > 4, this is just to illustrate).

everything <- expand.grid(x1=0:1,x2=0:1)
everything
#   x1 x2
# 1  0  0
# 2  1  0
# 3  0  1
# 4  1  1


We need to sample one subset s of the four vectors containing only n = 2 vectors. Our state space for n = 2 are all possible combinations of 2 vectors (2 of 4 = 6).

statespace <- apply(t(combn(4,2)), 1, function(x) everything[x,])
statespace
# [[1]]
#   x1 x2
# 1  0  0
# 2  1  0

# [[2]]
#   x1 x2
# 1  0  0
# 3  0  1

# [[3]]
#   x1 x2
# 1  0  0
# 4  1  1

# [[4]]
#   x1 x2
# 2  1  0
# 3  0  1

# [[5]]
#   x1 x2
# 2  1  0
# 4  1  1

# [[6]]
#   x1 x2
# 3  0  1
# 4  1  1


Now I wish to sample from this simple state space s = 1,2,3,4,5,6. We start with a random proposal s_start, say number 4; and then draw the next proposal s_next such that it generates a Markov chain Monte Carlo sample such that the proposal distribution is symmetric.

What I found is that usually we use a multivariate normal distribution for this. That is p(s_next | s_start) ~ N(s_start, some.variance).

But this supposes continuous variables in s. In my case, there are two discrete vectors with binary values each.

Which type of distribution can I use to generate MCMC samples for s such that the vector combinations s_next that are more similar to the current proposal s_start are more likely to be chosen compared to vectors more dissimilar? (This is my understanding of a symmetric proposal distribution, maybe I have gotten that wrong in the first place).

## migrated from stackoverflow.comJun 15 '16 at 15:10

This question came from our site for professional and enthusiast programmers.

• Seems to me more a statistic than a programming question. Voting to move to Cross Validated. – nicola Jun 15 '16 at 12:27
• 1) This is a stats question, not a programming question. 2) Cant you just sample(0:n, n, replace = T)? I think MCMC's have to come from a uniform distribution too. But not 100% sure. – Bryan Goggin Jun 15 '16 at 12:48
• Thanks for migrating! Uniform was indeed my first idea, but I thought that uniform proposal distributions for super large supports is not going to be efficient (in my problem, the support blows up easily) – JBJ Jun 16 '16 at 9:31