# Star sampling with and without replacement

Jonathan Stokes and Steven Weber Preliminary published versions of this work
include [1, 2, 3]. This work was supported by the National Science Foundation
$\\#$IIS-1250786. J. Stokes and S. Weber are with the Department of Electrical
and Computer Engineering of Drexel University. S. Weber is the contact author:
<EMAIL_ADDRESS>
###### Abstract

Star sampling (SS) is a random sampling procedure on a graph wherein each
sample consists of a randomly selected vertex (the star center) and its (one-
hop) neighbors (the star points). We consider the use of SS to find any member
of a target set of vertices in a graph, where the figure of merit (cost) is
either the expected number of samples (unit cost) or the expected number of
star centers plus star points (linear cost) until a vertex in the target set
is encountered, either as a star center or as a star point. We analyze these
two performance measures on three related star sampling paradigms: SS with
replacement (SSR), SS without center replacement (SSC), and SS without star
replacement (SSS). Exact and approximate expressions are derived for the
expected unit and linear costs of SSR, SSC, and SSS on Erdős-Rényi (ER) random
graphs. The approximations are seen to be accurate. SSC/SSS are notably better
than SSR under unit cost for low-density ER graphs, while SSS is notably
better than SSR/SSC under linear cost for low- to moderate-density ER graphs.
Simulations on twelve “real-world” graphs shows the cost approximations to be
of variable quality: the SSR and SSC approximations are uniformly accurate,
while the SSS approximation, derived for an ER graph, is of variable accuracy.

###### Index Terms:

graph sampling; sampling with replacement; graph search; Erdős-Rényi random
graph.

##  I Introduction

Let $G=(V,E)$ denote a simple undirected graph with vertex set $V$ and edge
set $E$. Suppose each vertex has a property value, defined via a function
$f:V\to P$, for $P$ the set of property values. Then $V^{*}\equiv
f^{-1}(P^{*})$, for $P^{*}\subset P$, is the subset of vertices holding
property values of interest (i.e., vertices with properties in $P^{*})$. This
paper evaluates the performance of three related random sampling approaches to
finding a vertex in $V^{*}$, called star sampling, described below, that
differ in terms of which part of the sample is replaced.

Star sampling. Using random sampling to search for a vertex of interest is
often suitable for large and/or dynamic graphs, where either the order/size
and/or the rapid evolution of the graph precludes holding the graph in local
memory. In such cases the searcher may be required to query the graph, by
requesting a random vertex. Star sampling (SS) is a variant on vertex sampling
in which each sample returns not only the property value $f(v)$ of the
selected vertex $v\in V$, termed the star center, but also the property values
$f(N_{G}(v))$ of its (one-hop) neighbors $N_{G}(v)$ (where
$N_{G}(v)\equiv\\{u\in V:uv\in E\\}$ is the neighborhood of $v$, and $uv\in E$
denotes vertices $u$ and $v$ are joined by an edge), termed the star points.
Random star sampling selects a vertex uniformly at random, then checks whether
either it or any of its neighbors hold the property of interest; this is
repeated until a vertex in $V^{*}$ is found.

Cost. Although large graphs are encoded in a variety of ways, it is often the
case that the data structure corresponding to each vertex (e.g., the profile
of a particular member in a social network) includes the list of neighbors of
that vertex (e.g., the social connections of that member in the network). Star
sampling is a practical sampling paradigm whenever such neighbor information
is available. The property may be readily available if it is easily
computable, or if it is not easily computable, but has been precomputed and
stored in the data structure for the vertex. To address this issue we consider
two natural cost models (unit and linear), where cost is measured either as
the number of star samples (unit cost) or as the number of vertices (linear
cost) for which property values are queried / computed. Unit cost is most
natural for the case when the primary cost incurred is the query of the star
itself and property values of neighbors are readily available, while linear
cost is most natural for the case where the primary cost incurred is the
computation of the property value.

Target set. We focus on the case where $P^{*}$ is independent of $G$, i.e.,
the target set is a subset $\mathsf{V}^{*}$, chosen uniformly at random from
$V$, with prescribed cardinality $|\mathsf{V}^{*}|=n^{*}$. As such, the
expected search cost to find a member of the target set depends upon the set
only through $n^{*}$.

Variants. Three SS variants are considered:

  * •

SS with replacement (SSR): the star center is selected uniformly at random
from the set of vertices;

  * •

SS without center replacement (SSC): the star center is selected uniformly at
random from the set of remaining vertices; the star center (along with its
adjacent edges) is removed from the graph after the query;

  * •

SS without star replacement (SSS): the star center is selected uniformly at
random from the set of remaining vertices; the entire star (center, points,
and all adjacent edges) is removed from the graph after the query.

Urn sampling. One motivation in considering these variants is to understand
their relative performance, in a manner similar to the elementary case of
sampling balls from an urn. When seeking any one of $n^{*}$ marked balls out
of a total of $n\geq n^{*}$ balls in an urn, sampling with replacement
requires on average $n/n^{*}$ samples; this follows immediately from the
observation that the number of draws until the first success, say
$\mathsf{c}^{\rm R}$, is a geometric random variable (RV) with success
probability $n^{*}/n$, and expectation $\mathbb{E}[\mathsf{c}^{\rm
R}]=n/n^{*}$. In contrast, sampling without replacement requires a random
number of draws, $\mathsf{c}^{\rm NR}$, with expectation given by the
following Fact.

######  Fact 1.

$\mathbb{E}[\mathsf{c}^{\rm NR}]=(n+1)/(n^{*}+1)$.

The proof is found in App. A.

Thus, the performance ratio of the expected number of samples with vs. without
replacement is $\mathbb{E}[\mathsf{c}^{\rm R}]/\mathbb{E}[\mathsf{c}^{\rm
NR}]=(1+1/n^{*})/(1+1/n)$. For $n^{*}\ll n$, sampling without replacement
improves the mean search time by at most two, relative to sampling with
replacement, with equality for $n^{*}=1$.

Contributions. The three primary contributions are:

  * •

Derivation of exact, bound, and approximate expected unit and linear cost
expressions, for both arbitrary graphs and Erdős-Rényi (ER) random graphs, for
the three star sampling variants; these results are summarized in Table I.

  * •

Numerical assessment of quality, in which the bounds are shown to be tight,
and the approximations are seen to be accurate, relative to simulation results
of ER random graphs; these results are seen in §IV-C (Fig. 3) and §V-C (Fig.
4).

  * •

Numerical assessment on “real-world” graphs, in which the relative error of
the approximations are compared with simulation results; c.f. §VI (Table IV
and Table V).

Three points of context for the results bear mention.

  * •

The accuracy of the cost approximations is notable, particularly for SSS,
given the complexity of the dynamics under star sampling without star
replacement. The conditional probability of hitting the star at time $t$,
conditioned on not hitting it before, is approximated by tracking both the
expected reduction in the overall order of the graph and the expected
reduction in the number of neighbors of the target set in the previous $t-1$
samples. This yields an approximate unconditional probability of first hitting
the target set at $t$, which in turn yields an approximate expected cost.

  * •

The (mostly) small relative error of the cost approximations for “real-world”
graphs is notable, particularly for SSS, given the approximations are derived
for ER graphs, which are quite distinct from the “real-world” graphs.

  * •

It is notable that all cost approximations require knowing only three
quantities: the graph order ($n$), the target set cardinality ($n_{0}^{*}$),
and the graph edge density $s$.

Graph | Variant | Unit cost (§IV) | Linear cost (§V)
---|---|---|---
Arbitrary | SSR | Fact 2 (exact) | Fact 6 (exact)
Arbitrary | SSC | Fact 3 (exact) | N/A
Arbitrary | SSS | N/A | N/A
Erdős-Rényi | SSR | Prop. 1 (bounds) | Prop. 4 (approx.)
Erdős-Rényi | SSC | Prop. 1 (bounds) | Prop. 5 (approx.)
Erdős-Rényi | SSS | Thm. 2 (approx.) | Prop. 6 (approx.)
TABLE I: Summary of results

Outline. The paper is organized as follows. §II discusses related work. §III
provides basic notation and definitions. §IV and §V study performance under
the unit and linear cost models, respectively. §VI assesses the accuracy and
relative performance of the cost estimates on “real-world” graphs. §VII gives
a brief conclusion. Most proofs are in the Appendices.

##  II Related work

There is an extensive literature on graph sampling, too vast to credibly
review here. Classic graph exploration strategies include: random sampling of
vertices or edges, random walks, and random jump sampling, which alternates
between a random walk and random sampling. These graph exploration strategies
are general in the sense that they may be applied towards a variety of
objectives. Two notable classes of objectives include $i)$ sampling to derive
an unbiased estimate of some graph property, and $ii)$ sampling to search for
vertices with particular properties; this paper falls into the latter
category.

Snowball sampling [4] was introduced in [5] (see also [6, 7, 8, 9]); star
sampling, a special case of snowball sampling, appears in [10]. Ref. [11]
argues that Metropolis-Hastings sampling algorithms should avoid backtracking.
Ref. [12] proposed a rejection controlled Metropolis-Hastings algorithm and a
non-backtracking generalized maximum-degree sampling algorithm. Ref. [13]
found that a Metropolis-Hasting random walk and a re-weighted random walk both
outperform a simple random walk in returning a uniform sample of Facebook
users. Ref. [14] has shown that weighted random walks can be used to carry out
stratified sampling on graphs. Ref. [15] bounds the number of steps required
to return a uniform sample of a network using rejection sampling, maximum-
degree sampling, and Metropolis-Hastings sampling.

Our pertinent prior and related work includes [1, 2, 3]. Ref. [1] compares the
cost of using random walk vs. random sampling to find a target vertex. Ref.
[2] analyzes the cost of finding a degree $j$ vertex or an edge with vertices
of degrees $j,k$ via star sampling without replacement. Ref. [3] holds
preliminary results comparing star sampling with and without replacement. To
our knowledge, ours is the first work to study the performance impact of
replacement on star sampling.

##  III Notation, Sampling Model, Background

Notation is defined in §III-A, ER graphs and their properties are described in
§III-B, and the three sampling models and two cost models are stated in
§III-C.

###  III-A Notation

Let $a\equiv b$ denote $a$ and $b$ are equal by definition. Let $[n]$ denote
$\\{1,\ldots,n\\}$, for $n\in\mathbb{N}$. Scalar random variables are denoted
in a lowercase sans-serif font, e.g., $\mathsf{x},\mathsf{k}$, while graph-
and set-valued random variables are denoted with uppercase sans-serif font,
e.g., $\mathsf{G},\mathsf{V},\mathsf{E}$. Expectation is denoted
$\mathbb{E}[\cdot]$, probability is denoted $\mathbb{P}(\cdot)$, and IID
refers to independent and identically distributed. Four probability
distributions are used: $i)$ $\mathrm{uni}(U)$ denotes a RV taking value
uniformly over $U$, $ii)$ $\mathrm{Ber}(p)$ denotes a Bernoulli RV with
parameter $p$, $iii)$ $\mathrm{bin}(n,p)$ denotes a binomial RV with
parameters $(n,p)$, and $iv)$ $\mathrm{geo}(p)$ denotes a geometric RV with
parameter $p$.

The following graph and sampling notation is used:

  * •

Order, size, edges. An undirected and simple graph of order $n$ is denoted
$G=(V,E)$, with vertex set $V\equiv[n]$ and edge set $E$; size is denoted by
$m\equiv|E|$. An edge is denoted $uv$.

  * •

Neighborhoods. Let $N_{G}(v)\equiv\\{u\in V:uv\in E\\}$ denote the (direct)
neighbors of $v$, $N_{G}^{e}(v)\equiv N_{G}(v)\cup\\{v\\}$ the extended
neighborhood of $v$, $\Gamma_{G}(v)\equiv\\{uv\in E\\}$ the edge neighborhood
of $v$, i.e., the edges adjacent to $v$, and

$\Gamma^{e}_{G}(v)\equiv\bigcup_{u\in N_{G}(v)}\Gamma_{G}(u),$ (1)

the extended edge neighborhood of $v$, i.e., all edges adjacent to $v$ or any
of $v$’s neighbors. Observe $N_{G}^{e}(v)$ is a star sample with star center
$v$ and star points $N_{G}(v)$. For $V^{*}\subseteq V$, let
$N_{G}(V^{*})\equiv(\bigcup_{v\in V^{*}}N_{G}(v))\setminus V^{*}$ denote
neighbors of $V^{*}$ not including $V^{*}$, and let
$N_{G}^{e}(V^{*})\equiv\bigcup_{v\in V^{*}}N_{G}^{e}(v)$ denote $V^{*}$ and
its neighbors.

  * •

Degrees. Let $d_{G}(v)\equiv|N_{G}(v)|$ denote the degree of $v$, and
$d_{G}^{e}(v)\equiv|N_{G}^{e}(v)|$ the “extended degree”, i.e.,
$d_{G}^{e}(v)=d_{G}(v)+1$. Let $D_{G}\equiv\bigcup_{v\in V}d_{G}(v)$ denote
the set of degrees found in $G$. Partition $V$ by degree into subsets
$(V_{G}(k),k\in D)$, with $V_{G}(k)\equiv\\{v\in V:d_{G}(v)=k\\}$ the set of
vertices with degree $k$ and $w_{G}(k)\equiv|V_{G}(k)|/n$ the fraction of
vertices with degree $k$, to obtain the degree distribution of $G$, denoted
$(w_{G}(k),k\in D)$ (with $\sum_{k\in D}w_{G}(k)=1$). The expected degree of a
randomly selected $\mathsf{v}\sim\mathrm{uni}(V)$ is

$d_{G}\equiv\mathbb{E}[d_{G}({\mathsf{v}})]=\sum_{k\in
D_{G}}kw_{G}(k)=\frac{1}{n}\sum_{v\in V}d_{G}(v).$ (2)

The notation in this subsection is summarized in Table II.

Notation | Description
---|---
$d_{G}(v)$ | degree of vertex $v$
$d_{G}^{e}(v)$ | extended degree of vertex $v$
$d_{G}$ | average degree of $G$, i.e., $\mathbb{E}[d_{G}(\mathsf{v})]$, for $\mathsf{v}\sim\mathrm{uni}(V)$
$E$ | edge set
$G$ | simple undirected graph
$\Gamma_{G}(v)$ | edge neighborhood of $v$
$\Gamma^{e}_{G}(v)$ | extended edge neighborhood of $v$
$m$ | graph size, $m=|E|$
$N_{G}(v)$ | neighbors of vertex $v$
$N_{G}(V^{*})$ | neighbors of target set $V^{*}$
$N^{e}_{G}(v)$ | extended neighbors of vertex $v$
$N^{e}_{G}(V^{*})$ | extended neighbors of target set $V^{*}$
$n$ | graph order, $n=|V|$
$n_{G}^{e,*}$ | order of the extended target set, $n_{G}^{e,*}=|N_{G}^{e}(V^{*})|$
$s$ | edge density, i.e., $s=|E|/\binom{n}{2}$
$uv$ | edge between vertices $u$ and $v$ is in $E$
$V$ | vertex set
$V^{*}$ | target set
$V_{G}(k)$ | set of vertices in $G$ of degree $k$
$w_{G}(k)$ | fraction of vertices in $G$ of degree $k$
TABLE II: Select notation from §III-A.

###  III-B Erdős Rényi (ER) graph properties

