Metropolis - Hastings algorithm on a set of countable sequences

Question

I want to simulate $\sigma$ from a measure $\pi(\sigma)$ through the Metropolis-Hastings algorithm, where $\sigma$ is a sequence of 0's and 1's on $S = \{0, 1\}^n$, the set of all sequences of 0's and 1's with a fixend length $n \in \mathbb{N}$ and $\pi(\sigma) = \textit{the number of 0's in the sequence}$.

In order to build the algorithm i need to find the distribuition of $\pi(\sigma)$ and a candidate distribuition $q$. How do I find both the distribuition of $\pi$ and a good candidate distribuition $q$? ( I know that a good distribuition will have the same support of $\pi$). Any hints or advices are more than welcome!

Answer 1

One of the benefits of doing MH is that you don't have to figure out $\pi(\sigma)$. You just need the unnormalized version.

Here's some Python code:

import numpy as np

def log_pi_unnorm(sigma):
    """evaluates unnormalized target"""
    s = np.sum(sigma)
    return np.log(s) if s > 0 else -np.inf

def proposal_samp(old_sigma):
    """proposes independently of old_sigma and uniformly across sample space"""
    return np.random.binomial(1, .5, len(old_sigma))

def do_one(old_sigma):
    """returns proposal if accepted; otherwise returns previous sigma"""
    proposed = proposal_samp(old_sigma)
    log_ratio = log_pi_unnorm(proposed)
    log_ratio -= log_pi_unnorm(old_sigma)
    if np.log(np.random.uniform(low=0, high=1)) < log_ratio:
        return proposed
    else:
        return old_sigma
    
# perform sampling
n = 10
num_iters = 10000
sigma_samps = np.zeros((num_iters,n))
sigma_samps[0,:] = np.random.binomial(1,.5,size=n)

for i in range(1, num_iters):
    sigma_samps[i,] = do_one(sigma_samps[i-1,])
    
#some plots
import matplotlib.pyplot as plt
fig, axs = plt.subplots(2)

# Hamming distance between sample and vector of all 0s
num_ones = np.apply_over_axes(np.sum, sigma_samps, 1)
axs[0].plot(num_ones)
axs[1].hist(num_ones)