Basic question on sampling stream of data

Question

I am reading up an article and came across sampling scenario, but I am not able to come up with intuition behind the numbers presented.

Scenario: User issuing search queries to a search engine.

"Suppose a user has issued s search queries one time in the past month, d search queries twice, and no search queries more than twice. If we have a 1/10th sample, of queries, we shall see in the sample for that user an expected s/10 of the search queries issued once. Of the d search queries issued twice, only d/100 will appear twice in the sample; that fraction is d times the probability that both occurrences of the query will be in the 1/10th sample. Of the queries that appear twice in the full stream, 18d/100 will appear exactly once."

So here is how I interpreted the above scenario s queries are sampled at 1/10 rate.

Therefore probability of retaining an element from s elements = 1/10
Probability that a query issued twice is retained = 1/10 * 1/10
But this where I deviate, probability of retaining d such queries issued twice must be = (1/10)^d right?

The probability of a query appearing once in a sample but issued twice = 1/10*(1-1/10) = 9/100 right?

Where am I going wrong?

Answer 1

It might be easiest to look at this question from the opposite end. Let's start by enumerating all possibilities for the queries that are searched twice to appear in the sample:

1. They appear in sample twice (1/100)
2. They appear in sample once (?/100)
3. They don't appear in sample (?/100)

You know how to do 1, and not sure about 2, so let's look at 3. This can be done exactly the same way you looked at 1: the probability of missing any given query is 9/10, so the probability of missing two (making the same assumptions that the question implicitly makes) is 9/10 * 9/10 = 81/100.

Now since 1, 2 and 3 enumerate all possible scenarios, they're probabilities must add up to 1. Hence the probability that a twice-searched query appears once in sample is 1 - 1/100 - 81/100 = 18/100.

So where did you go wrong?

Well, 1/10*(1-1/10) descibes the case where, say, the first search query is in sample and the second isn't, but not vice versa. That is, it does not account for the case where the second query is in sample and the first isn't. To take that into account as well, you have 1/10*(1-1/10) + (1-1/10)*1/10 = 18/100.

This is actually a binomial random variable, where you have a fixed number of independent events (in this case the two instances of a search query) that each have the same probability of success (in this case being selected in the sample). We can say that the probability of an $n$-times-searched query being sampled $k$ times in a $p$ proportion sample is: ${n\choose{k}} p^k(1-p)^{n-k}$