An Erdős-Rényi (ER) random graph $\mathsf{G}=(V,\mathsf{E})$ has parameters
$(n,s)$, where $n\in\mathbb{N}$ denotes the order, $V=[n]$, and $s\in(0,1)$
denotes the edge probability. A realization of an ER random graph, i.e., of
the random edge set $\mathsf{E}$, is obtained by including each of the
$\binom{n}{2}$ possible edges independently at random with probability $s$.
The random size of $\mathsf{G}$, denoted $\mathsf{m}\equiv|\mathsf{E}|$, is a
binomial RV, i.e., $\mathsf{m}\sim\mathrm{bin}(\binom{n}{2},s)$, as is the
degree $d_{\mathsf{G}}(\mathsf{v})$ of a randomly selected vertex
$\mathsf{v}\sim\mathrm{uni}(V)$, namely,
$d_{\mathsf{G}}(\mathsf{v})\sim\mathrm{bin}(n-1,s)$. The RV
$\mathsf{s}\equiv\mathsf{m}/\binom{n}{2}$ is the edge density (with
$\mathbb{E}[\mathsf{s}]=s$), and the RV
$\mathsf{d}\equiv(n-1)\mathsf{s}=2\mathsf{m}/n$ is the average degree of
$\mathsf{G}$. Given an ER graph $\mathsf{G}$, the RV $\mathsf{d}$ is the
expected degree of a vertex selected uniformly at random.

We focus our analysis of star sampling on ER graphs since they are closed
under both SSC and SSS, i.e., if either a star-center (SSC) or a star (SSS) is
removed from an ER graph the resulting graph is still an ER graph, albeit one
with a different (reduced) order. This follows intuitively from the fact that
the presence or absence of an edge is independent across edges, but is
established formally in Lem. 1 below.

######  Lemma 1.

Given an ER random graph, the graph that remains after an SSS or SSC random
sample is an ER random graph.

The proof is found in App. B.

###  III-C Sampling variant definitions and cost models

Random star sampling from a given graph $G=(V,E)$ produces a sequence of
random graphs, denoted $(\mathsf{G}_{t},t\in\mathbb{N})$, where
$\mathsf{G}_{t}=(\mathsf{V}_{t},\mathsf{E}_{t})$ is the random graph after
sample $t$. Both the vertex set and edge set are (in general) random
variables. It is convenient to denote the given graph as
$G_{0}=(V_{0},E_{0})$, i.e., the initial member of the list of random graphs,
corresponding to $t=0$. The target set is denoted by $V^{*}$ or $V_{0}^{*}$.
Define the sequence of random vertex sets
$(\mathsf{V}^{*}_{t},t\in\mathbb{N})$, where
$\mathsf{V}^{*}_{t}\equiv\mathsf{V}_{t}\cap V_{0}^{*}$ holds the members of
the initial target set still “alive” after $t$ samples. The sampling
construction ensures the random sets are nested:
$\mathsf{V}_{t+1}\subseteq\mathsf{V}_{t}$,
$\mathsf{E}_{t+1}\subseteq\mathsf{E}_{t}$, and
$\mathsf{V}^{*}_{t+1}\subseteq\mathsf{V}^{*}_{t}$. Recalling §I, the three SS
variants are as follows.

######  Definition 1.

SS with replacement (SSR). Generate the IID random sequence of star centers
$(\mathsf{v}_{t},t\in\mathbb{N})$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(V_{0})$. As SSR uses replacement,
$\mathsf{G}_{t}=G_{0}$ for all $t$.

######  Definition 2.

SS without center replacement (SSC). Generate the random sequence of star
centers $(\mathsf{v}_{t},t\in[n])$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(\mathsf{V}_{t-1})$, and update the graph by
removing the star center, i.e.,
$\mathsf{V}_{t}=\mathsf{V}_{t-1}\setminus\\{\mathsf{v}_{t}\\}$, and the edges
in the edge neighborhood of the star center, i.e.,
$\mathsf{E}_{t}=\mathsf{E}_{t-1}\setminus\Gamma_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})$.

######  Definition 3.

SS without star replacement (SSS). Generate the random sequence of star
centers $(\mathsf{v}_{t},t\in[n])$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(\mathsf{V}_{t-1})$, and update the graph by
removing the star, i.e., $\mathsf{V}_{t}=\mathsf{V}_{t-1}\setminus
N^{e}_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})$, and the edges in the extended edge
neighborhood of the star center, i.e.,
$\mathsf{E}_{t}=\mathsf{E}_{t-1}\setminus\Gamma^{e}_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})$.

Lem. 2 gives the expected number of edges removed from an ER graph under SSS.
Consider a star sample with star center $\mathsf{v}\sim\mathrm{uni}(V)$ of an
ER graph $\mathsf{G}$ with parameters $(n,s)$; recall $\mathsf{v}$ has degree
distribution $\mathsf{d}\sim\mathrm{bin}(n-1,s)$.

######  Lemma 2.

Given an ER random graph $\mathsf{G}$ with parameters $(n,s)$, a randomly
selected vertex $\mathsf{v}$ as star center, and conditioned on the degree
$\mathsf{d}$ of $\mathsf{v}$, the random number of edges in the extended edge
neighborhood of $\mathsf{v}$, denoted
$\mathsf{g}\equiv|\Gamma^{e}_{\mathsf{G}}(\mathsf{v})|$, has a binomial
distribution

$\mathsf{g}|\mathsf{d}\sim\mathsf{d}+\mathrm{bin}\left(\binom{\mathsf{d}}{2}+\mathsf{d}(n-\mathsf{d}-1),s\right),$
(3)

with (unconditional) expectation

$\mathbb{E}[\mathsf{g}]=(n-1)s(1+(n/2-1)(2-s)s).$ (4)

The asymptotic (in $n$) ratio of $\mathbb{E}[\mathsf{g}]$ to the expected
total number of edges in the graph $\binom{n}{2}s$ in the graph is
$\lim_{n\to\infty}\mathbb{E}[\mathsf{g}]/(\binom{n}{2}s)=(2-s)s$.

The proof is found in App. C. See Fig. 1 (left).

Figure 1: Left: expected fraction of ER graph edges in a star sample vs. edge
probability $s$, for $n\in\\{5,10,20,50\\}$ and $\lim n\uparrow\infty$, i.e.,
$(2-s)s$ (Lem. 2). Right: Expected fraction of vertices from an ER random
graph with parameters $(n=100,s)$ in the extended neighborhood, i.e.,
$n_{0}^{e,*}/n$ vs. the edge probability $s$, for
$n_{0}^{*}\in\\{1,2,5,10,20\\}$ (Fact 4).

The unit and linear costs for SS are defined below.

######  Definition 4.

The unit cost of a SS is the random number of samples until a star, either the
star center or one of the star points, intersects the target set $V^{*}$,
i.e.,

$\mathsf{c}_{u}(G,V^{*})\equiv\min\\{t\in\mathbb{N}:N^{e}_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})\cap
V^{*}\neq\emptyset\\}.$ (5)

This cost is a function of the sequence of random graphs
$(\mathsf{G}_{t},t\in\mathbb{N})$. The expected unit cost of a SS, denoted

$c_{u}(G,V^{*})\equiv\mathbb{E}[\mathsf{c}_{u}(G,V^{*})],$ (6)

is the expectation of $\mathsf{c}_{u}(G,V^{*})$, taken with respect to the
distribution over all possible realizations of graph sequences induced by SS
that begin with $G_{0}=G$.

######  Definition 5.

The linear cost of a SS is the random sum of the extended degrees of the
randomly selected vertex centers from each star sample until a star, either
the star center or one of the star points, intersects the target set $V^{*}$,
i.e.,

$\mathsf{c}_{l}(G,V^{*})\equiv\sum_{t=1}^{\mathsf{c}_{u}(G,V^{*})}d_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t}).$
(7)

This cost is a function of the sequence of random graphs
$(\mathsf{G}_{t},t\in\mathbb{N})$. The expected linear cost of a SS, denoted

$c_{l}(G,V^{*})\equiv\mathbb{E}[\mathsf{c}_{l}(G,V^{*})],$ (8)

is the expectation of $\mathsf{c}_{l}(G,V^{*})$, taken with respect to the
distribution over all possible realizations of graph sequences induced by SS
that begin with $G_{0}=G$.

##  IV Unit cost model

Expected unit costs of SSR and SSC are given in §IV-A and the expected unit
cost of SSS is given in §IV-B. Exact results in §IV-A are given for an
arbitrary graph and as bounds for ER random graphs, while approximate results
in §IV-B are only given for ER random graphs. §IV-C gives numerical results.

###  IV-A Unit cost analysis for SSR and SSC

Let $G=(V,E)$ be an arbitrary graph of order $n$, and let $V^{*}\subseteq V$
be an arbitrary target set. Recall from §III-A that $N^{e}_{G}(V^{*})$
contains the target set $V^{*}$ and its neighbors in $G$. Observe the
equivalence: a star sample $N^{e}_{G}(v)$ intersects $V^{*}$ if and only if
$v\in N^{e}_{G}(V^{*})$. This observation yields the expected unit cost of SSR
and SSC. Set $n^{e,*}_{G}\equiv|N^{e}_{G}(V^{*})|$.

######  Fact 2 (Unit cost of SSR).

Under SSR, for any graph $G$ and any target set $V^{*}$, the unit cost
$\mathsf{c}_{u}$ in Def. 4 is a geometric RV with success probability
$n^{e,*}_{G}/n$, i.e., $\mathsf{c}_{u}^{\rm
SSR}\sim\mathrm{geo}(n^{e,*}_{G}/n)$, and the expected unit cost is
$c_{u}^{\rm SSR}=n/n^{e,*}_{G}$.

###### Proof:

SSR unit cost is the random number of independent Bernoulli trials until the
first “success”, i.e., the random star intersects the target set
(equivalently, the random star center intersects the target set extended
neighborhood). ∎

######  Fact 3 (Unit cost of SSC).

Under SSC, for any graph $G$ and any target set $V^{*}$, the expected unit
cost $c_{u}^{\rm SSC}$ in Def. 4 is $c_{u}^{\rm SSC}=(n+1)/(n^{e,*}_{G}+1)$.

###### Proof:

SSC with target set $V^{*}$ on a graph $G$ with extended neighborhood
$N^{e}_{G}(V^{*})$ is equivalent to sampling without replacement from an urn
with $n$ balls, of which $n^{e,*}_{G}$ are marked, until a marked ball is
drawn. The expected number of samples is $(n+1)/(n^{e,*}_{G}+1)$ by Fact 1. ∎

Fact 2 and Fact 3 show the expected number of SSR samples exceeds the expected
number of SSC samples: $c_{u}^{\rm SSR}>c_{u}^{\rm SSC}$.

We now adapt the previous two facts to the case where the initial graph is an
ER random graph $\mathsf{G}_{0}=(V_{0},\mathsf{E}_{0})$ with parameters
$(n,s)$, and where the expectation is with respect to both the graph and
sampling distributions. Define the RVs:

  * •

$\mathsf{n}_{t}\equiv|\mathsf{V}_{t}|$: order of graph $\mathsf{G}_{t}$ (note
$n_{0}=n$);

  * •

$\mathsf{n}_{t}^{*}\equiv|\mathsf{V}_{t}^{*}|$: number of vertices from the
target set in $\mathsf{G}_{t}$;

  * •

$\mathsf{n}_{t}^{e,*}\equiv|\mathsf{V}_{t}^{e,*}|$ (where
$\mathsf{V}_{t}^{e,*}\equiv N_{\mathsf{G}_{t}}^{e}(\mathsf{V}_{t}^{*})$):
number of vertices in extended neighborhood of target set in $\mathsf{G}_{t}$.

######  Fact 4.

The random order of the extended neighborhood of the target set in the ER
random graph $\mathsf{G}_{0}$ is a binomial RV:

$\mathsf{n}_{0}^{e,*}\sim
n_{0}^{*}+\mathrm{bin}(n-n_{0}^{*},1-\bar{s}^{n_{0}^{*}}).$ (9)

Define $n_{0}^{e,*}\equiv\mathbb{E}[\mathsf{n}_{0}^{e,*}]$, where

$\displaystyle\mathbb{E}[\mathsf{n}_{0}^{e,*}]$ $\displaystyle=$
$\displaystyle n_{0}^{*}+(n-n_{0}^{*})(1-\bar{s}^{n_{0}^{*}}),$
$\displaystyle\mathrm{var}(\mathsf{n}_{0}^{e,*})$ $\displaystyle=$
$\displaystyle(n-n_{0}^{*})\bar{s}^{n_{0}^{*}}(1-\bar{s}^{n_{0}^{*}}).$ (10)

###### Proof:

Each $v\in V_{0}\setminus V_{0}^{*}$ is connected to $V_{0}^{*}$
(independently of other vertices) if there exists an edge (or edges) from $v$
to $V_{0}^{*}$, which happens with probability $1-\bar{s}^{n_{0}^{*}}$. ∎

Fig. 1 (right) shows $n_{0}^{e,*}/n$, the expected fraction of vertices in the
extended target set (Fact 4), vs. the edge probability $s$.

The next result, from [16], is leveraged in Prop. 1 below.

######  Fact 5 (Bounds on inverse moments, [16] (Eq. 3.1, p. 729)).

Let a random variable $\mathsf{x}$ have mean $\mu$, variance $\sigma^{2}$, and
minimum support $x_{\rm min}>0$ (i.e., $\mathbb{P}(\mathsf{x}\geq x_{\rm
min})=1$). Then

$\frac{1}{\mu}\leq\mathbb{E}\left[\frac{1}{\mathsf{x}}\right]\leq\frac{1}{x_{\rm
min}}\frac{\sigma^{2}+(\mu-x_{\rm min})x_{\rm min}}{\sigma^{2}+(\mu-x_{\rm
min})\mu}.$ (11)

Specializing (11) to a binomial RV $\mathsf{x}\sim\mathrm{bin}(m,p)$, for
$a>0$:

$\frac{1}{a+mp}\leq\mathbb{E}\left[\frac{1}{a+\mathsf{x}}\right]\leq\frac{a+1-p}{a(a+1+(m-1)p)}.$
(12)

######  Proposition 1 (Unit cost of SSR and SSC for ER graph).

Fix the initial graph as an ER random graph $\mathsf{G}_{0}$ with parameters
$(n,s)$. The expected unit cost under SSR and SSC has bounds

$\underline{c}_{u}^{\rm SSR}\leq c_{u}^{\rm SSR}\leq\bar{c}_{u}^{\rm
SSR},~{}~{}\underline{c}_{u}^{\rm SSC}\leq c_{u}^{\rm SSC}\leq\bar{c}_{u}^{\rm
SSC}.$ (13)

Let the target set $V_{0}^{*}\subseteq V_{0}$ have cardinality
$n_{0}^{*}=|V_{0}^{*}|$:

$\displaystyle\underline{c}_{u}^{\rm SSR}$ $\displaystyle\equiv$
$\displaystyle\frac{n}{n-\bar{s}^{n_{0}^{*}}(n-n_{0}^{*})}$
$\displaystyle\bar{c}_{u}^{\rm SSR}$ $\displaystyle\equiv$
$\displaystyle\frac{n(\bar{s}^{n_{0}^{*}}+n_{0}^{*})}{n^{*}_{0}(n-\bar{s}^{n_{0}^{*}}(n-1-n_{0}^{*}))}$
$\displaystyle\underline{c}_{u}^{\rm SSC}$ $\displaystyle\equiv$
$\displaystyle\frac{n+1}{n+1-\bar{s}^{n_{0}^{*}}(n-n_{0}^{*})}$
$\displaystyle\bar{c}_{u}^{\rm SSC}$ $\displaystyle\equiv$
$\displaystyle\frac{(n+1)(\bar{s}^{n_{0}^{*}}+1+n_{0}^{*})}{(n_{0}^{*}+1)(n+1-\bar{s}^{n_{0}^{*}}(n-1-n_{0}^{*}))}.$
(14)

