I am going to try to expand my previous comment and correct some notation (let me know if I am mistaken). (Thanks for the suggestion @Macro)
1. In this case you need to know explicitely what $p(x_j\vert x_{j-1})$ means (Note that here $x_{j-1}$ is a known value and this distribution depends on this value somehow). An example of this is
$$x_j\sim \mbox{Normal}(x_{j−1},1).$$
In this case, in order to sample from $x_j$, you just need to sample from the a normal distribution with mean $x_{j−1}$ and variance $1$. For other examples you can check the wikipedia page for Markov chains or check other transition kernels.
2. A pseudocode for obtaining a sample of size $M$ with replacement is as follows
Starting with a known sample $\{x_i,i=1,...,N\}$, repeat $M$ times
(i). Consider partitioning the interval $(0,1)$ into $N$ subintervals $I_1=(0,w_1)$,
$I_2=(w_1,w_1+w_2)$,..., $I_N = (\sum_{j=1}^{N-1}w_j,1)$.
(ii). Simulate $u\sim U(0,1)$.
(iii). Identify the interval $I_j$, $j\in\{1,...,N\}$, such that $u\in I_j$.
(iv). Take the sample $x_j$.
As you can see, there is a difference between these two methods.
In the first one you have a model, $p(x_{j}|x_{j−1})$ , and you simulate from it. Starting from, say $x_0$, the next value $x_1$ is sampled from $p(x_1|x_0)$; then the second value $x_2$ is sampled from $p(x_2|x_1)$ and so forth. For this purpose you need to be able to simulate from the conditional distributions $p(\cdot\vert\cdot)$. This is, you obtain a sample $\{x_i,i=1,...,N\}$
In the second sampling method (re-sampling) you already have a sample $\{x_i,i=1,...,N\}$ and you obtain a new sample by picking elements from the original one. This is similar to the 'urn game'. Imagine you have an urn with $N$ elements of different sizes (illustrating the different weights), you pick one of them, record the result and put it back in the urn. This experiment is repeated $M$ times.
I hope this helps.
This reply presents two solutions: Sheppard's corrections and a maximum likelihood estimate. Both closely agree on an estimate of the standard deviation: $7.70$ for the first and $7.69$ for the second (when adjusted to be comparable to the usual "unbiased" estimator).
Sheppard's corrections
"Sheppard's corrections" are formulas that adjust moments computed from binned data (like these) where
the data are assumed to be governed by a distribution supported on a finite interval $[a,b]$
that interval is divided sequentially into equal bins of common width $h$ that is relatively small (no bin contains a large proportion of all the data)
the distribution has a continuous density function.
They are derived from the Euler-Maclaurin sum formula, which approximates integrals in terms of linear combinations of values of the integrand at regularly spaced points, and therefore generally applicable (and not just to Normal distributions).
Although strictly speaking a Normal distribution is not supported on a finite interval, to an extremely close approximation it is. Essentially all its probability is contained within seven standard deviations of the mean. Therefore Sheppard's corrections are applicable to data assumed to come from a Normal distribution.
The first two Sheppard's corrections are
Use the mean of the binned data for the mean of the data (that is, no correction is needed for the mean).
Subtract $h^2/12$ from the variance of the binned data to obtain the (approximate) variance of the data.
Where does $h^2/12$ come from? This equals the variance of a uniform variate distributed over an interval of length $h$. Intuitively, then, Sheppard's correction for the second moment suggests that binning the data--effectively replacing them by the midpoint of each bin--appears to add an approximately uniformly distributed value ranging between $-h/2$ and $h/2$, whence it inflates the variance by $h^2/12$.
Let's do the calculations. I use R to illustrate them, beginning by specifying the counts and the bins:
counts <- c(1,2,3,4,1)
bin.lower <- c(40, 45, 50, 55, 70)
bin.upper <- c(45, 50, 55, 60, 75)
The proper formula to use for the counts comes from replicating the bin widths by the amounts given by the counts; that is, the binned data are equivalent to
42.5, 47.5, 47.5, 52.5, 52.5, 57.5, 57.5, 57.5, 57.5, 72.5
Their number, mean, and variance can be directly computed without having to expand the data in this way, though: when a bin has midpoint $x$ and a count of $k$, then its contribution to the sum of squares is $kx^2$. This leads to the second of the Wikipedia formulas cited in the question.
bin.mid <- (bin.upper + bin.lower)/2
n <- sum(counts)
mu <- sum(bin.mid * counts) / n
sigma2 <- (sum(bin.mid^2 * counts) - n * mu^2) / (n-1)
The mean (mu) is $1195/22 \approx 54.32$ (needing no correction) and the variance (sigma2) is $675/11 \approx 61.36$. (Its square root is $7.83$ as stated in the question.) Because the common bin width is $h=5$, we subtract $h^2/12 = 25/12 \approx 2.08$ from the variance and take its square root, obtaining $\sqrt{675/11 - 5^2/12} \approx 7.70$ for the standard deviation.
Maximum Likelihood Estimates
An alternative method is to apply a maximum likelihood estimate. When the assumed underlying distribution has a distribution function $F_\theta$ (depending on parameters $\theta$ to be estimated) and the bin $(x_0, x_1]$ contains $k$ values out of a set of independent, identically distributed values from $F_\theta$, then the (additive) contribution to the log likelihood of this bin is
$$\log \prod_{i=1}^k \left(F_\theta(x_1) - F_\theta(x_0)\right) =
k\log\left(F_\theta(x_1) - F_\theta(x_0)\right)$$
(see MLE/Likelihood of lognormally distributed interval).
Summing over all bins gives the log likelihood $\Lambda(\theta)$ for the dataset. As usual, we find an estimate $\hat\theta$ which minimizes $-\Lambda(\theta)$. This requires numerical optimization and that is expedited by supplying good starting values for $\theta$. The following R code does the work for a Normal distribution:
sigma <- sqrt(sigma2) # Crude starting estimate for the SD
likelihood.log <- function(theta, counts, bin.lower, bin.upper) {
mu <- theta[1]; sigma <- theta[2]
-sum(sapply(1:length(counts), function(i) {
counts[i] *
log(pnorm(bin.upper[i], mu, sigma) - pnorm(bin.lower[i], mu, sigma))
}))
}
coefficients <- optim(c(mu, sigma), function(theta)
likelihood.log(theta, counts, bin.lower, bin.upper))$par
The resulting coefficients are $(\hat\mu, \hat\sigma) = (54.32, 7.33)$.
Remember, though, that for Normal distributions the maximum likelihood estimate of $\sigma$ (when the data are given exactly and not binned) is the population SD of the data, not the more conventional "bias corrected" estimate in which the variance is multiplied by $n/(n-1)$. Let us then (for comparison) correct the MLE of $\sigma$, finding $\sqrt{n/(n-1)} \hat\sigma = \sqrt{11/10}\times 7.33 = 7.69$. This compares favorably with the result of Sheppard's correction, which was $7.70$.
Verifying the Assumptions
To visualize these results we can plot the fitted Normal density over a histogram:
hist(unlist(mapply(function(x,y) rep(x,y), bin.mid, counts)),
breaks = breaks, xlab="Values", main="Data and Normal Fit")
curve(dnorm(x, coefficients[1], coefficients[2]),
from=min(bin.lower), to=max(bin.upper),
add=TRUE, col="Blue", lwd=2)
To some this might not look like a good fit. However, because the dataset is small (only $11$ values), surprisingly large deviations between the distribution of the observations and the true underlying distribution can occur.
Let's more formally check the assumption (made by the MLE) that the data are governed by a Normal distribution. An approximate goodness of fit test can be obtained from a $\chi^2$ test: the estimated parameters indicate the expected amount of data in each bin; the $\chi^2$ statistic compares the observed counts to the expected counts. Here is a test in R:
breaks <- sort(unique(c(bin.lower, bin.upper)))
fit <- mapply(function(l, u) exp(-likelihood.log(coefficients, 1, l, u)),
c(-Inf, breaks), c(breaks, Inf))
observed <- sapply(breaks[-length(breaks)], function(x) sum((counts)[bin.lower <= x])) -
sapply(breaks[-1], function(x) sum((counts)[bin.upper < x]))
chisq.test(c(0, observed, 0), p=fit, simulate.p.value=TRUE)
The output is
Chi-squared test for given probabilities with simulated p-value (based on 2000 replicates)
data: c(0, observed, 0)
X-squared = 7.9581, df = NA, p-value = 0.2449
The software has performed a permutation test (which is needed because the test statistic does not follow a chi-squared distribution exactly: see my analysis at How to Understand Degrees of Freedom). Its p-value of $0.245$, which is not small, shows very little evidence of departure from normality: we have reason to trust the maximum likelihood results.
Best Answer
This "number of independent samples I really have" is called the effective sample size in simulation books, $N_\text{ess}$. Given a sample $$ x_1,\ldots,x_N \sim g(x) $$ leading to weights $w_i$ $(1\le i\le N)$, and their normalised version $$ \bar w_i = w_i / \sum_{j=1}^N w_j\,, $$ the estimate for $N_\text{ess}$ is given by $$ \hat N_\text{ess} = 1 \big/ \sum_{j=1}^N \bar w_j^2\,. $$ You can prove that $1\le \hat N_\text{ess}\le N$. In your example, the effective sample size is estimated by
a wee more than 2.
I am not sure I understand the last part of the question.