I wanted to get a more in-depth understanding of sampling algorithms, and so I thought I could start with the very simple example of a binomial or bernoulli likelihood with a beta prior (since it is solvable in closed form, I thought it might be suitable).
Assume we have trials where have draw $N$ times, and count $k$ successes. $N$ is a deterministic parameter predefined in the experimental setting. We model $k \mid \theta, N \sim \text{Binomial}(\theta, N)$ and model $\theta \sim \text{Beta}(\alpha_0, \beta_0)$. We would like to obtain $\Pr(\theta \mid k, N)$ by sampling, given several observations of $k$, without relying on the closed-form solution of a Beta-posterior.
Looking at MacKay's Information theory, inference and learning algorithms, we would start with an initial $x=(k_0, \theta_0)$, and use the $\text{Binomial}(k\mid \theta_0, N)$ to draw a new $k_1$. This part I can understand, because it is drawing a random sample from a binomial distribution. Then we would use $\Pr(\theta\mid k_1, N)$ to draw $\theta_1$. This part I do not understand anymore, because at this point, we don't have a posterior yet, don't we? So without a posterior distribution $\Pr(\theta\mid k, N)$, how can we sample a new $\theta$?. And furthermore, **shouldn't the algorithm also sample from the observed $k$ values? Or am I missing a step?