###### Proof:

Using Fact 2, the SSR bounds are derived by applying (12) in Fact 5 to
$n\mathbb{E}[1/\mathsf{n}_{0}^{e,*}]$, for $\mathsf{n}_{0}^{e,*}$ in (9) of
Fact 4, i.e., with $a=n_{0}^{*}$, $m=n-n_{0}^{*}$, and
$p=1-\bar{s}^{n_{0}^{*}}$. Using Fact 3, the SSC bounds are derived by
applying (12) in Fact 5 to $(n+1)\mathbb{E}[1/(\mathsf{n}_{0}^{e,*}+1)]$,
i.e., with $a=n_{0}^{*}+1$, $m=n-n_{0}^{*}$, and $p=1-\bar{s}^{n_{0}^{*}}$. ∎

###  IV-B Unit cost analysis for SSS

Let $(\mathsf{y},\mathsf{z})$ be a pair of continuous RVs, with
$\mathsf{z}\neq 0$ almost surely, means $(\mu_{\mathsf{y}},\mu_{\mathsf{z}})$,
variances $(\sigma^{2}_{\mathsf{y}},\sigma^{2}_{\mathsf{z}})$, and covariance
$\mathrm{cov}(\mathsf{y},\mathsf{z})$. Consider the expectation of their
ratio, i.e., $\mathbb{E}\left[\frac{\mathsf{y}}{\mathsf{z}}\right]$. The
following result is found in [17] and [18].

######  Proposition 2 ([17], [18]).

The second order Taylor series approximation of
$\mathbb{E}\left[\frac{\mathsf{y}}{\mathsf{z}}\right]$ around
$(\mu_{\mathsf{y}},\mu_{\mathsf{z}})$ is

$\mathbb{E}\left[\frac{\mathsf{y}}{\mathsf{z}}\right]\approx\frac{\mu_{\mathsf{y}}}{\mu_{\mathsf{z}}}+\frac{\sigma_{\mathsf{z}}^{2}\mu_{\mathsf{y}}}{\mu_{\mathsf{z}}^{3}}-\frac{\mathrm{cov}(\mathsf{y},\mathsf{z})}{\mu_{\mathsf{z}}^{2}}.$
(15)

In particular, the error associated with a first-order Taylor series
approximation is, to second order,

$\epsilon_{1}\equiv\left|\mathbb{E}\left[\frac{\mathsf{y}}{\mathsf{z}}\right]-\frac{\mu_{\mathsf{y}}}{\mu_{\mathsf{z}}}\right|\leq\left|\frac{\sigma_{\mathsf{z}}^{2}\mu_{\mathsf{y}}}{\mu_{\mathsf{z}}^{3}}-\frac{\mathrm{cov}(\mathsf{y},\mathsf{z})}{\mu_{\mathsf{z}}^{2}}\right|.$
(16)

This fact will be leveraged in Thm. 1 below.

Let the initial graph be an ER random graph
$\mathsf{G}_{0}=(V_{0},\mathsf{E}_{0})$ with parameters $(n,s)$. Recall a star
will hit the target set if its star center is in the extended neighborhood of
the target. The (random) probability that star $t+1$ hits the target set is

$\mathsf{p}_{t+1}^{\rm SSS}\equiv\frac{\mathsf{n}^{e,*}_{t}}{\mathsf{n}_{t}}.$
(17)

Define events $(\mathcal{E}_{t},t\in\mathbb{Z}^{+})$, with $\mathcal{E}_{0}$
trivial, and
$\mathcal{E}_{t}\equiv\left\\{\mathsf{v}_{t}\not\in\mathsf{V}^{e,*}_{t-1})\right\\}$
the event that star $t$ misses the target set. Next, define events
$(\bar{\mathcal{E}}_{t},t\in\mathbb{Z}^{+})$, with $\bar{\mathcal{E}}_{0}$
trivial, and

$\bar{\mathcal{E}}_{t}\equiv\bigcap_{t^{\prime}\in[t]}\mathcal{E}_{t^{\prime}}=\left\\{\mathsf{v}_{t^{\prime}}\not\in\mathsf{V}^{e,*}_{t^{\prime}-1},~{}\forall
t^{\prime}\in[t]\right\\}.$ (18)

Thus, $\bar{\mathcal{E}}_{t}$ is the event that the stars of the first $t$
samples have each missed the target set. Observe that, conditioned on
$\bar{\mathcal{E}}_{t}$, the target set in graph $\mathsf{G}_{t}$ is identical
to the same set in the initial graph $\mathsf{G}_{0}$, i.e.,
$\mathsf{V}^{*}_{t}|\bar{\mathcal{E}}_{t}=V_{0}^{*}$, although the degrees of
vertices in $V_{0}^{*}$ may have decreased due to sampling.

The expected probability of hitting the target with star $t+1$, conditioned on
missing the target set in the first $t$ samples, is:

$\mathbb{E}[\mathsf{p}_{t+1}^{\rm
SSS}|\bar{\mathcal{E}}_{t}]=\mathbb{E}\left[\left.\frac{\mathsf{n}^{e,*}_{t}}{\mathsf{n}_{t}}\right|\bar{\mathcal{E}}_{t}\right].$
(19)

Leveraging (16), the error in approximating this expected conditional
probability by its ratio of expectations, i.e.,

$\tilde{p}_{t+1}^{\rm
SSS}\equiv\frac{\mathbb{E}[\mathsf{n}^{e,*}_{t}|\bar{\mathcal{E}}_{t}]}{\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]},$
(20)

is approximately

$\epsilon_{n,t}\equiv\left|\frac{\mathrm{var}(\mathsf{n}_{t}|\bar{\mathcal{E}}_{t})\mathbb{E}[\mathsf{n}^{e,*}_{t}|\bar{\mathcal{E}}_{t}]}{\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]^{3}}-\frac{\mathrm{cov}(\mathsf{n}^{e,*}_{t},\mathsf{n}_{t}|\bar{\mathcal{E}}_{t})}{\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]^{2}}\right|.$
(21)

This approximate conditional hitting probability and its approximation error
are expressed in terms of the three fundamental parameters $(n,n_{0}^{*},s)$
and the sample index $t$ in Thm. 1.

######  Theorem 1.

The approximate probability of hitting the target set in sample $t+1$ under
SSS, conditioned on missing it in the first $t$ samples, is (for
$n_{0}^{e,*}\equiv\mathbb{E}[\mathsf{n}_{0}^{e,*}]$ in Fact 4 (4)):

$\tilde{p}_{t+1}^{\rm
SSS}=\frac{(n_{0}^{e,*}-n_{0}^{*})\bar{s}^{t}+n_{0}^{*}}{n\bar{s}^{t}-\frac{\bar{s}}{s}(1-\bar{s}^{t})}.$
(22)

Viewing $\tilde{p}_{t+1}^{\rm SSS}$ as a continuous function of $t$,
$\tilde{p}_{t+1}^{\rm SSS}$ is convex increasing in $t$ over
$t\in[0,t^{(2)}_{\tilde{p}})$, where

$t^{(2)}_{\tilde{p}}\equiv\frac{\log\left(n\frac{s}{\bar{s}}+1\right)}{\log(1/\bar{s})}.$
(23)

Moreover, $\tilde{p}_{1}^{\rm SSS}$ (hitting in the first sample) equals the
exact value $p_{1}^{\rm SSS}\equiv n^{e,*}_{0}/n$, and $\tilde{p}_{t+1}^{\rm
SSS}=1$ at

$t^{(1)}_{\tilde{p}}\equiv\frac{\log\left(s(n-\mathbb{E}[\mathsf{n}_{0}^{e,*}]+n^{*}_{0})+\bar{s}\right)-\log\left(\bar{s}+n^{*}_{0}s\right)}{\log(1/\bar{s})}<t^{(2)}_{\tilde{p}}.$
(24)

The error in this approximation, $\epsilon_{n,t}$, has upper bound

$\left(n(1-\bar{s}^{t})+\frac{\bar{s}(1+\bar{s}(1-\bar{s}^{t}))}{s(1+\bar{s})}\right)\frac{\bar{s}^{t}((n_{0}^{e,*}-n_{0}^{*})\bar{s}^{t}+n_{0}^{*})}{\left(n\bar{s}^{t}-\frac{\bar{s}}{s}(1-\bar{s}^{t})\right)^{3}}.$
(25)

The approximation error is asymptotically negligible in $n$:

$\lim_{n\uparrow\infty}\epsilon_{n,t}=0,~{}\forall t\in\mathbb{N},s\in(0,1).$
(26)

and in fact $\epsilon_{n,t}=O(n_{0}^{e,*}/n^{2})$.

The proof is found in App. E. Fig. 2 (top left) shows $\tilde{p}_{t}^{\rm
SSS}$ from (22) vs. the sample index $t$. Note the curves are convex
increasing even on a logarithmic scale, i.e., $\tilde{p}_{t}^{\rm SSS}$ is
log-convex.

Figure 2:  Top left: Thm. 1: approximate conditional probability of first
hitting the target in an ER graph with parameters $(n=100,s)$ at sample $t$,
conditioned on not yet hitting it, under SSS, i.e., $\tilde{p}_{t}^{\rm SSS}$
from (22), vs. $t$, for $n_{0}^{*}=2$ and
$s\in\\{0.0001,0.0005,0.001,0.005,0.01\\}$. Horizontal lines show $p_{1}^{\rm
SSS}\equiv n^{e,*}_{0}/n$ and vertical lines show $t^{(1)}_{\tilde{p}}$ from
(24). Top right: Thm. 2: approximate unconditional probability of first
hitting the target in an ER graph with parameters $(n=100,s)$ at sample $t$
under SSS, i.e., $\tilde{q}_{t}^{\rm SSS}$ from (27), vs. $t$, for
$n_{0}^{*}=2$ and $s\in\\{0.0001,0.0005,0.001,0.005,0.01\\}$. Vertical lines
show $t^{(1)}_{\tilde{p}}$ from (24). Bottom: Prop. 3: three conditional
probability ratios vs. graph order $n$, for $t\in\\{2,8\\}$ ($n_{0}^{*}=2$,
$s(n)=1/n$).

The approximate unconditional hitting probability $\tilde{q}_{t}^{\rm SSS}$
and the corresponding approximate expected unit cost under SSS for an ER graph
$\tilde{c}_{u}^{\rm SSS}$ are expressed in terms of the three fundamental
parameters $(n,n_{0}^{*},s)$ in Thm. 2.

Let the RV $\tilde{\mathsf{c}}_{u}^{\rm SSS}$ have distribution
$\tilde{q}^{\rm SSS}\equiv(\tilde{q}_{t}^{\rm
SSS},t\in[t_{\tilde{p}}^{(1)}])$, so that the approximate expected unit cost
is the expectation of this RV with respect to that distribution:
$\tilde{c}_{u}^{\rm SSS}\equiv\mathbb{E}[\tilde{\mathsf{c}}_{u}^{\rm SSS}]$.

######  Theorem 2.

The approximate unconditional probability of first hitting the target set in
sample $t$ under SSS is

$\tilde{q}_{t}^{\rm SSS}\equiv\tilde{p}_{t}^{\rm
SSS}\prod_{u\in[t-1]}(1-\tilde{p}_{u}^{\rm SSS}),$ (27)

for $t\in[\lfloor t_{\tilde{p}}^{(1)}\rfloor]$, with $t_{\tilde{p}}^{(1)}$
defined in (24). The associated approximate expected unit cost under SSS is

$\tilde{c}_{u}^{\rm
SSS}\equiv\sum_{t\in[t_{\tilde{p}}^{(1)}]}\prod_{u\in[t]}(1-\tilde{p}_{u}^{\rm
SSS}).$ (28)

The proof is found in App. F. Fig. 2 (top right) shows $\tilde{q}_{t}^{\rm
SSS}$ from (27) vs. the sample index $t$. As $s$ increases the distribution
support decreases and the distribution slope decreases.

The last result in this section, Prop. 3, considers the parameter regime where
the ER edge probability $s$ is $O(1/n)$. Let

$p_{t}^{\rm SSR}=\frac{n_{0}^{e,*}}{n},~{}p_{t}^{\rm
SSC}=\frac{n_{0}^{e,*}}{n-t+1}$ (29)

be the conditional probabilities of hitting the target set for the first time
on sample $t$ under SSR and SSC, respectively.

######  Proposition 3.

Set the ER edge probability $s(n)=c/n$ (with $c>0$), and fix $t$ and
$n_{0}^{*}$. The conditional probability of hitting the target set in sample
$t$ (conditioned on not yet having hit it) is, asymptotically as
$n\uparrow\infty$, equal for all three SS variants:

$\frac{\tilde{p}_{t}^{\rm SSS}}{p_{t}^{\rm SSR}}\to 1,\;\frac{p_{t}^{\rm
SSR}}{p_{t}^{\rm SSC}}\to 1,\;\frac{\tilde{p}_{t}^{\rm SSS}}{p_{t}^{\rm
SSC}}\to 1.$ (30)

The proof is found in App. G. Fig. 2 (bottom) shows all three conditional
probability ratios in Prop. 3 vs. the graph order $n$, for $n_{0}^{*}=2$ and
$s(n)=c/n$ with $c=1$ for $t\in\\{2,8\\}$. The convergence of all three ratios
to $1$ as $n\uparrow\infty$ is evident.

###  IV-C Numerical results

The four plots in Fig. 3 show numerical and simulation results for the
expected unit cost to find $v\in V^{*}$ (with $n_{0}^{*}=2$) under SSR, SSC,
and SSS on ER random graphs with order $n=1,000$ vs. the edge density $s$ (on
a log scale). Three conclusions are evident from the plots. First, the bounds
on SSR (Prop. 1, top left plot) and SSC (Prop. 1, top right plot) are “tight”
and the approximation for SSS (Thm. 1, bottom left plot) is “accurate”.
Second, the average unit cost ordering on ER graphs is $c_{u}^{\rm SSR}\geq
c_{u}^{\rm SSC}\geq c_{u}^{\rm SSS}$ (bottom right plot). Third, there is a
notable difference in unit cost between SSR and SSC/SSS for “small” $s$, but
no appreciable difference among the three sampling schemes for “large” $s$
(bottom right plot).

Figure 3: Numerical and simulation results for expected unit cost on ER random
graphs with order $n=1,000$ and target size $n_{0}^{*}=2$ vs. edge density $s$
(on log scale). Top left: SSR bounds and simulation. Top right: SSC bounds and
simulation. Bottom left: SSC approximation and simulation. Bottom right:
simulation results for SSR, SSC, SSS.

##  V Linear Cost Model

The expected linear cost (Def. 5) of SSR on an arbitrary graph is given in
§V-A. Approximate expected linear costs of SSR, SSC, and SSS on an ER random
graph are given in §V-B. Numerical results are presented in §V-C.

###  V-A Arbitrary graph

Let $G=(V,E)$ be an arbitrary graph with order $|V|=n$, and let
$V^{*}\subseteq V$ be an arbitrary target set. Fact 6 below is the linear cost
analog of the unit cost result for SSR in Fact 2.

