How to compute confidence intervals from *weighted* samples?

Question

Imagine we have a webserver, which serves a total of N static URLS.

There are users visiting the URLs every day. At the end of each day, we have data like this:

URL1   --> 500 visits
URL2   --> 450 visits
URL3   --> 370 visits
URL4   --> 330 visits
...
URLN-1 --> 1 visit
URLN   --> 0 visits

Then, we take a weighted sample out of these URLs. Each URL is included in the sample with probability proportional to the number of visits.

E.g. URLN will never be sampled, And URLN-1 (which was only visited once that day) is 500 times less likely to be selected than URL1.

Why we sample?

Each URL leads to a page which either has a white background or a black one. Assume that determining this background is a time-consuming task which we can't automate it. Hence, we would like to sample a small number of URLs, manually check their colors, and produce such an estimate for the whole set of URLs:

• How likely will a URL visit lead to a page with a white background?

This is easy: given a set of sampled URLs, for which we have manually determined the colors, we compute the following:

  (SUM of visits of white URLs in the sample) / (SUM of all visits in the sample)

E.g. if this produced a number like 0.40, we could say "we estimate that 40% of URL visits lead to a page with white background".

But here's the tricky part:

• How can we compute confidence intervals (say at 95%) for this quantity?

I've been reading various "resampling" or "bootstrap" techniques (wikipedia), for example Jackknife or Bootstrap, or even Poisson Bootstrap which seems a good choice for large data that need to be processed in a distributed way.

To get a 95% confidence interval with such a method, all I'd have to do would be to compute the 2.5% and 97.5% quantiles of the generated estimates.

But all these methods appear to assume that the sampled observations (URLs here) are selected with the same probability. In my case, they aren't, they are selected with probability proportional to the number of visits.

And again, let's assume that I can't avoid the use of weights, I can't process my data to remove the weights, e.g. by replacing "URL111 --> 2 visits, URL999 --> 3 visits" with [URL111, URL111, URL999, URL999, URL999]. Sure, in that case, these bootstrapping techniques would work without modification.

So: Is there a way to augment one of these techniques to take account of sampling weights, and to produce confidence intervals?

Answer 1

You have a scheme of two-level sampling, first sampling the urls, then sampling from that empirical distribution over urls to detect some website property. I will assume that website property, White (W) is constant in time, so it is enough to visit each site once. So it would be best with sampling without replacement, but you didn't tell us how you sampled. So first I will assume sampling with replacement, since that is easier analysis, and good approximation if number of sites is large.

Some notation. There is a population of websites (urls) visited by some frequencies $\pi=(\pi_1, \dotsc, \pi_S)$. Each website has (or not) some property $W$, written $W_i$ for site $i$, which is 1 if site is $W$ and 0 else. On the first level of sampling site $i$ is visited $N_i$ times, and so we have an estimate of $\pi_i$, $\hat{\pi}_1=N_i/N_\cdot$, where $N_\cdot=\sum_i N_i$.

On the second level of sampling, we sample websites from the distribution $\hat{\pi}$ (with replacement), $n$ times. Let the site being sampled be $I_j$, but first we concentrate on the first time and write only $I$. Under the second-level distribution, we have $\DeclareMathOperator{\P}{\mathbb{P}} \P(I=i)=\hat{\pi}_i$. The observed property is $W_I$, and we have $$ \P(W_I=1)=\sum_i \P(W_I=1 \mid I=i)\hat{\pi}_i=\sum_i W_i \hat{\pi}_i $$ and then taking the expectation of that expression over the first-level sampling, we find $\P(W_I=1)=\sum_i W_i \pi_i$ which we denote by $Q$ and is the weighted fraction of sites with the property, which is our estimand. So the $\sum_{j=1}^n W_{I_j}$ has a binomial distribution with parameters $n,Q$, and confidence intervals can be based on that.