We first develop some necessary notation, extending that introduced in §III-A.
Let $V^{e,*}_{G}=N_{G}^{e}(V^{*})$ denote the extended neighborhood of $V^{*}$
(with order $n^{e,*}_{G}\equiv|V^{e,*}_{G}|$), and let
$\bar{V}^{e,*}_{G}\equiv V\setminus V^{e,*}_{G}$ denote its complement. Define
$V^{e,*}_{G}(k)\equiv\\{v\in V^{e,*}_{G}:d_{G}(v)=k\\}$ and
$\bar{V}^{e,*}_{G}(k)\equiv\\{v\in\bar{V}^{e,*}_{G}:d_{G}(v)=k\\}$ as the
subsets of vertices in $V^{e,*}_{G},\bar{V}^{e,*}_{G}$, respectively, of
degree $k$. The conditional degree distributions in
$V^{e,*}_{G},\bar{V}^{e,*}_{G}$ are denoted $w^{e,*}_{G},\bar{w}^{e,*}_{G}$,
respectively, with components

$w^{e,*}_{G}(k)\equiv\frac{|V^{e,*}_{G}(k)|}{|V^{e,*}_{G}|},~{}\bar{w}^{e,*}_{G}(k)\equiv\frac{|\bar{V}^{e,*}_{G}(k)|}{|\bar{V}^{e,*}_{G}|}.$
(31)

Finally, the average degrees in $V^{e,*}_{G},\bar{V}^{e,*}_{G}$, respectively,
are

$d^{e,*}_{G}=\sum_{k\in
D^{e,*}_{G}}kw^{e,*}_{G}(k),~{}\bar{d}^{e,*}_{G}=\sum_{k\in\bar{D}^{e,*}_{G}}k\bar{w}^{e,*}_{G}(k).$
(32)

######  Fact 6 (Linear cost of SSR).

Under SSR, for any graph $G$ and any target set $V^{*}$, the expected linear
cost $c_{l}$ in (8) is

$c_{l}^{\rm
SSR}(G,V^{*})=\bar{d}^{e,*}_{G}\left(\frac{n}{n^{e,*}_{G}}-1\right)+d^{e,*}_{G}.$
(33)

The proof is found in App. H.

Despite the success in deriving the previous result for SSR, we are of the
impression that a simple exact expression for the expected linear cost under
SSC on an arbitrary graph is not available. In contrast to the unit cost case,
for which the SSC expected unit cost is given by Fact 3, the linear cost case
appears to be much more difficult to analyze, as it requires a representation
of the evolution under SSC of the (effectively arbitrary) degree distribution
$w_{G}$ of the initial graph $G$. This evolution does not appear to be
sufficiently tractable to yield “closed-form” results like those in §IV-A.
Given this difficulty, we turn to approximations for the case of an ER random
graph.

###  V-B ER random graph

Let the initial graph be an ER random graph
$\mathsf{G}_{0}=(V_{0},\mathsf{E}_{0})$ with parameters $(n,s)$. Expectations
below are taken with respect to the graph and sampling distributions. The
starting point for all three sampling paradigms is to express the expected
linear cost in terms of the conditional expectations of the extended degrees
of each sampled vertex, conditioned on the unit cost, and to approximate the
per-sample extended degree as independent of the unit cost:

$\displaystyle c_{l}$ $\displaystyle\equiv$
$\displaystyle\mathbb{E}[\mathsf{c}_{l}]=\mathbb{E}\left[\sum_{t\in[c_{\rm
max}]}\mathsf{d}^{e}_{t}\mathbf{1}(t\leq\mathsf{c}_{u})\right]$
$\displaystyle=$ $\displaystyle\sum_{t\in[c_{\rm
max}]}\mathbb{E}[\mathsf{d}^{e}_{t}\mathbf{1}(t\leq\mathsf{c}_{u})]\approx\sum_{t\in[c_{\rm
max}]}\mathbb{E}[\mathsf{d}^{e}_{t}]\mathbb{P}(t\leq\mathsf{c}_{u}).$

Here, $\mathsf{d}^{e}_{t}$ is the extended degree of sample $t$,
$\mathsf{c}_{u}$ is the unit cost, i.e., the random number of samples required
for the star center to hit the extended target set, and $c_{\rm max}$ is an
upper bound, possibly infinite, on $\mathsf{c}_{u}$. The extended degree is
not independent of the number of samples, as the target set in
$\mathsf{G}_{t}$ will have a distinct degree distribution from its complement,
conditioned on the previous $t-1$ samples missing the target. Nonetheless, the
approximation is useful in that it facilitates analysis and our numerical
investigations support our claim that the approximation is accurate over a
wide array of parameter values. Below, we adapt the above approximation to
give the approximate expected linear cost conditioned on the random extended
target set, $\mathsf{n}_{0}^{e,*}$, i.e.,

$\mathbb{E}[\tilde{\mathsf{c}}_{l}|\mathsf{n}_{0}^{e,*}]\approx\tilde{\mathbb{E}}[\tilde{\mathsf{c}}_{l}|\mathsf{n}_{0}^{e,*}]\equiv\sum_{t\in[c_{\rm
max}(\mathsf{n}_{0}^{e,*})]}\mathbb{E}[\mathsf{d}^{e}_{t}]\mathbb{P}(t\leq\mathsf{c}_{u}|\mathsf{n}_{0}^{e,*}).$
(35)

The additional approximation in (35), beyond the one in (V-B), is that
$\mathsf{d}^{e}_{t}$ is independent of $\mathsf{n}_{0}^{e,*}$, i.e.,
$\mathbb{E}[\mathsf{d}^{e}_{t}|\mathsf{n}_{0}^{e,*}]=\mathbb{E}[\mathsf{d}^{e}_{t}]$.

####  V-B1 SSR

In the case of SSR, the approximation in (35) leads to a particularly simple
expression on account of the fact that $(\mathsf{d}^{e}_{t})$ are IID, i.e.,
$\mathbb{E}[\mathsf{d}^{e}_{t}]$ does not depend upon $t$, and as such Wald’s
identity for the expected value of the sum of a random number of IID RVs
applies:

$\displaystyle\tilde{\mathbb{E}}[\tilde{\mathsf{c}}_{l}^{\rm
SSR}|\mathsf{n}_{0}^{e,*}]$ $\displaystyle=$
$\displaystyle\mathbb{E}[\mathsf{d}^{e}_{1}]\sum_{t\in[c_{\rm max}^{\rm
SSR}(\mathsf{n}_{0}^{e,*})]}\mathbb{P}(t\leq\mathsf{c}_{u}|\mathsf{n}_{0}^{e,*})$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathsf{d}^{e}_{1}]\mathbb{E}[\mathsf{c}_{u}|\mathsf{n}_{0}^{e,*}]=(1+(n-1)s)\frac{n}{\mathsf{n}_{0}^{e,*}}.$

Here, $\mathbb{E}[\mathsf{d}^{e}_{1}]=1+(n-1)s$ is the expected extended
degree of a random vertex in an ER random graph, and
$\mathbb{E}[\mathsf{c}_{u}|\mathsf{n}_{0}^{e,*}]=n/\mathsf{n}_{0}^{e,*}$ is
the conditional expected unit cost of SSR. Taking expectation with respect to
$\mathsf{n}_{0}^{e,*}$ yields the following.

######  Proposition 4 (SSR linear cost for ER graph.).

Fix the initial graph as an ER random graph $\mathsf{G}_{0}$ with parameters
$(n,s)$, and the extended target set cardinality $\mathsf{n}_{0}^{e,*}$. The
approximate expected linear cost under SSR, $\tilde{c}_{l}^{\rm SSR}$, is

$\tilde{c}_{l}^{\rm
SSR}\equiv\mathbb{E}[\mathbb{E}[\tilde{\mathsf{c}}_{l}^{\rm
SSR}|\mathsf{n}_{0}^{e,*}]]=(1+(n-1)s)c_{u}^{\rm SSR},$ (37)

and the SSR expected unit cost, $c_{u}^{\rm SSR}$, has bounds in Prop. 1.

####  V-B2 SSC

Leveraging the approximation (35) for SSC requires the expected extended
degree of the random star center selected in sample $t$ and the hitting
probability for sample $t$.

######  Proposition 5 (SSC linear cost for ER graph.).

The approximate expected linear cost under SSC for an ER graph, conditioned on
the random extended target set order $\mathsf{n}^{e,*}_{0}$, is

$\mathbb{E}[\tilde{\mathsf{c}}_{l}^{\rm
SSC}|\mathsf{n}^{e,*}_{0}]=\sum_{t=1}^{n-\mathsf{n}^{e,*}_{0}+1}(1+(n-t)s)\prod_{u=1}^{t-1}\left(1-\frac{\mathsf{n}^{e,*}_{0}}{n-u+1}\right).$
(38)

The proof is found in App. I.

####  V-B3 SSS

As with SSC, leveraging the approximation (35) for SSS requires the expected
extended degree of the random star center selected in sample $t$ and the
approximate conditional hitting probability for sample $t$.

######  Proposition 6 (SSS linear cost for ER graph.).

The approximate expected linear cost under SSS for an ER graph, conditioned on
the random extended target set order $\mathsf{n}^{e,*}_{0}$, is

$\mathbb{E}[\tilde{\mathsf{c}}_{l}^{\rm
SSS}|\mathsf{n}^{e,*}_{0}]=\sum_{t=1}^{t^{(1)}_{\tilde{p}}}((n-1)s+1)\bar{s}^{t-1}\prod_{u=1}^{t-1}\left(1-\tilde{p}_{u}^{\rm
SSS}\right),$ (39)

where $t^{(1)}_{\tilde{p}}$ (c.f. (24)) and $\tilde{p}_{t}^{\rm SSS}$ (c.f.
(22)) are defined in Thm. 1.

The proof is found in App. J.

###  V-C Numerical results

The four plots in Fig. 4 show numerical and simulation results for the
expected linear cost to find $v\in V^{*}$ (with $n_{0}^{*}=2$) under SSR, SSC,
and SSS on ER random graphs with order $n=1,000$ vs. the edge density $s$ (on
a log scale). Three conclusions are evident from the plots. First, the bounds
on SSR (Prop. 4, top left plot) are not as tight as for the unit cost case,
but both bounds are tight for separate ranges of values of $s$, and the
approximation for SSC (Prop. 5, top right plot) and SSS (Prop. 6, bottom left
plot) are “accurate”. Second, the average linear cost ordering on ER graphs is
$c_{l}^{\rm SSR}\geq c_{l}^{\rm SSC}\geq c_{l}^{\rm SSS}$ (bottom right plot),
as was true for unit cost. Third, there is a notable difference in linear cost
between SSR and SSC/SSS for “small” $s$, and a notable difference between
SSR/SSC and SSS for “large” $s$ (bottom right plot).

Figure 4: Numerical and simulation results for expected linear cost on ER
random graphs with order $n=1,000$ and target size $n_{0}^{*}=2$ vs. edge
density $s$ (on log scale). Top left: SSR bounds and simulation. Top right:
SSC approximation and simulation. Bottom left: SSC approximation and
simulation. Bottom right: simulation results for SSR, SSC, SSS.

##  VI Results on “real-world” graphs

This section assesses the accuracy when the SSR, SSC, and SSS unit and linear
cost estimates, derived for ER graphs in §IV and §V, are applied to twelve
“real-world” graphs. These graphs come from a variety of sources: power-
network is from [19]; condMat, gnutella08, gnutella04, web-google, astroPh,
epinions, fb-combined, oregon1, and brightkite are from the SNAP repository
[20]; while the web-edu and tech-routers are from the network data repository
[21].

Table III gives statistics for these graphs, including order $n\equiv|V|$,
size $m\equiv|E|$, edge density $s\equiv m/\binom{n}{2}$, assortativity
$\alpha$ (the correlation of the degrees of a randomly selected edge), and
maximum degree $d_{\rm max}\equiv\max D$.

Table IV and Table V present empirical and estimated costs, unit and linear
respectively, on these graphs under SSR, SSC, and SSS, assuming $n_{0}^{*}=4$,
and assuming $\mathsf{n}_{0}^{e,*}$ is known. Simulation results are presented
as a $95\%$ confidence interval after $1,000$ independent trials. The percent
relative error between the simulation mean cost and the estimated expected
cost are given for all three sampling variants. The relative error column
entries are bolded when the estimate does not lie in the $95\%$ confidence
interval from simulation.

Several comments bear mention. First, the SSR and SSC approximations are
remarkably accurate, all within $5\%$ relative error. Second, the SSS
approximations, while less accurate than SSR and SSC, are still remarkably
accurate given $i)$ these graphs are quite different from one another and
quite different from an ER graph, and $ii)$ the approximate costs require so
few summary statistics about the graph, i.e., $(n,n_{0}^{*},s)$. Both unit and
linear SSS relative errors are all under $30\%$, several having much smaller
relative error, aside from the $~{}60\%$ error for epinions1 (unit) and
oregon1 (linear).

Graph | $n$ | $m$ | $s$ | $\alpha$ | $d_{\rm max}$
---|---|---|---|---|---
astroPh | 18,772 | 198,110 | 0.00110 | 0.21 | 504
brightkite | 58,228 | 214,078 | 0.00013 | 0.11 | 1134
condMat | 23,133 | 93,497 | 0.00350 | 0.14 | 281
epinions | 75,879 | 405,740 | 0.00014 | -0.04 | 3044
fb-combined | 4,039 | 88,234 | 0.01100 | 0.06 | 1045
gnutella04 | 10,876 | 39,994 | 0.00068 | -0.01 | 103
gnutella08 | 6,301 | 20,777 | 0.00100 | 0.04 | 97
oregon1 | 10,670 | 22,002 | 0.00039 | -0.19 | 2312
power-network | 4,941 | 6,594 | 0.00054 | 0.00 | 19
tech-routers | 2,113 | 6,632 | 0.00300 | 0.02 | 109
web-edu | 3,031 | 6,474 | 0.00140 | -0.17 | 104
web-google | 1,299 | 2,773 | 0.00330 | -0.05 | 59
TABLE III: Statistics of the “real-world” graphs. | SSR-E | SSR-C | SSR-R | SSC-E | SSC-C | SSC-R | SSS-E | SSS-C | SSS-R
---|---|---|---|---|---|---|---|---|---
astroPh | 399.4 | 348.0, 410.9 | 5.3 | 391.1 | 361.5, 424.0 | 0.4 | 381.1 | 369.4, 430.4 | 4.7
britekite | 1164.6 | 1049.2, 1231.4 | 2.1 | 1141.7 | 1070.2, 1260.4 | 2.0 | 1134.6 | 1279.1, 1522.5 | 19.0
contMat | 545.2 | 547.4, 644.7 | 5.3 | 550.8 | 546.0, 643.5 | 7.4 | 545.0 | 508.6, 591.0 | 0.9
epinions1 | 465.5 | 426.1, 497.8 | 1.4 | 465.5 | 418.2, 488.1 | 2.7 | 465.1 | 1020.5, 1298.3 | 60.0
fb-combined | 28.0 | 26.0, 30.4 | 0.7 | 27.9 | 25.8, 30.2 | 0.5 | 27.7 | 28.9, 34.3 | 12.3
gnutella04 | 302.1 | 268.7, 318.5 | 2.9 | 294.0 | 279.1, 326.2 | 2.9 | 290.4 | 288.9, 245.7 | 8.5
gnutella08 | 525.1 | 479.5, 562.7 | 0.8 | 484.8 | 461.0, 537.5 | 2.9 | 444.9 | 459.0, 537.0 | 10.6
oregon1 | 304.9 | 273.4, 320.5 | 2.7 | 296.4 | 261.1, 308.0 | 4.2 | 294.4 | 343.0, 403.0 | 21.1
power-network | 308.8 | 270.1, 319.1 | 4.8 | 290.7 | 266.9, 311.8 | 0.5 | 285.2 | 248.4, 287.4 | 6.4
tech-routers | 192.0 | 176.6, 206.6 | 0.2 | 176.2 | 168.8, 196.5 | 3.6 | 160.4 | 226.9, 261.5 | 34.3
web-edu | 216.5 | 214.1, 251.5 | 7.0 | 202.1 | 192.7, 223.4 | 2.8 | 194.0 | 226.0, 262.5 | 20.6
web-google | 86.6 | 76.1, 90.2 | 4.1 | 81.3 | 77.2, 89.7 | 2.6 | 78.3 | 69.6, 80.0 | 4.7
TABLE IV: Unit cost, $1000$ trials $n_{0}^{*}=4$: SSR-E $\to$ SSR Estimate, SSR-C $\to$ SSR $95\%$ Confidence Interval, SSR-R $\to$ SSR Absolute Relative Error $(\%)$, Etc. Bold indicates the estimate is outside the confidence interval. | SSR-E | SSR-C | SSR-R | SSC-E | SSC-C | SSC-R | SSS-E | SSS-C | SSS-R
---|---|---|---|---|---|---|---|---|---
astroPh | 8829.6 | 7678.2, 9066.4 | 5.5 | 8477.6 | 7852.1, 9174.3 | 0.4 | 5959.2 | 4271.7, 4749.2 | 32.1
britekite | 9727.7 | 8753.0, 10275.4 | 2.2 | 9375.6 | 8752.2, 10279.0 | 1.5 | 8309.0 | 6155.9, 7005.0 | 26.3
contMat | 5125.0 | 4974.1, 5858.9 | 5.4 | 4899.7 | 4849.9, 5693.8 | 7.1 | 4174.0 | 3435.9, 3901.4 | 13.5
epinions1 | 5477.5 | 4981.9, 5782.3 | 1.8 | 5413.6 | 4885.4, 5669.5 | 2.6 | 5069.6 | 4944.2, 5765.5 | 4.8
fb-combined | 1253.5 | 1165.7, 1361.4 | 0.8 | 1236.8 | 1147.9, 1334.7 | 0.4 | 928.8 | 816.5, 915.2 | 7.3
gnutella04 | 2524.0 | 2245.2, 2660.5 | 2.9 | 2399.1 | 2278.6, 2652.2 | 2.7 | 2034.3 | 1738.3, 1980.4 | 9.4
gnutella08 | 3987.9 | 3648.3, 4280.2 | 0.6 | 3453.3 | 3293.7, 3801.3 | 2.7 | 2388.9 | 1805.8, 2006.7 | 25.3
oregon1 | 1562.1 | 1388.9, 1632.3 | 3.4 | 1485.8 | 1320.1, 1545.9 | 3.7 | 1354.9 | 793.9, 902.8 | 59.7
power-network | 1133.1 | 990.2, 1169.6 | 4.9 | 1023.5 | 941.8, 1094.7 | 0.5 | 912.5 | 812.1, 926.4 | 5.0
tech-routers | 1397.9 | 1287.7, 1503.6 | 0.2 | 1196.8 | 1154.1, 1328.5 | 3.6 | 819.7 | 717.0, 792.0 | 8.6
web-edu | 1141.4 | 1137.1, 1335.5 | 7.7 | 1011.6 | 972.0, 1117.5 | 3.2 | 815.6 | 725.3, 820.5 | 5.5
web-google | 456.3 | 401.1, 475.1 | 4.2 | 407.7 | 388.0, 448.6 | 2.5 | 330.8 | 265.6, 296.3 | 17.7
TABLE V: Linear cost, $1000$ trials, $n_{0}^{*}=4$: SSR-E $\to$ SSR Estimate,
SSR-C $\to$ SSR $95\%$ Confidence Interval, SSR-R $\to$ SSR Absolute Relative
Error $(\%)$, Etc. Bold indicates the estimate is outside the confidence
interval.

Fig. 5 shows the unit (top) and linear (bottom) costs for the twelve “real-
world” graphs vs. the sampling variant, i.e., SSR, SSC, or SSS. The cost for
most graphs is relatively constant across the three variants, with several
notable exceptions. Namely, the unit costs for epinions1 and britekite are
notably higher for SSS than for SSR/SSC, and the linear costs for britekite
and astroph are notably lower for SSS than for SSR/SSC.

Figure 5: Simulation results for the twelve “real-world” graphs.

##  VII Conclusion

Star sampling (SS) is a natural means by which to randomly search for an
element of a target set in a large / dynamic graph that is not available for
deterministic search. Assessing the performance of the three SS variants (SSR,
SSC, and SSS) is an important question to answer in order to assess whether
the complexity incurred in avoiding sample replacement will yield a notable
reduction in cost. ER random graphs are a useful class of graphs to analyze
given their tractability; the bounds are seen to be tight, and the
approximations are seen to be accurate. Moreover, applying these
approximationsn to “real-world” graphs shows them to have, in most but not all
cases, reasonably small relative errors, despite the approximations,
particularly for SSS, having been derived for an ER graph. Finally, the
results are easy to apply in that they require knowledge of only three basic
facts: the graph order, the cardinality of the target set, and the edge
density.

## References

  * [1] J. Stokes and S. Weber, “On random walks and random sampling to find max degree nodes in assortative Erdős Rényi graphs,” in _2016 IEEE Global Communications Conference (GLOBECOM)_ , Dec 2016.
  * [2] ——, “On the number of star samples to find a vertex or edge with given degree in a graph,” in _2017 51st Annual Conference on Information Sciences and Systems (CISS)_ , 2017, pp. 1–6.
  * [3] ——, “Star sampling with and without replacement,” in _Proceedings of the International Workshop on Mining and Learning with Graphs (MLG)_ , August 2017.
  * [4] E. D. Kolaczyk, _Statistical analysis of network data : methods and models_. New York,, London: Springer, 2009\.
  * [5] L. Goodman, “Snowball Sampling,” _Ann. Math. Statist._ , vol. 32, no. 1, pp. 148–170, 1961.
  * [6] O. Frank, “Survey sampling in graphs,” _Journal of Statistical Planning and Inference_ , vol. 1, no. 3, pp. 235 – 264, 1977.
  * [7] S. H. Lee, P.-J. Kim, and H. Jeong, “Statistical properties of sampled networks,” _Phys. Rev. E_ , vol. 73, p. 016102, 2006.
  * [8] Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of topological characteristics of huge online social networking services,” in _Proceedings of the 16th International Conference on World Wide Web_ , ser. WWW ’07, 2007, pp. 835–844.
  * [9] P. Hu and W. C. Lau, “A survey and taxonomy of graph sampling,” _arXiv preprint arXiv:1308.5865_ , 2013.
  * [10] H. Wang and J. Lu, “Detect inflated follower numbers in OSN using star sampling,” in _2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013)_ , 2013, pp. 127–133.
  * [11] C.-H. Lee, X. Xu, and D. Y. Eun, “Beyond random walk and metropolis-hastings samplers: Why you should not backtrack for unbiased graph sampling,” _SIGMETRICS Perform. Eval. Rev._ , vol. 40, no. 1, pp. 319–330, June 2012\.
  * [12] R. H. Li, J. X. Yu, L. Qin, R. Mao, and T. Jin, “On random walk based graph sampling,” in _2015 IEEE 31st International Conf. on Data Engineering_ , 2015, pp. 927–938.
  * [13] M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, “Walking in Facebook: A case study of unbiased sampling of osns,” in _Proceedings of the 29th Conference on Information Communications_ , ser. INFOCOM’10, 2010, pp. 2498–2506.
  * [14] M. Kurant, M. Gjoka, C. T. Butts, and A. Markopoulou, “Walking on a graph with a magnifying glass: Stratified sampling via weighted random walks,” in _Proc. of the ACM SIGMETRICS Joint Intl. Conf. on Measurement and Modeling of Computer Systems_ , 2011, pp. 281–292.
  * [15] F. Chiericetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlós, “On sampling nodes in a network,” in _Proceedings of the 25th International Conference on World Wide Web_ , ser. WWW ’16. International World Wide Web Conferences, 2016, pp. 471–481.
  * [16] R. A. Lew, “Bounds on negative moments,” _SIAM Journal of Applied Mathematics_ , vol. 30, no. 4, pp. 728–731, June 1976.
  * [17] G. M. J. V. Kempen and L. J. van Vliet, “Mean and variance of ratio estimators used in fluorescence ratio imaging.” _Cytometry_ , vol. 39 4, pp. 300–5, 2000.
  * [18] H. Seltman, “Approximations for mean and variance of a ratio,” www.stat.cmu.edu/~hseltman/files/ratio.pdf, May 2017.
  * [19] D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [20] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, June 2014.
  * [21] R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015. [Online]. Available: http://networkrepository.com

##  Appendix A Proof of Fact 1

###### Proof:

Define: $i)$ $(n)_{k}\equiv(n-0)(n-1)\cdots(n-(k-1))$ as the falling factorial
(recall $\binom{n}{k}=(n)_{k}/k!$); $ii)$ $p_{t}\equiv n^{*}/(n-t+1)$ for
$t\in[n-n^{*}+1]$ as the probability of success on trial $t$, conditioned on
failure in the first $t-1$ trials (observe $p_{1}=n^{*}/n$ and
$p_{n-n^{*}+1}=1$); $iii)$ $q_{t}\equiv p_{t}\prod_{c=1}^{t-1}(1-p_{c})$ as
the unconditioned probability of a first success on trial $t$; $iv)$
$\mathsf{x}$ as the RV for the number of required trials, where $\mathsf{x}$
has distribution $(q_{t},t\in[n-n^{*}+1])$. It is straightforward but tedious
to show that $(q_{t},t\in[n-n^{*}+1])$ is correctly normalized. Substituting
into the definition $\mathbb{E}[\mathsf{x}]\equiv\sum_{t=1}^{n+1-n^{*}}tq_{t}$
yields

$\mathbb{E}[\mathsf{x}]=\frac{n^{*}}{n}+n^{*}\sum_{t=2}^{n+1-n^{*}}\frac{t}{n+1-t}\prod_{s=1}^{t-1}\frac{n+1-n^{*}-s}{n+1-s}.$
(40)

Using the falling factorial definition yields:

$\mathbb{E}[\mathsf{x}]=\frac{n^{*}}{n}+n^{*}\sum_{t=2}^{n+1-n^{*}}\frac{\binom{n-n^{*}}{t-1}}{\binom{n}{t}}\\\
$

Using the change of variable $s=n+1-n^{*}-t$ yields

$\mathbb{E}[\mathsf{x}]=\frac{n^{*}}{n}+\frac{1}{\binom{n}{n^{*}}}\sum_{s=0}^{n-1-n^{*}}(n+1-n^{*}-s)\binom{n^{*}-1+s}{n^{*}-1}.$
(41)

It is straightforward but tedious to verify that

$\sum_{s=0}^{n-1-n^{*}}(n+1-n^{*}-s)\binom{n^{*}-1+s}{n^{*}-1}=\frac{(n+n^{*}+1)(n-1)!}{(n-n^{*}-1)!(n^{*}+1)!}.$
(42)

Substitution and simple algebra yields the result. ∎

##  Appendix B Proof of Lem. 1

Lem. 1 holds by Lem. 3 and Lem. 4, both proved below.

######  Lemma 3.

Take $t^{\prime}\in[n]$ samples from an ER random graph $\mathsf{G}$ with
parameters $(n,s)$ using SSC, yielding a sequence of random graphs
$(\mathsf{G}_{t},t\in[t^{\prime}])$. Then
$\mathsf{G}_{t}=(V_{t},\mathsf{E}_{t})$ is an ER random graph with parameters
$(n-t,s)$ for each $t\in[t^{\prime}]$.

###### Proof:

Let $\mathsf{G}_{0}=\mathsf{G}$ denote the initial ER random graph, with
$\mathsf{G}_{0}=(V_{0},\mathsf{E}_{0})$, where $V_{0}=[n]$ and
$\mathsf{E}_{0}$ may be considered as a sequence of $\binom{n}{2}$ IID
Bernoulli RVs, say $\mathsf{E}_{0}=(\mathsf{x}_{e},e\in[\binom{n}{2}])$, with
$\mathsf{x}_{e}\sim\mathrm{Ber}(s)$ indicating the random inclusion or
exclusion of an edge at the “site” at (unordered) vertex pair $e$.

Define the sequence of random vertex and set triples
$((\mathsf{v}_{t},\mathsf{V}_{t},\mathsf{E}_{t}),t\in[t^{\prime}])$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(\mathsf{V}_{t-1})$ the randomly selected star
center in sample $t$,
$\mathsf{V}_{t}=\mathsf{V}_{t-1}\setminus\\{\mathsf{v}_{t}\\}$ the set of
vertices that remain after removal of star center $\mathsf{v}_{t}$, and
$\mathsf{E}_{t}=\mathsf{E}_{t-1}\setminus\mathsf{F}_{t}$, for
$\mathsf{F}_{t}\equiv\Gamma_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})$, the edges
that remain after removal of the edge neighborhood of $\mathsf{v}_{t}$ from
$\mathsf{G}_{t-1}$.

For $t\in[t^{\prime}]$: $i)$
$\mathsf{V}_{t}=V_{0}\setminus\mathsf{V}_{t}^{c}$, for
$\mathsf{V}_{t}^{c}\equiv\mathsf{v}_{1}\cup\cdots\cup\mathsf{v}_{t}$ the set
of vertices removed in the first $t$ samples, and $ii)$
$\mathsf{E}_{t}=\mathsf{E}_{0}\setminus\mathsf{E}_{t}^{c}$, for
$\mathsf{E}_{t}^{c}\equiv\mathsf{F}_{1}\cup\cdots\cup\mathsf{F}_{t}$ the set
of edges removed in the first $t$ samples. Then $|\mathsf{V}_{t}|=n-t$, and,
as $\mathsf{E}_{0}$ is IID $\mathrm{Ber}(s)$, the RVs in $\mathsf{E}_{t}$ are
IID $\mathrm{Ber}(s)$, so that $\mathsf{G}_{t}$ is an ER random graph (with
random vertex labels) with parameters $(n-t,s)$. ∎

######  Lemma 4.

Take $t^{\prime}\in[n]$ samples from an ER random graph $\mathsf{G}$ with
parameters $(n,s)$ using SSS, yielding a sequence of random graphs
$(\mathsf{G}_{t},t\in[t^{\prime}])$. Then
$\mathsf{G}_{t}=(\mathsf{V}_{t},\mathsf{E}_{t})$ is an ER random graph with
random order parameter $\mathsf{n}_{t}$ and edge probability $s$, for each
$t\in[t^{\prime}]$. The random order parameter,
$\mathsf{n}_{t}\equiv|\mathsf{V}_{t}|$, obeys the recursion
$\mathsf{n}_{t}=\mathsf{n}_{t-1}-\mathsf{d}^{e}_{t}$, for
$\mathsf{d}^{e}_{t}\sim 1+\mathrm{bin}(\mathsf{n}_{t-1}-1,s)$, for
$t\in[t^{\prime}]$.

###### Proof:

The first two paragraphs in the proof of Lem. 3 hold here as well; we adopt
the same notation below. Define the sequence of random vertex and set triples
$((\mathsf{v}_{t},\mathsf{V}_{t},\mathsf{E}_{t}),t\in[t^{\prime}])$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(\mathsf{V}_{t-1})$ the randomly selected star
center in sample $t$, $\mathsf{V}_{t}=\mathsf{V}_{t-1}\setminus
N_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})$ the set of vertices that remain
after removal of star $N_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})$, and
$\mathsf{E}_{t}=\mathsf{E}_{t-1}\setminus\Gamma_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})$,
the edges that remain after removal of the extended edge neighborhood of
$\mathsf{v}_{t}$ from $\mathsf{G}_{t-1}$. The sequence of RV pairs
$((\mathsf{n}_{t},\mathsf{d}^{e}_{t}),t\in[t^{\prime}])$, where
$\mathsf{n}_{t}=|\mathsf{V}_{t}|$ is the random order of $\mathsf{G}_{t}$ and
$\mathsf{d}^{e}_{t}=|N_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})|$ is the random
order of the extended neighborhood of $\mathsf{v}_{t}$, obeys (by
construction) the recursion
$\mathsf{n}_{t}=\mathsf{n}_{t-1}-\mathsf{d}^{e}_{t}$, with $\mathsf{n}_{0}=n$.
Proof by induction in $t$ will show $i)$ $\mathsf{G}_{t}$ is ER, and $ii)$
$\mathsf{d}^{e}_{t}\sim 1+\mathrm{bin}(\mathsf{n}_{t-1}-1,s)$, for
$t\in[t^{\prime}]$.

Base case. It must be shown $i)$
$\mathsf{G}_{1}=(\mathsf{V}_{1},\mathsf{E}_{1})$ is an ER random graph with
parameters $\mathsf{n}_{1}=n-\mathsf{d}^{e}_{1}$ and $s$, and $ii)$
$\mathsf{d}^{e}_{1}\sim 1+\mathrm{bin}(n-1,s)$. Recall
$\mathsf{V}_{1}=V_{0}\setminus N^{e}_{G_{0}}(\mathsf{v}_{1})$ and
$\mathsf{E}_{1}=\mathsf{E}_{0}\setminus\Gamma_{G_{0}}^{e}(\mathsf{v}_{1})$.
First, the edges in $\mathsf{E}_{1}$ are a (randomly selected) subset of the
IID $\mathrm{Ber}(s)$ RVs in $\mathsf{E}_{0}$, and as such the edges in
$\mathsf{E}_{1}$ are also IID $\mathrm{Ber}(s)$ RVs; this shows $i)$. Second,
$\mathsf{d}^{e}_{1}=|N_{G_{0}}^{e}(\mathsf{v}_{1})|$ counts both the star
center $\mathsf{u}_{1}$ and its neighbors $N_{G_{0}}(\mathsf{v}_{1})$, where
$d_{\mathsf{v}_{1}}\equiv|N_{G_{0}}(\mathsf{v}_{1})|$ has distribution
$\mathrm{Ber}(n-1,s)$ by construction; this shows $ii)$.

Induction hypothesis. Fix $t\in[t^{\prime}]$ and assume the induction
hypothesis for $t-1$, i.e., assume $i)$ $\mathsf{G}_{t-1}$ is an ER random
graph with parameters $\mathsf{n}_{t-1}$ and $s$, and $ii)$
$\mathsf{d}^{e}_{t-1}\sim 1+\mathrm{bin}(\mathsf{n}_{t-2}-1,s)$. It follows
that $\mathsf{n}_{t-1}=\mathsf{n}_{t-2}-\mathsf{d}^{e}_{t-1}$. It must shown
that this implies $i)$ the random graph $\mathsf{G}_{t}$ obtained by removing
a random star from $\mathsf{G}_{t-1}$ is an ER graph with parameters
$\mathsf{n}_{t}=\mathsf{n}_{t-1}-\mathsf{d}^{e}_{t}$ and $s$, and $ii)$
$\mathsf{d}^{e}_{t}\sim 1+\mathrm{bin}(\mathsf{n}_{t-1},s)$. First, the edges
in $\mathsf{E}_{t}$ are a (randomly selected) subset of the IID
$\mathrm{Ber}(s)$ RVs in $\mathsf{E}_{t-1}$, and as such the edges in
$\mathsf{E}_{t}$ are also IID $\mathrm{Ber}(s)$ RVs; this shows $i)$. Second,
$\mathsf{d}^{e}_{t}=|N_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})|$ counts both
the star center $\mathsf{v}_{t}$ and its neighbors
$N_{\mathsf{G}_{t-1}}(\mathsf{v}_{t})$, where
$d_{\mathsf{v}_{t}}\equiv|N_{\mathsf{G}_{t-1}}^{e}(\mathsf{v}_{t})|$ has
distribution $\mathrm{Ber}(\mathsf{n}_{t-1}-1,s)$ by construction; this shows
$ii)$. ∎

##  Appendix C Proof of Lem. 2

###### Proof:

A star sample has two “types” of vertices (the star center $\mathsf{v}$ and
its $\mathsf{d}$ neighbors) and three “types” of edges, namely, $i)$
“neighbor” edges connecting $\mathsf{v}$ with $N_{\mathsf{G}}(\mathsf{v})$,
$ii)$ “internal” edges with both vertices in $N_{\mathsf{G}}(\mathsf{v})$, and
$iii)$ “external” edges with one vertex in $N_{\mathsf{G}}(\mathsf{v})$ and
the other in $V\setminus N_{\mathsf{G}}^{e}(\mathsf{v})$. There are
$\mathsf{d}$ neighbor edges by assumption, $\binom{\mathsf{d}}{2}$ potential
internal edges, and $\mathsf{d}(n-\mathsf{d}-1)$ potential external edges,
where (due to the ER random graph properties) all potential edges are present
or absent independently with probability $s$.

As $\mathsf{d}\sim\mathrm{bin}(n-1,s)$, we have
$\mathbb{E}[\mathsf{d}]=(n-1)s$ and
$\mathbb{E}[\mathsf{d}^{2}]=(n-1)s+2\binom{n-1}{2}s^{2}$, and with these (4)
is obtained by conditional expectation and simple algebra:

$\displaystyle\mathbb{E}[\mathsf{g}]$ $\displaystyle=$
$\displaystyle\mathbb{E}[\mathbb{E}[\mathsf{g}|\mathsf{d}]]$ (43)
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathsf{d}+\left(\binom{\mathsf{d}}{2}+\mathsf{d}(n-\mathsf{d}-1)\right)s\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(1+\left(n-\frac{3}{2}\right)s\right)\mathsf{d}-\frac{1}{2}s\mathsf{d}^{2}\right]$
$\displaystyle=$
$\displaystyle\left(1+\left(n-\frac{3}{2}\right)s\right)\mathbb{E}[\mathsf{d}]-\frac{1}{2}s\mathbb{E}[\mathsf{d}^{2}]$

The limit of $\mathbb{E}[\mathsf{g}]/(\binom{n}{2}s)$ as $n\uparrow\infty$
follows from (4). ∎

##  Appendix D Proof of Lem. 5

Let $(\mathsf{G}_{t},t\in\mathbb{Z}^{+})$ be a sequence of ER random graphs
induced by SSS, with $\mathsf{G}_{t}=(\mathsf{V}_{t},\mathsf{E}_{t})$ the
graph following the removal of the random star selected in sample $t$,
starting from an initial ER random graph
$\mathsf{G}_{0}=(V_{0},\mathsf{E}_{0})$ with parameters $(n,s)$. Set
$\bar{s}\equiv 1-s$.

Fix “watch” $W_{0}\subseteq V_{0}$ and “draw” $D_{0}\subseteq V_{0}$ subsets,
and define an “immune” subset $Z_{0}\subseteq W_{0}$ comprised of vertices in
$W_{0}$ with no neighbors in $D_{0}$. Define the random set-valued sequences
$(\mathsf{W}_{t},t\in\mathbb{Z}^{+})$ and
$(\mathsf{D}_{t},t\in\mathbb{Z}^{+})$, with $\mathsf{W}_{t}\equiv
W_{0}\cap\mathsf{V}_{t}$ and $\mathsf{D}_{t}\equiv D_{0}\cap\mathsf{V}_{t}$
the watch and draw sets surviving the first $t$ samples. Consider two cases
for star centers: $i)$ they are never drawn from the watch set, i.e.,
$D_{0}\cap W_{0}=\emptyset$, and $ii)$ they are always drawn from the watch
set, i.e., $D_{0}\subseteq W_{0}$.

Let $(\mathsf{v}_{t},t\in\mathbb{N})$, with
$\mathsf{v}_{t}\sim\mathrm{uni}(\mathsf{V}_{t-1})$, denote the sequence of
random star centers associated with each random sample, and define the event
sequence $(\mathcal{C}_{t},t\in\mathbb{N})$ that star center $t$ is drawn from
the surviving draw set, i.e.,
$\mathcal{C}_{t}\equiv\\{\mathsf{v}_{t}\in\mathsf{D}_{t-1}\\}$. Let
$\bar{\mathcal{C}}_{t}\equiv\bigcap_{t^{\prime}\in[t]}\mathcal{C}_{t^{\prime}}$
be the event that the first $t$ star centers are each drawn from the surviving
draw set.

Define the random sequence $(\mathsf{n}_{t},t\in\mathbb{Z}^{+})$, with
$\mathsf{n}_{t}\equiv|\mathsf{W}_{t}|$ the watch set order, and define the
sequences of conditional means $(\mu_{W|D,t},t\in\mathbb{Z}^{+})$ and
conditional variances $(\sigma^{2}_{W|D,t},t\in\mathbb{Z}^{+})$, with
$\mu_{W|D,t}\equiv\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{C}}_{t}]$ and
$\sigma^{2}_{W,t}\equiv\mathrm{Var}(\mathsf{n}_{t}|\bar{\mathcal{C}}_{t})$
associated with $\mathsf{n}_{t}$ and $\bar{\mathcal{C}}_{t}$. Let
$n_{Z,0}=|Z_{0}|$.

######  Lemma 5.

The mean and variance in the size of the watch set $\mathsf{W}_{t}$,
conditioned on drawing from the draw set $\mathsf{D}_{t}$ and removing no
vertices from the immune set $Z_{0}$, after $t$ samples, where
$n_{W,0}=|W_{0}|$ and $n_{Z,0}=|Z_{0}|$, are: $i)$ if $D_{0}\cap
W_{0}=\emptyset$,

$\displaystyle\mu_{W|D,t}^{i)}$ $\displaystyle=$
$\displaystyle(n_{W,0}-n_{Z,0})\bar{s}^{t}+n_{Z,0}$ (44)
$\displaystyle\sigma^{2,i)}_{W|D,t}$ $\displaystyle=$
$\displaystyle(n_{W,0}-n_{Z,0})\bar{s}^{t}(1-\bar{s}^{t})$ (45)

or, $ii)$ if $D_{0}\subseteq W_{0}$ and $Z_{0}=\emptyset$,

$\displaystyle\mu_{W|D,t}^{ii)}$ $\displaystyle=$
$\displaystyle\mu_{W|D,t}^{i)}-\frac{\bar{s}}{s}(1-\bar{s}^{t})$ (46)
$\displaystyle\sigma^{2,ii)}_{W|D,t}$ $\displaystyle=$
$\displaystyle\sigma^{2,i)}_{W|D,t}+\frac{\bar{s}}{s(1+\bar{s})}\left(1+\bar{s}(1-\bar{s}^{t})\right)\bar{s}^{t}.$
(47)

###### Proof:

Let $\mathsf{r}_{t}$ be the RV denoting the number of vertices in the watch
set removed by sample $t$. The random recurrence induced by the sampling is
$\mathsf{n}_{t}=\mathsf{n}_{t-1}-\mathsf{r}_{t}$. First:

$\displaystyle\mu_{W|D,t}$ $\displaystyle\equiv$
$\displaystyle\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{C}}_{t}]=\mathbb{E}[\mathbb{E}[\mathsf{n}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathbb{E}[\mathsf{n}_{t-1}-\mathsf{r}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t}]=\mathbb{E}[\mathsf{n}_{t-1}-\mathbb{E}[\mathsf{r}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t}].$

Second: $\sigma^{2}_{W|D,t}$

$\displaystyle\equiv$
$\displaystyle\mathrm{Var}(\mathsf{n}_{t}|\bar{\mathcal{C}}_{t})$ (49)
$\displaystyle=$
$\displaystyle\mathrm{Var}(\mathbb{E}[\mathsf{n}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t})+\mathbb{E}[\mathrm{var}(\mathsf{n}_{t}|\mathsf{n}_{t-1})|\bar{\mathcal{C}}_{t}]$
$\displaystyle=$
$\displaystyle\mathrm{Var}(\mathbb{E}[\mathsf{n}_{t-1}-\mathsf{r}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t})+\mathbb{E}[\mathrm{Var}(\mathsf{n}_{t-1}-\mathsf{r}_{t}|\mathsf{n}_{t-1})|\bar{\mathcal{C}}_{t}]$
$\displaystyle=$
$\displaystyle\mathrm{Var}(\mathsf{n}_{t-1}-\mathbb{E}[\mathsf{r}_{t}|\mathsf{n}_{t-1}]|\bar{\mathcal{C}}_{t})+\mathbb{E}[\mathrm{Var}(\mathsf{r}_{t}|\mathsf{n}_{t-1})|\bar{\mathcal{C}}_{t}]$

Case $i)$ ($D_{0}\cap W_{0}=\emptyset$). As the star center is never drawn
from the watch set
$\mathsf{r}_{t}|(\mathsf{n}_{t-1},\mathcal{C}_{t})\sim\mathrm{bin}(\mathsf{n}_{t-1}-n_{Z,0},s)$,
and therefore $i)$
$\mathbb{E}[\mathsf{r}_{t}|\mathsf{n}_{t-1},\mathcal{C}_{t}]=(\mathsf{n}_{t-1}-n_{Z,0})s$
and $ii)$
$\mathrm{Var}(\mathsf{r}_{t}|\mathsf{n}_{t-1},\mathcal{C}_{t})=(\mathsf{n}_{t-1}-n_{Z,0})s\bar{s}$.
First:

$\displaystyle\mu_{W|D,t}-n_{Z,0}$ $\displaystyle=$
$\displaystyle\mathbb{E}[(\mathsf{n}_{t-1}-n_{Z,0})-(\mathsf{n}_{t-1}-n_{Z,0})s|\bar{\mathcal{C}}_{t}]$
(50) $\displaystyle=$
$\displaystyle\bar{s}\mathbb{E}[(\mathsf{n}_{t-1}-n_{Z,0})|\bar{\mathcal{C}}_{t}]$
$\displaystyle=$
$\displaystyle\bar{s}\mathbb{E}[(\mathsf{n}_{t-1}-n_{Z,0})|\bar{\mathcal{C}}_{t-1}]$
$\displaystyle=$ $\displaystyle\bar{s}(\mu_{W|D,t-1}-n_{Z,0}).$

The recurrence $\mu_{W|D,t}-n_{Z,0}=\bar{s}(\mu_{W|D,t-1}-n_{Z,0})$ with
initial condition $\mu_{W|D,0}=n_{W,0}$ has solution (44).

$\displaystyle\sigma^{2}_{W|D,t}$ $\displaystyle=$
$\displaystyle\mathrm{Var}((\mathsf{n}_{t-1}-n_{Z,0})-(\mathsf{n}_{t-1}-n_{Z,0})s|\bar{\mathcal{C}}_{t})$
(51) $\displaystyle+$
$\displaystyle\mathbb{E}[(\mathsf{n}_{t-1}-n_{Z,0})s\bar{s}|\bar{\mathcal{C}}_{t-1}]$
$\displaystyle=$ $\displaystyle
s^{2}\mathrm{Var}(\mathsf{n}_{t-1}-n_{Z,0}|\bar{\mathcal{C}}_{t})+s\bar{s}\mathbb{E}[\mathsf{n}_{t-1}-n_{Z,0}|\bar{\mathcal{C}}_{t-1}]$
$\displaystyle=$ $\displaystyle
s^{2}\mathrm{Var}(\mathsf{n}_{t-1}|\bar{\mathcal{C}}_{t-1})+s\bar{s}\mathbb{E}[\mathsf{n}_{t-1}-n_{Z,0}|\bar{\mathcal{C}}_{t-1}]$
$\displaystyle=$ $\displaystyle
s^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}\mathbb{E}[\mathsf{n}_{t-1}-n_{Z,0}|\bar{\mathcal{C}}_{t-1}]$
$\displaystyle=$ $\displaystyle
s^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}(\mu_{W|t-1}-n_{Z,0})$ $\displaystyle=$
$\displaystyle
s^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}((n_{W,0}-n_{Z,0})\bar{s}^{t-1})$
$\displaystyle=$ $\displaystyle
s^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}^{t}(n_{W,0}-n_{Z,0}).$

The recurrence
$\sigma^{2}_{W|D,t}=\bar{s}^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}^{t}(n_{W,0}-n_{Z,0})$
with initial condition $\sigma^{2}_{W|D,0}=0$ has solution (45).

Case $ii)$ ($D_{0}\subseteq W_{0}$, $Z_{0}=\emptyset$). As the star center is
always drawn from the watch set and $n_{Z,0}=0$,
$\mathsf{r}_{t}|(\mathsf{n}_{t-1},\bar{\mathcal{C}}_{t})\sim
1+\mathrm{bin}(\mathsf{n}_{t-1}-1,s)$, and therefore $i)$
$\mathbb{E}[\mathsf{r}_{t}|\mathsf{n}_{t-1}]=1+(\mathsf{n}_{t-1}-1)s$ and
$ii)$
$\mathrm{Var}(\mathsf{r}_{t}|\mathsf{n}_{t-1})=(\mathsf{n}_{t-1}-1)s\bar{s}$.
First:

$\displaystyle\mu_{W|D,t}$ $\displaystyle=$
$\displaystyle\mathbb{E}[\mathsf{n}_{t-1}-(1+(\mathsf{n}_{t-1}-1)s)|\bar{\mathcal{C}}_{t}]$
(52) $\displaystyle=$
$\displaystyle\bar{s}\mathbb{E}[\mathsf{n}_{t-1}|\bar{\mathcal{C}}_{t}]-\bar{s}$
$\displaystyle=$
$\displaystyle\bar{s}\mathbb{E}[\mathsf{n}_{t-1}|\bar{\mathcal{C}}_{t-1}]-\bar{s}$
$\displaystyle=$ $\displaystyle\bar{s}(\mu_{W|D,t-1}-1).$

The recurrence $\mu_{W|D,t}=\bar{s}(\mu_{W|D,t-1}-1)$ with initial condition
$\mu_{W|D,0}=n_{W,0}$ has solution (46). Second:

$\displaystyle\sigma^{2}_{W|D,t}$ $\displaystyle=$
$\displaystyle\mathrm{Var}(\mathsf{n}_{t-1}-(1+(\mathsf{n}_{t-1}-1)s)|\bar{\mathcal{C}}_{t})$
$\displaystyle+$
$\displaystyle\mathbb{E}[(\mathsf{n}_{t-1}-1)s\bar{s}|\bar{\mathcal{C}}_{t})$
$\displaystyle=$
$\displaystyle\bar{s}^{2}\mathrm{Var}(\mathsf{n}_{t-1}|\bar{\mathcal{C}}_{t})+s\bar{s}\mathbb{E}[\mathsf{n}_{t-1}-1|\bar{\mathcal{C}}_{t})$
$\displaystyle=$
$\displaystyle\bar{s}^{2}\mathrm{Var}(\mathsf{n}_{t-1}|\bar{\mathcal{C}}_{t-1})+s\bar{s}\mathbb{E}[\mathsf{n}_{t-1}-1|\bar{\mathcal{C}}_{t-1})$
$\displaystyle=$
$\displaystyle\bar{s}^{2}\sigma^{2}_{W|D,t-1}+s\bar{s}(\mu_{W|D,t-1}-1)$
$\displaystyle=$ $\displaystyle\bar{s}^{2}\sigma^{2}_{W|D,t-1}+s\mu_{W|D,t}$
$\displaystyle=$
$\displaystyle\bar{s}^{2}\sigma^{2}_{W|D,t-1}+\bar{s}\left(((n_{W,0}-1)s+1)\bar{s}^{t-1}-1\right).$

The recurrence

$\sigma^{2}_{W|D,t}=\bar{s}^{2}\sigma^{2}_{W|D,t-1}+((n_{W,0}-1)s+1)\bar{s}^{t}-\bar{s},$

with initial condition $\sigma^{2}_{W|D,0}=0$ has solution (47). ∎

##  Appendix E Proof of Thm. 1

###### Proof:

The proof relies upon Lem. 5 in App. D.

(22) through (24). Apply Lem. 5 to each of the numerator and denominator in
(20). Specifically, $\mathbb{E}[\mathsf{n}^{e,*}_{t}|\bar{\mathcal{E}}_{t}]$
follows from the expectation expression for case $i)$ with watch set
$N_{G_{0}}^{e}(V^{*})$, (disjoint) draw set $V_{0}\setminus
N_{G_{0}}^{e}(V^{*})$, conditioned on $\bar{\mathcal{E}}_{t}$ and hence
$V^{*}$ being unsampled, while
$\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]$ follows from the
expectation expression for case $ii)$ with watch set $V_{0}$ and (subset) draw
set $V_{0}\setminus N_{G_{0}}^{e}(V^{*})$:

$\displaystyle\mathbb{E}[\mathsf{n}^{e,*}_{t}|\bar{\mathcal{E}}_{t}]$
$\displaystyle=$
$\displaystyle(\mathbb{E}[\mathsf{n}^{e,*}_{0}]-n^{*}_{0})\bar{s}^{t}+n^{*}_{0}$
(54) $\displaystyle\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]$
$\displaystyle=$ $\displaystyle
n\bar{s}^{t}-\frac{\bar{s}}{s}(1-\bar{s}^{t}).$ (55)

The ratio of (54) and (55) gives (22). The first two derivatives of
$\tilde{p}_{t}^{\rm SSS}$ with respect to $t$ are:

$\displaystyle\tilde{p}_{t+1}^{\rm SSS^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{s\bar{s}^{t}(n^{*}_{0}ns+\mathbb{E}[\mathsf{n}_{0}^{e,*}]\bar{s})\log(\frac{1}{\bar{s}})}{(\bar{s}-\bar{s}^{t}(ns+\bar{s}))^{2}}>0$
$\displaystyle\tilde{p}_{t+1}^{\rm SSS^{\prime\prime}}$ $\displaystyle=$
$\displaystyle\frac{ss^{t+1}\mathbb{E}[\mathsf{n}_{0}^{e,*}](\bar{s}+\bar{s}^{t}(ns+\bar{s}))\left(\log{\bar{s}}\right)^{2}}{(\bar{s}^{t}(ns+\bar{s})-\bar{s})^{3}}>0.$

This establishes that $\tilde{p}_{t}^{\rm SSS}$ is convex increasing. The
value $t^{(2)}_{\tilde{p}}$ is found by equating the denominator in
$\tilde{p}_{t}^{\rm SSS}$ to zero and solving for $t$, and
$t^{(1)}_{\tilde{p}}$ is found by solving $\tilde{p}_{t}^{\rm SSS}=1$ for $t$.

Proof of (25). Apply the variance expression in case $ii)$ of Lem. 5 with
watch set $V_{0}$ and (subset) draw set $V_{0}\setminus N_{G_{0}}^{e}(V^{*})$:

$\mathrm{var}(\mathsf{n}_{t}|\bar{\mathcal{E}}_{t})=\left(n(1-\bar{s}^{t})+\frac{\bar{s}}{s(1+\bar{s})}\left(1+\bar{s}(1-\bar{s}^{t})\right)\right)\bar{s}^{t}.$
(56)

Next, observe
$\mathrm{cov}(\mathsf{n}^{e,*}_{t},\mathsf{n}_{t}|\bar{\mathcal{E}}_{t})$ in
(21) is nonnegative. To see this, consider a general scenario where each
member of a population is given a property value, and two subsets of the
population are defined as holding those members with property values in a
given target set, with the second target set a subset of the first. Let the
property values be random, and consider the two random variables denoting the
cardinalities of the two random population subsets. These random variables are
by construction positively correlated. This general scenario applies here to
the population $\mathsf{V}_{t}$ with the first subset equal to
$\mathsf{V}_{t}$ and the second subset equal to
$N_{\mathsf{G}_{t}}^{e}(\mathsf{V}_{t}^{*})$.

By the above argument, (21) may be upper bounded as:

$\epsilon_{n,t}\leq\frac{\mathrm{var}(\mathsf{n}_{t}|\bar{\mathcal{E}}_{t})\mathbb{E}[\mathsf{n}^{e,*}_{t}|\bar{\mathcal{E}}_{t}]}{\mathbb{E}[\mathsf{n}_{t}|\bar{\mathcal{E}}_{t}]^{3}}.$
(57)

Substitution of (54), (55), and (56) into (57) gives (25).

Proof of (26). This follows by observing the numerator is
$O(nn_{0}^{e,*})=O(n^{2})$ while the denominator is $O(n^{3})$. ∎

##  Appendix F Proof of Thm. 2

###### Proof:

The proofs of (27) and (28) are given in turn.

Proof of (27). Set $\mathcal{C}_{t}$ as the event that star $t$ misses the
target, $\bar{\mathcal{C}}_{t}=\mathcal{C}_{1}\cap\cdots\cap\mathcal{C}_{t}$
as the event that the first $t$ stars each miss the target, and
$\mathcal{C}_{t}^{c}$ as the complement of $\mathcal{C}_{t}$, i.e., the event
that star $t$ hits the target. Set
$p_{t+1}\equiv\mathbb{P}(\mathcal{C}_{t+1}^{c}|\bar{\mathcal{C}}_{t})$ as the
conditional probability that star $t+1$ hits the target given that the first
$t$ stars miss the target. Note
$1-p_{t+1}=\mathbb{P}(\mathcal{C}_{t+1}|\bar{\mathcal{C}}_{t})$. Set
$q_{t+1}\equiv\mathbb{P}(\mathcal{C}_{t+1}^{c}\cap\bar{\mathcal{C}}_{t})$ as
the unconditioned probability that star $t+1$ hits the target and that the
first $t$ stars miss the target. Thus $q_{t+1}$ is the unconditioned
probability that the first star to hit the target is star $t+1$. Set
$r_{t}\equiv\mathbb{P}(\bar{\mathcal{C}}_{t})$ as the probability that the
first $t$ stars each miss the target. As

$q_{t+1}=\mathbb{P}(\mathcal{C}_{t+1}^{c}|\bar{\mathcal{C}}_{t})\mathbb{P}(\bar{\mathcal{C}}_{t})=p_{t+1}r_{t}.$
(58)

and

$r_{t}=\mathbb{P}(\mathcal{C}_{1})\mathbb{P}(\mathcal{C}_{2}|\mathcal{C}_{1})\mathbb{P}(\mathcal{C}_{3}|\bar{\mathcal{C}}_{2})\cdots\mathbb{P}(\mathcal{C}_{t}|\bar{\mathcal{C}}_{t-1})=\prod_{s=1}^{t}(1-p_{s}),$
(59)

it follows that $q_{t+1}=p_{t+1}\prod_{s=1}^{t}(1-p_{s})$. Given approximation
$\tilde{p}_{t+1}\approx p_{t+1}$ of the conditional distribution, (27) is a
corresponding approximation of the unconditional distribution.

Proof of (28). Consider a sequence $\hat{p}\equiv(\hat{p}_{t},t\in\mathbb{N})$
with each $\hat{p}_{t}\in(0,1)$. For $T\in\mathbb{N}$ set
$p^{(T)}\equiv(p^{(T)}_{t},t\in[T])$, with

$p^{(T)}_{t}\equiv\left\\{\begin{array}[]{ll}\hat{p}_{t},&t\in[T-1]\\\
1,&t=T\end{array}\right.,$ (60)

Define the following quantities:

  * •

$\bar{p}^{(T)}_{t}\equiv 1-p^{(T)}_{t}$;

  * •

$\pi^{(T)}\equiv(\pi^{(T)}_{t},t\in[T])$, with $\pi^{(T)}_{1}\equiv 1$,
$\pi^{(T)}_{t}\equiv\prod_{s\in[t-1]}\bar{p}^{(T)}_{s}$ for
$t\in\\{2,\ldots,T\\}$;

  * •

$q^{(T)}\equiv(q^{(T)}_{t},t\in[T])$, with $q^{(T)}_{t}\equiv
p^{(T)}_{t}\pi^{(T)}_{t}$, noting $q^{(T)}_{1}=p^{(T)}_{1}$ and
$q^{(T)}_{T}=\pi^{(T)}_{T}$; and

  * •

$\mu^{(T)}\equiv\sum_{t\in[T]}\pi^{(T)}_{t}$.

Then: $a)$ $q^{(T)}$ is a probability distribution, $b)$ if
$\mathsf{x}^{(T)}\sim q^{(T)}$ then $\mathbb{P}(\mathsf{x}^{(T)}\geq
t)=\pi^{(T)}_{t}$, and $c)$ $\mathbb{E}[\mathsf{x}^{(T)}]=\mu^{(T)}$.

$a)$ Set $\Sigma_{q}^{(T)}\equiv\sum_{t\in[T]}q^{(T)}_{t}$. It must be shown
that $\Sigma_{q}^{(T)}=1$. The proof is by induction in $T$. The base case
$T=1$ is trivial. Suppose it is true for $T$, i.e., suppose
$\Sigma_{q}^{(T)}=1$, so that
$\Sigma_{q}^{(T)}=\Sigma_{q}^{(T-1)}+\pi^{(T)}_{T}=1$. For induction
hypothesis case $T+1$:

$\displaystyle\Sigma_{q}^{(T+1)}$ $\displaystyle=$
$\displaystyle\sum_{t\in[T-1]}q^{(T+1)}_{t}+q^{(T+1)}_{T}+q^{(T+1)}_{T+1}$
(61) $\displaystyle=$
$\displaystyle\sum_{t\in[T-1]}q^{(T+1)}_{t}+p^{(T+1)}_{T}\pi^{(T+1)}_{T}+\pi^{(T+1)}_{T+1}$
$\displaystyle=$
$\displaystyle\sum_{t\in[T-1]}q^{(T+1)}_{t}+p^{(T+1)}_{T}\pi^{(T+1)}_{T}+\bar{p}^{(T+1)}_{T}\pi^{(T+1)}_{T}$
$\displaystyle=$ $\displaystyle\sum_{t\in[T-1]}q^{(T+1)}_{t}+\pi^{(T+1)}_{T}$
$\displaystyle=$
$\displaystyle\sum_{t\in[T-1]}q^{(T)}_{t}+\pi^{(T)}_{T}=\Sigma_{q}^{(T)}=1$

This proves the induction step.

$b)$ The proof is by induction in $t$, starting with base case $t=T$, for
which the claim holds trivially. Suppose it holds for $t+1$; it is shown below
this implies it holds for $t$:

$\displaystyle\mathbb{P}(\mathsf{x}^{(T)}\geq t)$ $\displaystyle=$
$\displaystyle\mathbb{P}(\mathsf{x}^{(T)}=t)+\mathbb{P}(\mathsf{x}^{(T)}\geq
t+1)$ (62) $\displaystyle=$ $\displaystyle
q^{(T)}_{t}+\pi^{(T)}_{t+1}=p^{(T)}_{t}\pi^{(T)}_{t}+\pi^{(T)}_{t+1}$
$\displaystyle=$ $\displaystyle
p^{(T)}_{t}\pi^{(T)}_{t}+\bar{p}^{(T)}_{t}\pi^{(T)}_{t}=\pi^{(T)}_{t}$

$c)$ This follows from the elementary fact that the expectation of a
nonnegative discrete RV may be expressed in terms of its CCDF as
$\mathbb{E}[\mathsf{x}]=\sum_{t}\mathbb{P}(\mathsf{x}\geq t)$. Application to
the sequence $\tilde{p}^{\rm SSS}$ with $T=t_{\tilde{p}}^{(1)}$ establishes
(28). ∎

##  Appendix G Proof of Prop. 3.

###### Proof:

For finite $(c,x,y)$,

$\lim_{n\uparrow\infty}n\left[\left(1-\frac{c}{n}\right)^{x}-\left(1-\frac{c}{n}\right)^{x+y}\right]=yc.$
(63)

The three claims from Prop. 3 are established in turn.

Claim $i)$: SSR and SSS. By Fact 2 and Thm. 1:

$\displaystyle\frac{\tilde{p}^{\rm SSS}_{t}}{p^{\rm SSR}_{t}}$
$\displaystyle=$
$\displaystyle\frac{(n_{0}^{e,*}-n_{0}^{*})\bar{s}^{t}+n_{0}^{*}}{n\bar{s}^{t}-\frac{\bar{s}}{s}(1-\bar{s}^{t})}\bigg{/}\frac{n_{0}^{e,*}}{n}$
(64) $\displaystyle=$
$\displaystyle\frac{n\bar{s}^{t}n_{0}^{e,*}-n\bar{s}^{t}n_{0}^{*}+nn_{0}^{*}}{n\bar{s}^{t}n_{0}^{e,*}-\frac{\bar{s}}{s}n_{0}^{e,*}+\frac{\bar{s}^{t+1}}{s}n_{0}^{e,*}}.$
(65)

Recall from (4) that $n_{0}^{e,*}=n-\bar{s}^{n_{0}^{*}}(n-n_{0}^{*})$.
Substitution into (65) and rearranging gives $\tilde{p}^{\rm SSS}_{t}/p^{\rm
SSR}_{t}=P(n)/(Q(n)+R(n))$ where, using $s(n)=c/n$,

$\displaystyle P(n)$ $\displaystyle=$ $\displaystyle
n\left(\left(1-\frac{c}{n}\right)^{t}-\left(1-\frac{c}{n}\right)^{n_{0}^{*}+t}\right)$
$\displaystyle+$ $\displaystyle
n_{0}^{*}\left(\left(1-\frac{c}{n}\right)^{n_{0}^{*}+t}-\left(1-\frac{c}{n}\right)^{t}\right)+n_{0}^{*}$
$\displaystyle Q(n)$ $\displaystyle=$ $\displaystyle
n\left[\left(1-\frac{c}{n}\right)^{t}-\left(1-\frac{c}{n}\right)^{n_{0}^{*}+t}+\frac{1}{c}\left[\left(1-\frac{c}{n}\right)^{t+1}\right.\right.$
$\displaystyle-$
$\displaystyle\left.\left.\left(1-\frac{c}{n}\right)+\left(1-\frac{c}{n}\right)^{n_{0}^{*}+1}-\left(1-\frac{c}{n}\right)^{t+n_{0}^{*}+1}\right]\right]$
$\displaystyle R(n)$ $\displaystyle=$ $\displaystyle
n_{0}^{*}\left[\left(1-\frac{c}{n}\right)^{t+n_{0}^{*}}\right.$ (66)
$\displaystyle+$
$\displaystyle\left.\frac{1}{c}\left(\left(1-\frac{c}{n}\right)^{t+n_{0}^{*}+1}-\left(1-\frac{c}{n}\right)^{n_{0}^{*}+1}\right)\right].$

Given (63) it follows that

$\lim_{n\uparrow\infty}P(n)=(c+1)n_{0}^{*},~{}\lim_{n\uparrow\infty}Q(n)=cn_{0}^{*},~{}\lim_{n\uparrow\infty}R(n)=n_{0}^{*}.$
(67)

It follows that $\lim_{n\uparrow\infty}\tilde{p}^{\rm SSS}_{t}/p^{\rm
SSR}_{t}=\lim_{n\uparrow\infty}P(n)/(Q(n)+R(n))=1$. This establishes Claim
$i)$.

Claim $ii)$: SSR and SSC. Since each SSC sample removes a vertex from
$V_{0}\backslash V_{0}^{e,*}$ it follows that $p_{t}^{\rm
SSC}=n_{0}^{e,*}/(n-t+1)$, and as such, Claim $ii)$ follows directly from Fact
2.

Claim $iii)$: SSC and SSS. This follows immediately from Claims $i)$ and
$ii)$. ∎

##  Appendix H Proof of Fact 6

###### Proof:

Let $p_{t}^{\rm SSR}\equiv n^{e,*}_{G}/n$ denote the probability of success
under SSR, with $n^{e,*}_{G}\equiv|V^{e,*}_{G}|$. Recall from Def. 4 that
$\mathsf{c}_{u}=\mathsf{c}^{\rm SSR}_{u}(G,V^{*})$, the random unit cost,
denotes the random number of samples until success, and recall from Fact 2
that this quantity has distribution $\mathrm{geo}\left(p_{t}^{\rm
SSR}\right)$. The random linear cost under SSR, denoted $\mathsf{c}^{\rm
SSR}_{l}(G,V^{*})$, equals
$\mathsf{c}_{l}=\mathsf{x}_{1}+\cdots+\mathsf{x}_{\mathsf{c}_{u}}$, where
$\mathsf{x}_{t}$ is the random extended degree of the star center in sample
$t$. The expected linear cost is

$\displaystyle c_{l}^{\rm SSR}(G,V^{*})$ $\displaystyle=$
$\displaystyle\mathbb{E}[\mathsf{c}_{l}^{\rm SSR}(G,V^{*})]$ $\displaystyle=$
$\displaystyle\mathbb{E}[(\mathsf{x}_{1}+\cdots+\mathsf{x}_{\mathsf{t}-1})+\mathsf{x}_{\mathsf{c}_{u}}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathbb{E}[(\mathsf{x}_{1}+\cdots+\mathsf{x}_{\mathsf{c}_{u}-1})+\mathsf{x}_{\mathsf{c}_{u}}|\mathsf{c}_{u}]]$
$\displaystyle=$
$\displaystyle\mathbb{E}[(\mathsf{c}_{u}-1)\mathbb{E}[\mathsf{x}_{1}|\mathsf{c}_{u}]]+\mathbb{E}[\mathbb{E}[\mathsf{x}_{\mathsf{c}_{u}}|\mathsf{c}_{u}]].$

The first term represents the expected linear cost up until but not including
the cost of the final sample, while the second term is the expected cost of
the final sample. The unsuccessful samples are identically distributed, due to
replacement. The expected cost of an unsuccessful sample is
$\bar{d}^{e,*}_{G}$ while the expected cost of a successful sample is
$d^{e,*}_{G}$. The distribution of the cost of a sample is conditionally
independent of the number of samples, conditioned on whether or not the sample
is successful or not. As such,
$\mathbb{E}[\mathsf{x}_{1}|\mathsf{c}_{u}]=\bar{d}^{e,*}_{G}$,
$\mathbb{E}[\mathsf{x}_{\mathsf{c}_{u}}|\mathsf{c}_{u}]=d^{e,*}_{G}$, and
$\mathbb{E}[\mathsf{c}_{u}]=n/n^{e,*}_{G}$, yielding (33). ∎

##  Appendix I Proof of Prop. 5.

###### Proof:

Consider an urn with $n$ balls of which $k$ are marked. Draw $m$ balls
uniformly at random and let $\mathsf{x}$ be the random number of marked balls
drawn, with support
$\mathcal{S}\equiv\\{\max\\{0,m-(n-k)\\},\ldots,\min\\{k,m\\}\\}$, and
distribution
$\mathbb{P}(\mathsf{x}=l)=\binom{k}{l}\binom{n-k}{m-l}/\binom{n}{m}$ for
$l\in\mathcal{S}$. The expectation of $\mathsf{x}$ is
$\mathbb{E}[\mathsf{x}]=\sum_{l\in\mathcal{S}}l\mathbb{P}(\mathsf{x}=l)=\frac{km}{n}$.
Note this is the same as if the $m$ balls were drawn with replacement, where
$\mathsf{x}\sim\mathrm{bin}(m,k/n)$. This expectation is pertinent in the
derivation below of the expected degree when sampling an ER random graph using
SSC. Pick uniformly at random any vertex in $\mathsf{G}_{t}$, i.e., a vertex
that was not selected in the first $t$ draws. This vertex has a random initial
degree in $\mathsf{G}_{0}$ of $\mathsf{d}_{0}\sim\mathrm{bin}(n-1,s)$. Let
$\mathsf{x}_{t-1}$ be the random number of neighbors that are removed in the
first $t-1$ samples, so that its random degree in $\mathsf{G}_{t}$ is
$\mathsf{d}_{t}=\mathsf{d}_{0}-\mathsf{x}_{t-1}$. Then:

$\displaystyle\mathbb{E}[\mathsf{d}_{t}]$ $\displaystyle=$
$\displaystyle\mathbb{E}[\mathbb{E}[\mathsf{d}_{t}|\mathsf{d}_{0}]]$ (68)
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathbb{E}[\mathsf{d}_{0}-\mathsf{x}_{t-1}|\mathsf{d}_{0}]]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\mathsf{d}_{0}-\mathbb{E}[\mathsf{x}_{t-1}|\mathsf{d}_{0}]]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathsf{d}_{0}-\frac{\mathsf{d}_{0}(t-1)}{n-1}\right]$
$\displaystyle=$
$\displaystyle\left(1-\frac{t-1}{n-1}\right)\mathbb{E}[\mathsf{d}_{0}]$
$\displaystyle=$ $\displaystyle\left(1-\frac{t-1}{n-1}\right)(n-1)s$
$\displaystyle=$ $\displaystyle(n-1)s-(t-1)s=(n-t)s.$

The proof that
$\mathbb{E}[\mathsf{x}_{t-1}|\mathsf{d}_{0}]=\frac{\mathsf{d}_{0}(t-1)}{n-1}$
comes from the discussion above, where the $n-1$ “balls” are the potential
neighbors in $\mathsf{G}_{0}$ of the randomly selected vertex, of which the
$\mathsf{d}_{0}$ marked “balls” are the actual neighbors, and $t-1$ “balls”
are drawn.

The event $\\{\mathsf{c}_{u}\geq t\\}$, conditioned on $\mathsf{n}^{e,*}_{0}$,
means the first $t-1$ samples fail to find the target. As graph
$\mathsf{G}_{u-1}$ has order $n-u+1$, conditioned on the failure of each
previous sample, sample $u\in[t-1]$ fails with probability
$1-\mathsf{n}^{e,*}_{0}/(n-u+1)$. As these random outcomes are independent:

$\displaystyle\mathbb{P}(\mathsf{c}_{u}\geq t|\mathsf{n}^{e,*}_{0})$
$\displaystyle=$
$\displaystyle\prod_{u=1}^{t-1}\left(1-\frac{\mathsf{n}^{e,*}_{0}}{n-u+1}\right).$
(69)

The maximum number of samples possible under SSC, $\mathsf{c}_{\rm max}^{\rm
SSC}(\mathsf{n}^{e,*}_{0})$, is $n-\mathsf{n}^{e,*}_{0}+1$. Substitution into
(35) yields (38). ∎

##  Appendix J Proof of Prop. 6.

###### Proof:

The proof follows the same lines as that of Prop. 5, i.e., we establish $i)$
$\mathbb{E}[\mathsf{d}_{t}]$, $ii)$ $\mathsf{c}_{\rm max}^{\rm
SSS}|\mathsf{n}^{e,*}_{0}$, and $iii)$ $\mathbb{P}(\mathsf{c}_{u}\geq
t|\mathsf{n}^{e,*}_{0})$.

$i)$ $\mathbb{E}[\mathsf{d}_{t}]$. The expected degree of the star center in
sample $t$ is obtained as follows. Consider any vertex not yet removed by the
first $t-1$ samples. Conditioned on $\mathsf{n}_{t-1}$, this vertex has a
random degree
$\mathsf{d}_{t}|\mathsf{n}_{t-1}\sim\mathrm{bin}(\mathsf{n}_{t-1}-1,s)$, and
as such

$\mathbb{E}[\mathsf{d}_{t}]=\mathbb{E}[\mathbb{E}[\mathsf{d}_{t}|\mathsf{n}_{t-1}]]=s\mathbb{E}[\mathsf{n}_{t-1}-1],$
(70)

By case $ii)$ (46) in Lem. 5:

$\displaystyle\mathbb{E}[\mathsf{d}_{t}]$ $\displaystyle=$ $\displaystyle
s(\mathbb{E}[\mathsf{n}_{t-1}]-1)$ (71) $\displaystyle=$ $\displaystyle
s\left(n\bar{s}^{t-1}-\frac{\bar{s}}{s}(1-\bar{s}^{t-1})-1\right)$
$\displaystyle=$ $\displaystyle ns\bar{s}^{t-1}-\bar{s}(1-\bar{s}^{t-1})-s$

and as such

$\displaystyle\mathbb{E}[\mathsf{d}_{t}^{e}]$ $\displaystyle=$ $\displaystyle
ns\bar{s}^{t-1}-\bar{s}(1-\bar{s}^{t-1})+\bar{s}$ (72) $\displaystyle=$
$\displaystyle ns\bar{s}^{t-1}+\bar{s}^{t}=((n-1)s+1)\bar{s}^{t-1}$

$ii)$ $c_{\rm max}^{\rm SSS}(\mathsf{n}^{e,*}_{0})$. The maximum number of
samples before the target set is reached may be upper bounded by
$t^{(1)}_{\tilde{p}}$ the time at which $\tilde{p}_{t+1}^{\rm SSS}=1$ given in
(24) of Thm. 1, i.e. $c_{\rm max}^{\rm SSS}(\mathsf{n}^{e,*}_{0})\leq
t^{(1)}_{\tilde{p}}$.

$iii)$ $\mathbb{P}(\mathsf{c}_{u}\geq t|\mathsf{n}^{e,*}_{0})$. The
probability of requiring $t$ or more samples under SSS is approximated by
leveraging the results in Thm. 2, namely,

$\mathbb{P}(\mathsf{c}_{u}\geq
t|\mathsf{n}^{e,*}_{0})\approx\prod_{u=1}^{t-1}(1-\tilde{p}_{u}^{\rm SSS}),$
(73)

where $\tilde{p}_{t}^{\rm SSS}$ is defined in (22) in Thm. 1.

As in the case of Prop. 5, (39) follows by substitution. ∎