*

# Fourier spectral-timing techniques for the study of accreting black holes

Adam Ingram  School of Mathematics, Statistics and Physics, Newcastle
University, Herschel Building, Newcastle Upon Tyne, UK
<EMAIL_ADDRESS>A. Ingram

(26 April 2016; 6 June 2016; 6 June 2016)

###### Abstract

The X-ray signal from active galactic nuclei and black hole X-ray binaries is
highly variable on a range of timescales. This variability can be exploited to
map the region of interest close to the black hole, which is far too small to
directly image for all but two black holes in the Universe. Spectral-timing
techniques provide causal information by combining timing and spectral
information. I present a brief review of such techniques, focusing on two
examples: X-ray reverberation mapping and phase-resolved spectroscopy of low
frequency quasi-periodic oscillations (LF QPOs). The former provides a means
to diagnose the accretion geometry and measure parameters such as black hole
mass, and the latter gives perhaps the best constraints we currently have as
to the enigmatic LF QPO mechanism.

###### keywords:

X-rays: binaries, accretion, black hole physics, keyword4

††articletype: Article Type

(2022), Fourier spectral-timing techniques for the study of accreting black
holes, Astronomical Notes, 2022;00:1–6.

##  1 Introduction

Accretion onto black holes (BHs) can efficiently produce huge X-ray
luminosities, lighting up the vicinity of the horizon. This process happens in
active galactic nuclei (AGNs), whereby a supermassive BH accretes material
from its host galaxy, and in BH X-ray binaries (XRBs), whereby a stellar-mass
BH accretes from its binary partner. In both object classes, accretion occurs
via a thin, accretion disk and, close to the hole, a cloud of hot electrons
commonly referred to as the corona. The shape and physical nature of the
corona is still a subject of hot debate, with models including a layer
sandwiching the disk (Galeev ., 1979; Haardt Maraschi, 1991), a large scale-
height accretion flow located inside of a truncated disk (Eardley ., 1975;
Ichimaru, 1977) and a compact or vertically extended region at the base of the
out-flowing jet (Miyamoto Kitamoto, 1991; Markoff ., 2005; Miniutti ., 2004).
The region of interest is far too small to directly image, necessitating
sophisticated mapping techniques to infer the nature of the corona. Spectral-
timing methods do just this, exploiting the rapid time variability routinely
observed in the X-ray flux. Since signal to noise is typically low for each
variability cycle but we observe many cycles, such rapid variability is best
studied in the Fourier domain.

The X-ray spectrum includes a multi-temperature blackbody component
contributed by the disk (Shakura Sunyaev, 1973; Novikov Thorne, 1973) and a
cut-off power-law component contributed by Compton up-scattering in the corona
(Thorne Price, 1975; Sunyaev Truemper, 1979). X-rays from the corona that
irradiate the disk are reprocessed and re-emitted by the disk to form a so-
called reflection spectrum that includes features such as a $\sim 6.4$ keV
iron K$\alpha$ line and a broad ‘Compton hump’ peaking at $\sim 20-30$ keV
(Matt ., 1991; Ross Fabian, 2005; García ., 2013). General relativistic
effects distort the reflection spectrum seen by the observer, leading to the
iron line being broadened by rapid disk orbital motion and skewed by
gravitational redshift and Doppler boosting (Fabian ., 1989). The spectrum of
XRBs is observed to transition from the power-law dominated hard state to the
disk dominated soft state, via the intermediate state, on timescales of
$\sim$weeks-years (e.g. Belloni, 2010; Done ., 2007). AGN, on the other hand,
evolve much more slowly, since all characteristic timescales scale linearly
with BH mass.

Figure 1: Demonstrations of reverberation. a) A simulated direct signal (grey)
smoothed and lagged (red and blue). b) Time lag vs Fourier frequency between
direct and reflected signals (black) and between two energy bands (red). c)
Lag-energy spectrum calculated with the same reverberation model as (b).

The rapid X-ray variability includes broad band stochastic noise and quasi-
periodic oscillations (QPOs). The broad band noise has a roughly constant
root-mean-squared (rms) variability amplitude between low and high frequency
breaks that scale with spectral state and BH mass (McHardy ., 2006). Different
kinds of QPO are observed in XRBs, with the main division being between low
frequency (LF) QPOs (centroid frequency $\nu_{\rm qpo}\lesssim 30$ Hz) and
high frequency (HF) QPOs ($\nu_{\rm qpo}\gtrsim 30$ Hz). Whereas HF QPOs are
very weak and rare features (Belloni ., 2012), LF QPOs are very strong and
commonly observed (AR. Ingram Motta, 2019). The X-ray timing properties evolve
in a manner tightly correlated with the spectral state transitions (Wijnands
., 1999; Psaltis ., 1999). In AGN, QPOs are notoriously difficult to observe
due to the long timescales and irregular sampling involved (Vaughan Uttley,
2005). As such, most known AGN QPOs are thought to be mass-scaled analogies of
HF QPOs (e.g. Gierliński ., 2008).

In this proceeding of the conference ‘Black hole accretion under the X-ray
microscope’ (14-17 June 2022 at ESAC, Madrid), I will briefly review the
spectral-timing methods at our disposal to learn more about the accretion
geometry, the origin of QPOs and even attempt to measure the fundamental BH
parameters: mass and spin. I will focus on two examples: in Section 2 X-ray
reverberation mapping, and in Section 3 phase-resolved spectroscopy of LF
QPOs. Conclusions are presented in Section 4.

##  2 Reverberation mapping

Reverberation mapping exploits the light crossing delay between X-rays that
travel directly from the corona to the observer, and those that take a longer
path by first reflecting off the accretion disk. This is demonstrated
conceptually in Fig 1a. The reflected signal (red) is a lagged and smoothed
version of the direct signal (grey, generated using the algorithm of Timmer
Koenig 1995). The smoothing is due to the different travel time of rays that
reflect off of different parts of the disk. Mathematically, this lagging and
smoothing can be achieved by convolving with an impulse-response function
(e.g. Uttley ., 2014; Bambi ., 2021). Here, I have simply used a top-hat
function (with parameters designed to greatly exaggerate the salient effects),
whereas modern reverberation models calculate an impulse-response function by
assuming a geometry and accounting for all relativistic effects (e.g. A.
Ingram ., 2019). Since the light crossing delays associated with reflection
from the inner disk are shorter than those for the outer disk, the reflection
signal from the inner disk only (blue) is lagged and smoothed to a lesser
degree than that from the entire disk (red). Therefore, if we could isolate
only the fastest variability, we could isolate the signal from the inner disk
only to build up a map of the disk. How can we isolate different variability
timescales? We take a Fourier transform!

Fig 1b shows the time lag between the direct and reflected signal (black line)
as a function of Fourier frequency, this time with the impulse-response
function calculated for an XRB using the reverberation model reltrans (A.
Ingram ., 2019). The Fourier frequency-dependent phase lag between two signals
can be calculated from the argument of the complex cross-spectrum (van der
Klis ., 1987) and the time lag is then recovered from division by $2\pi\nu$,
where $\nu$ is Fourier frequency (see e.g. Uttley . 2014 for a detailed
review). The lags in Fig 1b are independent of the driving signal, they are
purely governed by the impulse-response function. The $\sim 2.2$ ms lag seen
at low frequencies is the extra time it takes for most of the reflected flux
to arrive at our detector relative to the direct flux. The lag reduces for
higher frequencies ($\gtrsim 0.1$ Hz) because higher Fourier frequencies
isolate reflection from smaller disk radii, for which the light crossing delay
is shorter. For the highest frequencies, we see phase-wrapping. This happens
when the reverberation lag is greater than the Fourier period, or in other
words the reverberation phase lag is $>\pi$ or $<-\pi$ radians. The same
effect can be seen in movies when car wheels appear to be moving backwards
because they almost complete a full rotation between camera frames.

Unfortunately, X-ray photons detected from accreting BHs do not come labelled
as either direct or reflected. They must instead be separated out by their
different spectra111In principle they can also be separated out by their
different polarization properties but this is challenging with current
instrumentation (A. Ingram, 2022): a cut-off power law continuum for the
direct photons and a reflection spectrum for the reflected photons. The red
line in Fig 1b shows the time lag between $6.4$ keV and $10$ keV photons. The
$6.4$ keV band (containing the iron line) lags behind the 10 keV band because
it includes a greater fraction of reflected photons. However, the lag is
diluted compared to the true reverberation lag because each band includes some
direct and some reflected photons.

Figure 2: Lag-energy spectrum of MAXI J1820+070 demonstrating featureless
continuum lags at low frequencies (top) and reverberation features at high
frequencies (bottom).

The clearest observational manifestation of reverberation is in the lag-energy
spectrum, which is derived from a series of cross-spectra between the count
rate in each energy band and one common reference band (Kotov ., 2001). Fig 1c
shows by how much time photons of each energy lag behind 10 keV photons (i.e.
here the reference band is narrow and centered on 10 keV, but in practice
using the full telescope band-pass maximises signal to noise; e.g. A. Ingram
2019). We see an iron line and Compton hump feature in the lag-energy
spectrum, which result from there being more reflection, and therefore less
dilution, at these energies. So do we see such features in observational lag-
energy spectra? The short answer is yes. Fig 2 (bottom) shows the clearest
example of an iron K reverberation feature for an XRB (Kara ., 2019). Similar
iron K reverberation features have been observed for $\sim 25$ AGN (Kara .,
2016) and the amplitude of the lag scales with BH mass (De Marco ., 2013).
Therefore, the lag is much larger for AGN than for XRBs, simply because the
light crossing time of the system scales linearly with BH mass.

However, reverberation lags are only visible for high Fourier frequencies
($\nu\gtrsim 3~{}[10~{}M_{\odot}]/M$ in practice; e.g. Kara . 2016), i.e.
considering only the most rapid variability in the system. The low frequency
lag-energy spectrum is instead featureless (Fig 2 top). Since there are no
reverberation features, these lags are not associated with reflection and must
be caused by non-linear spectral variability of the continuum. Note that these
‘continuum lags’ are much larger than the reverberation lags. It is very
likely that reverberation lags are still present at low frequency, but they
are simply drowned out by the much larger continuum lags. In fact, it is often
possible to see a dip in the low frequency lag-energy spectrum at $\sim 6.4$
keV (Kotov ., 2001). This can be explained by reverberation: the comparatively
small reverberation lag dilutes the larger continuum lag more at the iron line
energy than at any other, leading to a dip (Mastroserio ., 2018).

The simplest way to proceed with reverberation modelling is to simply ignore
the continuum lags by modelling only the high frequency lag-energy spectrum
(Cackett ., 2014; A. Ingram ., 2019). Moreover, the simplest model to employ
is the lamppost model, whereby the corona is assumed to be a point-like source
some height $h$ above the BH (Matt ., 1992). However, this approach provides
only weak constraints on the BH mass, since the same reverberation lag results
if $h$ is many small gravitational radii ($r_{g}=GM/c^{2}$) or only a few
large gravitational radii. The degeneracy can be broken either by considering
many observations, over which the coronal height changes but the BH mass stays
the same (Alston ., 2020), or by modelling multiple frequency ranges –
requiring a model for the continuum lags. The continuum lags are typically
attributed to inward propagating fluctuations in mass accretion rate
(Lyubarskii, 1997; Arévalo Uttley, 2006; A. Ingram van der Klis, 2013), but
accurately modelling this process and reverberation mapping simultaneously is
too computationally intensive to fit the model directly to data (Wilkins .,
2016). The ‘two blobs’ model of Chainakun Young (2017) simplifies the problem
by considering propagating fluctuations between two lamppost sources. The
model reltrans (A. Ingram ., 2019) instead accounts for continuum lags by
introducing fluctuations in the continuum power-law index (Mastroserio .,
2018).

reltrans has been used to fit the lag-energy spectrum in multiple frequency
ranges, simultaneously with the time-averaged spectrum, for several AGNs and
XRBs (e.g. Mastroserio ., 2020; Wang ., 2021). For Cygnus X-1, it was even
possible to also fit the rms-energy spectrum (the energy dependence of rms
variability amplitude) in multiple frequency ranges. This extra constraint
informs on how destructive interference between rays that reflected from
different parts of the disk washes out variability in the reflection spectrum
(i.e. exactly the smoothing shown in Fig 1a). The resulting mass estimate of
$M=26.0\pm 5.5~{}M_{\odot}$ (Mastroserio ., 2019) agrees with the dynamical
measurement of $M=21.2\pm 2.2~{}M_{\odot}$ (Miller-Jones ., 2021). Other
objects have proved more challenging: the Mastroserio . (2020) X-ray
reverberation mass of Mrk 335 disagrees with existing optical reverberation
measurements (Peterson ., 2004), and fitting the lag-energy spectra of MAXI
J1820+070 yields a very different source height to fits of the same model to
the time-averaged spectrum (Wang ., 2021). Part of the problem may be the
over-simplicity of the lamppost geometry. Also, the fits to Mrk 335 and MAXI
J1820+070 (respectively using XMM and NICER data) may be mainly driven by the
soft X-rays, which carry the most model uncertainty and are not present in the
RXTE data used for the Cygnus X-1 mass estimate.

##  3 Quasi-periodic oscillations

Spectral-timing methods are also key tools to diagnose the mechanism behind
QPOs. The best example to focus on for this review is that of Type-C QPOs
($0.1~{}{\rm Hz}\lesssim\nu_{\rm qpo}\lesssim 30$ Hz), which are by far the
most commonly observed QPO class (see Casella . 2005 for a description of the
Type A-B-C classification) and are also very strong signals on which to apply
spectral-timing methods. Studies of the QPO rms-energy spectrum reveal that
the Comptonised component oscillates with higher amplitude than the disk
(Sobolewska Życki, 2006), indicating that the QPO is modulated in the corona.
Population studies provide strong evidence that Type-C QPOs are geometrical in
origin; i.e. the accretion geometry is oscillating quasi-periodically.
Firstly, the QPO amplitude is larger for higher inclination (more edge-on)
systems (Motta ., 2015). Secondly, low inclination sources always show soft
phase lags222Note that the cyclical nature of QPOs makes it more intuitive to
think about phase lags, whereas reverberation is more intuitively considered
in terms of time lags. on the QPO fundamental frequency, whereas high
inclination objects display soft lags for $\nu_{\rm qpo}\gtrsim 2$ Hz (van den
Eijnden ., 2017).

Currently the most powerful QPO diagnostic is provided by QPO phase-resolved
spectroscopy: constraining the flux-energy spectrum as a function of QPO
phase. Of particular interest is the QPO phase-dependence of the iron line
profile, since this can in principle be used to reconstruct the accretion
geometry as a function of QPO phase. A prominent class of QPO models attribute
the QPO to Lense-Thirring precession (see AR. Ingram Motta 2019 for details) –
a nodal precession of orbits driven by the BH spin. In the model of A. Ingram
. (2009) it is the corona that undergoes Lense-Thirring precession, in which
case the iron line is predicted to rock from red to blue shifted throughout
each QPO cycle as respectively receding and approaching disk azimuths are
preferentially illuminated (A. Ingram Done, 2012). QPO phase-resolved
spectroscopy is, however, technically challenging because QPO phase does not
increase linearly, or even deterministically, with time (e.g. Morgan ., 1997).
The QPO waveform can therefore not be measured by simply folding on the QPO
period. One method to circumvent this problem is to first attempt to isolate
the QPO signal from the broad band noise by filtering the light curve, and
then assign QPO phase values to each time bin from peaks, troughs and mean
crossings of the filtered signal (Tomsick Kaaret, 2001; van den Eijnden .,
2016; HS. Krawczynski ., 2016).

However, a higher signal to noise can be achieved by reconstructing the phase-
resolved spectrum from Fourier spectral-timing products. Almost all of the
information is contained in the rms-energy spectrum and the lag-energy
spectrum. Fig 3 demonstrates this: lines are generated by a model in which a
power-law continuum and Gaussian iron line oscillate periodically with two
harmonics. Oscillations of the power-law index and normalisation drive the
continuum shape of the lag-energy (top) and rms-energy (bottom) spectra at the
first (red) and second (blue) harmonics. Oscillations of the Gaussian
centroid, width and normalisation drive the ‘wiggles’ around $\sim 6.4$ keV.
The predicted quasi-periodic modulation of the iron line centroid energy
therefore translates to predicted wiggles in the lag-energy and rms-energy
spectra at the QPO first and second harmonic.

Since the first two harmonics typically dominate the QPO signal, the only
information missing from the full phase-resolved spectra here is the phase
difference between the two harmonics (A. Ingram van der Klis, 2015; de Ruiter
., 2019). This is because the rms-energy spectrum measures the relative
amplitude of the harmonics and the lag-energy spectra measures how the phase
of each harmonic in each energy band corresponds to the phase of the same
harmonic in the reference band, but does not compare the phase of the two
harmonics. The method of A. Ingram van der Klis (2015), later improved upon by
A. Ingram . (2016) and Nathan . (2022), essentially includes this extra phase
difference information by adjusting the second harmonic lag-energy spectra by
the phase difference measured in the reference band. On the other hand, the
cross-correlation method of Stevens Uttley (2016) ignores the phase difference
information.

A. Ingram . (2016) used the Fourier reconstruction method to discover a QPO
phase-dependence of the iron line centroid energy in H 1743-322 (black points
in Fig 3). This constitutes strong evidence in favour of a precession origin
of the Type-C QPO. However, other models can potentially explain this, for
example a spiral density wave in the disk (Tagger Pellat, 1999). More advanced
phase-resolved spectral modelling of the same data revealed a QPO phase-
dependence of the reflection fraction (A. Ingram ., 2017), which provides
definitive evidence for a geometric QPO origin. Similar results were obtained
for GRS 1915+105 by Nathan . (2022). A detailed review of QPO models and
observational constraints can be found in AR. Ingram Motta (2019).

Figure 3: Lag-energy spectrum (top) and rms-energy spectrum (bottom) of the
QPO fundamental (red) and second harmonic (blue). Solid lines are generated by
a model in which a power law plus Gaussian iron line spectral model oscillates
periodically on both harmonics. Black points are a $\sim 65$ ks exposure sub-
set of XMM-Newton data from the $200$ ks XMM-Newton plus $70$ ks NuSTAR
observation analysed by A. Ingram . (2016).

##  4 Conclusions

Spectral-timing techniques provide insights into the inner workings of
accreting BHs by providing causal information; for example whether variations
in one spectral component precede or delay those in another. The key tool for
spectral-timing is the Fourier cross-spectrum, since the variability amplitude
can be derived from its modulus and the time lag between two signals can be
derived from its argument. This short review has covered two prominent
examples of Fourier spectral-timing: X-ray reverberation mapping and QPO
phase-resolved spectroscopy; both of which make heavy use of the cross-
spectrum. I have briefly reviewed the key concepts that underpin both methods,
and summarised the current state of the art of the field. Both methods with
benefit greatly from future high throughput X-ray missions, since higher count
rates reduce counting errors. In particular, this will enable reverberation
mapping studies to push to higher Fourier frequencies (ideally into the phase-
wrapping regime) and will enable the phase-resolved spectroscopic studies we
currently conduct for LF QPOs to also be applied to HF QPOs. Combination with
X-ray polarisation measurements, which are now finally achievable (H.
Krawczynski ., 2022) and in the near future may be available with greatly
improved signal to nose (De Rosa ., 2019), will hugely complement the
spectral-timing tools discussed here.

## References

  * Alston . (2020) Alston2020Alston, WN., Fabian, AC., Kara, E. et al.  202001,  Nature Astronomy4597-602.  10.1038/s41550-019-1002-x
  * Arévalo Uttley (2006) Arevalo2006Arévalo, P. Uttley, P.  200604,  MNRAS367801-814.  10.1111/j.1365-2966.2006.09989.x
  * Bambi . (2021) Bambi2021Bambi, C., Brenneman, LW., Dauser, T. et al.  202108,  Space Sci. Rev.217565.  10.1007/s11214-021-00841-8
  * Belloni (2010) Belloni2010Belloni, TM.  201003,  Lecture Notes in Physics79453-+.  10.1007/978-3-540-76937-8_3
  * Belloni . (2012) Belloni2012Belloni, TM., Sanna, A. Méndez, M.  201211,  MNRAS4261701-1709.  10.1111/j.1365-2966.2012.21634.x
  * Cackett . (2014) Cackett2014Cackett, EM., Zoghbi, A., Reynolds, C., Fabian, AC., Kara, E., Uttley, P. Wilkins, DR.  201403,  MNRAS4382980-2994.  10.1093/mnras/stt2424
  * Casella . (2005) Casella2005Casella, P., Belloni, T. Stella, L.  200508,  ApJ629403-407.  10.1086/431174
  * Chainakun Young (2017) Chainakun2017Chainakun, P. Young, AJ.  201703,  MNRAS4653965-3976.  10.1093/mnras/stw2964
  * De Marco . (2013) DeMarco2013De Marco, B., Ponti, G., Cappi, M. et al.  201305,  MNRAS4312441-2452.  10.1093/mnras/stt339
  * De Rosa . (2019) DeRosa2019De Rosa, A., Uttley, P., Gou, L. et al.  201902,  Science China Physics, Mechanics, and Astronomy62229504.  10.1007/s11433-018-9297-0
  * de Ruiter . (2019) DeRuiter2019de Ruiter, I., van den Eijnden, J., Ingram, A. Uttley, P.  201905,  MNRAS4853834-3844.  10.1093/mnras/stz665
  * Done . (2007) Done2007Done, C., Gierlinski, M. Kubota, A.  200712,  A&A151-66.  10.1007/s00159-007-0006-1
  * Eardley . (1975) Eardley1975Eardley, DM., Lightman, AP. Shapiro, SL.  197508,  ApJ199L153-L155.  10.1086/181871
  * Fabian . (1989) Fabian1989Fabian, AC., Rees, MJ., Stella, L. White, NE.  198905,  MNRAS238729-736.
  * Galeev . (1979) Galeev1979Galeev, AA., Rosner, R. Vaiana, GS.  197904,  ApJ229318-326.  10.1086/156957
  * García . (2013) Garcia2013García, J., Dauser, T., Reynolds, CS., Kallman, TR., McClintock, JE., Wilms, J. Eikmann, W.  201305,  ApJ768146.  10.1088/0004-637X/768/2/146
  * Gierliński . (2008) Gierlinski2008Gierliński, M., Middleton, M., Ward, M. Done, C.  200809,  Nature455369-371.  10.1038/nature07277
  * Haardt Maraschi (1991) Haardt1991Haardt, F. Maraschi, L.  199110,  ApJ380L51-L54.  10.1086/186171
  * Ichimaru (1977) Ichimaru1977Ichimaru, S.  197706,  ApJ214840-855.  10.1086/155314
  * A. Ingram (2019) Ingram2019aIngram, A.  201911,  MNRAS48933927-3938.  10.1093/mnras/stz2409
  * A. Ingram (2022) Ingram2022aIngram, A.  202206,  arXiv e-printsarXiv:2206.11671.
  * A. Ingram Done (2012) Ingram2012Ingram, A. Done, C.  201201,  MNRAS4192369-2378.  10.1111/j.1365-2966.2011.19885.x
  * A. Ingram . (2009) Ingram2009Ingram, A., Done, C. Fragile, PC.  200907,  MNRAS397L101-L105.  10.1111/j.1745-3933.2009.00693.x
  * A. Ingram . (2019) Ingram2019Ingram, A., Mastroserio, G., Dauser, T., Hovenkamp, P., van der Klis, M. García, JA.  2019Sep,  MNRAS4881324-347.  10.1093/mnras/stz1720
  * A. Ingram van der Klis (2015) Ingram2015Ingram, A. van der Klis, M.  201502,  MNRAS4463516-3525.  10.1093/mnras/stu2373
  * A. Ingram . (2017) Ingram2017Ingram, A., van der Klis, M., Middleton, M., Altamirano, D. Uttley, P.  201701,  MNRAS4642979-2991.  10.1093/mnras/stw2581
  * A. Ingram . (2016) Ingram2016Ingram, A., van der Klis, M., Middleton, M. et al.  201609,  MNRAS4611967-1980.  10.1093/mnras/stw1245
  * A. Ingram van der Klis (2013) Ingram2013Ingram, A. van der Klis, Mvd.  201309,  MNRAS4341476-1485.  10.1093/mnras/stt1107
  * AR. Ingram Motta (2019) Ingram2019bIngram, AR. Motta, SE.  201909,  New A Rev.85101524.  10.1016/j.newar.2020.101524
  * Kara . (2016) Kara2016Kara, E., Alston, WN., Fabian, AC., Cackett, EM., Uttley, P., Reynolds, CS. Zoghbi, A.  201610,  MNRAS462511-531.  10.1093/mnras/stw1695
  * Kara . (2019) Kara2019Kara, E., Steiner, JF., Fabian, AC. et al.  2019Jan,  Nature5657738198-201.  10.1038/s41586-018-0803-x
  * Kotov . (2001) Kotov2001Kotov, O., Churazov, E. Gilfanov, M.  200111,  MNRAS327799-807.  10.1046/j.1365-8711.2001.04769.x
  * H. Krawczynski . (2022) Henric2022Krawczynski, H., Muleri, F., Dovčiak, M. et al.  202206,  arXiv e-printsarXiv:2206.09972.
  * HS. Krawczynski . (2016) Henric2016Krawczynski, HS., Stern, D., Harrison, FA. et al.  201602,  Astroparticle Physics758-28.  10.1016/j.astropartphys.2015.10.009
  * Lyubarskii (1997) Lyubarskii1997Lyubarskii, YE.  199712,  MNRAS292679.  10.1093/mnras/292.3.679
  * Markoff . (2005) Markoff2005Markoff, S., Nowak, MA. Wilms, J.  200512,  ApJ6351203-1216.  10.1086/497628
  * Mastroserio . (2018) Mastroserio2018Mastroserio, G., Ingram, A. van der Klis, M.  201804,  MNRAS4754027-4042.  10.1093/mnras/sty075
  * Mastroserio . (2019) Mastroserio2019Mastroserio, G., Ingram, A. van der Klis, M.  201909,  MNRAS4881348-361.  10.1093/mnras/stz1727
  * Mastroserio . (2020) Mastroserio2020Mastroserio, G., Ingram, A. van der Klis, M.  202011,  MNRAS49844971-4982.  10.1093/mnras/staa2735
  * Matt . (1991) Matt1991Matt, G., Perola, GC. Piro, L.  199107,  A&A24725-34.
  * Matt . (1992) Matt1992Matt, G., Perola, GC., Piro, L. Stella, L.  199204,  A&A25763-68.
  * McHardy . (2006) McHardy2006McHardy, IM., Koerding, E., Knigge, C., Uttley, P. Fender, RP.  200612,  Nature4447120730-732.  10.1038/nature05389
  * Miller-Jones . (2021) Miller-Jones2021Miller-Jones, JCA., Bahramian, A., Orosz, JA. et al.  202103,  Science37165331046-1049.  10.1126/science.abb3363
  * Miniutti . (2004) Miniutti2004Miniutti, G., Fabian, AC. Miller, JM.  200406,  MNRAS351466-472.  10.1111/j.1365-2966.2004.07794.x
  * Miyamoto Kitamoto (1991) Miyamoto1991Miyamoto, S. Kitamoto, S.  199106,  ApJ374741-743.  10.1086/170158
  * Morgan . (1997) Morgan1997Morgan, EH., Remillard, RA. Greiner, J.  199706,  ApJ482993-+.  10.1086/304191
  * Motta . (2015) Motta2015Motta, SE., Casella, P., Henze, M., Muñoz-Darias, T., Sanna, A., Fender, R. Belloni, T.  201502,  MNRAS4472059-2072.  10.1093/mnras/stu2579
  * Nathan . (2022) Nathan2022Nathan, E., Ingram, A., Homan, J. et al.  202203,  MNRAS5111255-279.  10.1093/mnras/stab3803
  * Novikov Thorne (1973) Novikov1973Novikov, ID. Thorne, KS.  1973,  Astrophysics of black holes. Astrophysics of black holes.  C. Dewitt BS. Dewitt (), Black Holes (Les Astres Occlus) Black Holes (Les Astres Occlus) 343-450.  Gordon and Breach, New York.
  * Peterson . (2004) Peterson2004Peterson, BM., Ferrarese, L., Gilbert, KM. et al.  200410,  ApJ613682-699.  10.1086/423269
  * Psaltis . (1999) Psaltis1999Psaltis, D., Belloni, T. van der Klis, M.  199907,  ApJ520262-270.  10.1086/307436
  * Ross Fabian (2005) Ross2005Ross, RR. Fabian, AC.  200503,  MNRAS358211-216.  10.1111/j.1365-2966.2005.08797.x
  * Shakura Sunyaev (1973) Shakura1973Shakura, NI. Sunyaev, RA.  1973,  A&A24337-355.
  * Sobolewska Życki (2006) Sobolewska2006Sobolewska, MA. Życki, PT.  200607,  MNRAS370405-414.  10.1111/j.1365-2966.2006.10489.x
  * Stevens Uttley (2016) Stevens2016Stevens, AL. Uttley, P.  201605,  ArXiv e-prints.
  * Sunyaev Truemper (1979) Sunyaev1979Sunyaev, RA. Truemper, J.  197906,  Nature279506-508.  10.1038/279506a0
  * Tagger Pellat (1999) Tagger1999Tagger, M. Pellat, R.  199909,  A&A3491003-1016.
  * Thorne Price (1975) Thorne1975Thorne, KS. Price, RH.  197502,  ApJ195L101-L105.  10.1086/181720
  * Timmer Koenig (1995) Timmer1995Timmer, J. Koenig, M.  199508,  A&A300707.
  * Tomsick Kaaret (2001) Tomsick2001Tomsick, JA. Kaaret, P.  200102,  ApJ548401-409.  10.1086/318683
  * Uttley . (2014) Uttley2014Uttley, P., Cackett, EM., Fabian, AC., Kara, E. Wilkins, DR.  201408,  A&A Rev.2272.  10.1007/s00159-014-0072-0
  * van den Eijnden . (2016) vandeneijnden2016van den Eijnden, J., Ingram, A. Uttley, P.  201606,  MNRAS45843655-3666.  10.1093/mnras/stw610
  * van den Eijnden . (2017) vandeneijnden2017van den Eijnden, J., Ingram, A., Uttley, P., Motta, SE., Belloni, TM. Gardenier, DW.  201701,  MNRAS4642643-2659.  10.1093/mnras/stw2634
  * van der Klis . (1987) vanderKlis1987van der Klis, M., Hasinger, G., Stella, L., Langmeier, A., van Paradijs, J. Lewin, WHG.  198708,  ApJ319L13-L18.  10.1086/184946
  * Vaughan Uttley (2005) Vaughan2005Vaughan, S. Uttley, P.  200509,  MNRAS362235-244.  10.1111/j.1365-2966.2005.09296.x
  * Wang . (2021) Wang2021Wang, J., Mastroserio, G., Kara, E. et al.  202103,  ApJ9101L3.  10.3847/2041-8213/abec79
  * Wijnands . (1999) Wijnands1999Wijnands, R., Homan, J. van der Klis, M.  199911,  ApJ526L33-L36.  10.1086/312365
  * Wilkins . (2016) Wilkins2016Wilkins, DR., Cackett, EM., Fabian, AC. Reynolds, CS.  201605,  MNRAS458200-225.  10.1093/mnras/stw276


# Nested Group Testing Procedures for Screening

Yaakov Malinovsky and Paul S. Albert  Department of Mathematics and
Statistics, University of Maryland, Baltimore County, Baltimore, MD 21250, USA
Biostatistics Branch, Division of Cancer Epidemiology and Genetics, National
Cancer Institute, Rockville, MD 20850, USA. The work was supported by the
National Cancer Institute Intramural Program.

###### Abstract

This article reviews a class of adaptive group testing procedures that operate
under a probabilistic model assumption as follows. Consider a set of $N$
items, where item $i$ has the probability $p$ ($p_{i}$ in the generalized
group testing) to be defective, and the probability $1-p$ to be non-defective
independent from the other items. A group test applied to any subset of size
$n$ is a binary test with two possible outcomes, positive or negative. The
outcome is negative if all $n$ items are non-defective, whereas the outcome is
positive if at least one item among the $n$ items is defective. The goal is
complete identification of all $N$ items with the minimum expected number of
tests.

Keywords: Dynamic programming; Disease screening; Information theory;
Partition problem; Optimal design

##  1 Introduction

In the last few months of the COVID-19 pandemic, the mostly-forgotten practice
of group testing has been raised again in many countries as an efficient
method for addressing an epidemic while facing restrictions of time and
resources. During this very short period, numerous publications and reports
have appeared in both scientific and non-scientific journals. The reader can
easily see them, for example, in the Washington Post, NY Times, Scientific
American, Science Advances, medRxiv, bioRxiv, ArXiv, and elsewhere.

The story goes back to 1943, when Robert Dorfman published a manuscript where
he introduced the concept of group testing in response to the need to
administer syphilis tests to millions of individuals drafted into the U.S.
Army during World War II (Dorfman, 1943). A nice description of the Dorfman
(1943) procedure is given by Feller (1950): ”A large number, $N$, of people
are subject to a blood test. This can be administered in two ways. (i) Each
person is tested separately. In this case $N$ tests are required. (ii) The
blood samples of $k$ people can be pooled and analyzed together. If the test
is negative, this one test suffices for the $k$ people. If the test is
positive, each of the $k$ persons must be tested separately, and all $k+1$
tests are required for the $k$ people. Assume the probability $p$ that the
test is positive is the same for all and that people are stochastically
independent.”
Procedure $(ii)$ is commonly referred to as the Dorfman (D) two-stage group
testing (GT) procedure.

In general, the above setting assumes a probabilistic model where there are
$N$ individuals to be tested, test outcomes are independent, and each
individual has the same probability $p$ to be infected (Binomial model). In
this article, we will discuss different GT procedures under this model, where
comparisons are done based on the expected number of tests. The fundamental
result by Peter Ungar (Ungar, 1960) shows that if
$p>p_{u}=(3-\sqrt{5})/2\approx 0.38$, then individual testing is the optimal
GT procedure, and if $p<p_{u}$, then it is not optimal. However, it is
important to note that despite 80 years’ worth of research effort, the optimal
procedure is yet unknown for $p<p_{u}$ and a general $N$.

This article deals with nested GT procedures, of which the Dorfman (1943)
procedure is a member. A nested algorithm has the property that if a positive
subset $I$ is identified, the next subset $I_{1}$ that we will test is a
proper subset of $I$–that is, $I_{1}\subset I$. This natural class of GT
procedures was defined by Sobel and Groll (1959) and Sobel (1960). Procedure
$D$ belongs to this class with the restriction that up to two stages are
required.

##  2 Nested GT Procedures: common $p$ case

Recall that we prefer procedure/design $A$ over procedure/design $B$ if
$E_{A}\leq E_{B}$, where $E$ is the corresponding expected number of tests.

###  2.1 Dorfman and modified Dorfman procedures

In a group of size $k\geq 2,$ the total number of tests is $1$ with
probability $q^{k}$ ($q=1-p$) and $k+1$ with probability $1-q^{k}$. Therefore,
the expected number of tests per person in Procedure D is ${\displaystyle
E_{D}\left(k,p\right)=1-q^{k}+\frac{1}{k},\,\text{for}\,\,k\geq 2}$; and
equals 1 otherwise.

Dorfman numerically found the optimum group size $k$ when assuming that a
population is large (infinite) and $p$ is fixed. For example, if $p=0.01$,
then the optimal group size is $11$. Specifically, this means that for testing
$N=999,999$ individuals, we need only $195,571$ tests in expectation. Samuels
(1978) showed that an optimal value of $k$, $k^{*}_{D}(p)$ is a non-increasing
function of $p$, which is $1$ for $p>1-1/3^{1/3}\approx 0.31$ and otherwise is
either $1+[p^{-1/2}]$ or $2+[p^{-1/2}]$, where $[x]$ denotes the integer part
of $x$.

There is a logical inconsistency in Procedure D. It is clear that any
”reasonable” group testing plan should satisfy the following property: ”A test
is not performed if its outcome can be inferred from previous test results”
(Ungar, 1960). Procedure $D$ does not satisfy this property since if the group
is positive and all but the last person are negative, the last person is still
tested. The modified Dorfman procedure, which we define as $D^{\prime}$, would
not test the last individual in that case (Sobel and Groll, 1959). Also,
Procedure $D^{\prime}$ will be preferred over individual testing if $p$ is
below Ungat’s cut-off point (Malinovsky and Albert, 2019). For $k\geq 2,$ the
total number of tests is $1$ with probability $q^{k}$, $k$ with probability
$q^{k-1}(1-q)$, and $k+1$ with probability $1-q^{k-1}$. Therefore, the
expected number of tests per person in a group of size $k$ under Procedure
$D^{\prime}$: ${\displaystyle
E_{{D^{\prime}}}\left(k,p\right)=1-q^{k}+1/k-(1/k)(1-q)q^{k-1}}.$ Pfeifer and
Enis (1978) showed that an optimal value $k^{*}_{D^{\prime}}$ is the smallest
$k$ value that satisfies $E_{D^{\prime}}\left(k,p\right)\leq
E_{D^{\prime}}\left(k-1,p\right)\,\,\,\,\text{and}\,\,\,\,E_{D^{\prime}}\left(k,p\right)<E_{D^{\prime}}\left(k+1,p\right)$.
It was conjectured and empirically verified in Malinovsky and Albert (2019)
that the optimal group size $k^{*}_{D^{\prime}}(p)$ is equal to either
$\displaystyle\lfloor p^{-1/2}\rfloor$ or $\displaystyle\lceil
p^{-1/2}\rceil$.

###  2.2 Sterrett sequential procedure

Sterrett (1957) realized that one can improve the efficiency of the GT
procedure by a sequential modification of Procedure $D^{\prime}$. If in the
first stage of Procedure $D^{\prime}$ a group is positive, then individuals
are tested one-by-one until the first positive individual is identified, or
until all but the last person are negative; in the latter case, the positivity
of the last individual follows from the positivity of the group. Otherwise, if
the first individual identified as positive is not the last in the group, then
the first stage of Procedure $D^{\prime}$ is applied to the remaining
(nonidentified) individuals. This process is repeated until all individuals
are identified. A simple closed-form expression for the expected number of
tests per person was provided by Sobel and Groll (1959): ${\displaystyle
E_{S}\left(k,p\right)=\frac{1}{k}\left[2k-(k-2)q-\frac{1-q^{k+1}}{1-q}\right]}.$
It was conjectured and empirically verified in Malinovsky and Albert (2019)
that for $0<p<p_{U}$ the optimal group size $k^{*}_{D^{\prime}}(p)$ is equal
to $\displaystyle\lfloor\sqrt{2/p}\rfloor$ or
$\displaystyle\lfloor\sqrt{2/p}\rfloor+1$ or
$\displaystyle\lfloor\sqrt{2/p}\rfloor+2$. Using above conjectures one can
verify that ${\displaystyle\lim_{p\downarrow
0}\frac{E_{D}\left(k^{*}_{D},p\right)}{E_{S}\left(k^{*}_{S},p\right)}=\sqrt{2}.}$
Some extensions of the Sterrett (S) procedure were presented in Johnson et al.
(1991).

Finite Versus Infinite Population

A finite population of size $N$ is not necessarily divisible by $k$.
Therefore, for a finite population of size $N$ and a given Procedure
$A\in\left\\{D,D^{\prime},S\right\\}$, we have to solve the following
optimization problem: find the optimal partition
$\displaystyle\left\\{n_{1},\ldots,n_{I}\right\\}$ with $n_{1}+\ldots+n_{I}=N$
for some $I\in\left\\{1,\ldots,N\right\\}$ such that $E_{A}\left(k,\,p\right)$
is minimal. A common method to solve such an optimization problem is dynamic
programming (DP) (Sobel and Groll, 1959). It was conjectured by Lee and Sobel
(1972) for that Procedure $D$, the optimal partition subgroup sizes differ at
most by one unit. Gilstein (1985) proved a similar result for Procedure
$D^{\prime}$, and Malinovsky and Albert (2019) for Procedure $S$.

###  2.3 Hierarchical and nested procedures

Procedures $D,D^{\prime}$, and $S$ fit into a larger class of procedures
discussed below.

An Optimal Hierarchical Procedure

The hierarchical class procedure was introduced by Sobel and Groll (1959) and
defined as follows (see also Hwang et al. (1981)): A procedure is in the
hierarchical class (HC) if two units are only tested together in a group if
they have an identical test history, i.e. if each previous group test contains
either both of them or none of them.

It follows from this definition that a procedure in the HC is similar to the
multistage Dorfman procedure. An optimal hierarchical procedure was obtained
by Sobel and Groll (1959) as a dynamic programming algorithm with
computational cost $O(N^{2})$, which they called Procedure $R_{3}$. This was
recently computationally improved by Zimmerman (2017) (see also Malinovsky
(2019a) for a discussion).

An Optimal Nested Procedure

This class of GT procedures was defined by Sobel and Groll (1959) and Sobel
(1960, 1967) A nested procedure requires that between any two successive tests
$n$ units not yet classified have to be separated into only (at most) two
sets. One set of size $m\geq 0$, called the “defective set,” is known to
contain at least one defective unit if $m\geq 1$ (it is not known which ones
are defective or exactly how many there are). The other set of size $n-m\geq
0$ is called the “binomial set” because we have no knowledge about it other
than the original binomial assumption. Either of these two sets can be empty
in the course of experimentation; both are empty at termination.

The number of potential nested group testing algorithms is astronomical. For
example, if $N=5$, then there are $235,200$ possible algorithms (Moon and
Sobel, 1977). Sobel and Groll (1959) overcame this problem by proposing a DP
algorithm that finds the optimal nested algorithm, which Sobel and Groll
termed “Procedure $R_{1}$.” There was a large research effort to reduce the
$O(N^{3})$ computational complexity of the original proposed algorithm (Sobel,
1960; Kumar and Sobel, 1971; Hwang, 1976a; Yao and Hwang, 1990). Zaman and
Pippenger (2016) provided an asymptotic analysis of the optimal nested
procedure; see also Malinovsky and Albert (2019) for discussion. In addition,
the connection of group testing with noiseless-coding theory was presented in
the group testing literature by Sobel and Groll (1959) and further
investigated in Sobel (1960, 1967). In particular, for $N=2$ the procedures
$D^{\prime},S,R_{3}$, and $R_{1}$ coincide and are the optimal GT procedures.
The optimality follows from the fact that for $N=2$ they are equivalent to the
optimal prefix Huffman code (Huffman, 1952) with the expected length $L(N)$.
In general, for any $N$, $L(N)$ can serve as a theoretical lower bound for the
expected number of tests of an optimal GT procedure; however, the complexity
of calculation of $L(N)$ is $O\left(2^{N}\log_{2}(2^{N})\right)$. Therefore,
even for small $N$, obtaining the exact value of $L(N)$ is impossible. A well-
known noiseless coding theorem provides the information theory bounds for
$L(N)$ as ${\displaystyle H(p)\leq L(N)\leq H(p)+1}$, where ${\displaystyle
H(p)=N\left[p\log_{2}\frac{1}{p}+q\log_{2}\frac{1}{q}\right]}$ is the Shannon
entropy. For a comprehensive discussion, see Katona (1973).

Below, we compare Procedures $D^{\prime},S$, Optimal Hierarchical ($R_{3}$),
and Optimal Nested ($R_{1}$) for different $p$ with respect to the expected
number of tests for $N=100$. For Procedures $D^{\prime}$ and $S$, the optimal
configuration for finite population was found in Gilstein (1985) and in
Malinovsky and Albert (2019), respectively.

Table 1:  The minimal (optimal) expected number of tests per 100 individuals for Procedures $D^{\prime}$, S, Hierarchical ($R_{3}$), and Nested ($R_{1}$) for different $p$.  $p$ | $D^{\prime}$ | $S$ | $R_{3}$ | $R_{1}$ | $H(p)$
---|---|---|---|---|---
0.001 | 6.278 | 4.605 | 1.9554 | 1.766 | 1.141
0.01 | 19.470 | 15.181 | 9.6872 | 8.320 | 8.079
0.05 | 41.807 | 36.018 | 32.0186 | 28.958 | 28.640
0.10 | 57.567 | 52.288 | 50.6752 | 47.375 | 46.900
0.20 | 77.872 | 74.974 | 74.974 | 72.875 | 72.192
0.25 | 84.375 | 83.875 | 83.875 | 82.191 | 81.128
0.30 | 90.500 | 90.500 | 90.500 | 88.889 | 88.129
0.35 | 96.375 | 96.375 | 96.375 | 95.633 | 93.407
0.38 | 99.780 | 99.780 | 99.780 | 99.730 | 95.804

Table 1 shows that for each value of $p$ there is a consistent ranking among
optimal Procedures $D^{\prime},S$, Optimal Hierarchical ($R_{3}$), and Optimal
Nested ($R_{1}$) with respect to the expected total number of tests: Procedure
$R_{1}$ is the best, $R_{3}$ is the second-best, $S$ is the third-best, and
$D^{\prime}$ is the worst. The consistent ranking among Procedures
$D^{\prime},R_{3}$, and $R_{1}$ follows from their definitions; $R_{3}$ is
similar to $D^{\prime}$ but without being limited in maximal number of stages
as $D^{\prime}$, and $R_{1}$ does not have a restriction (as $R_{3}$ has) that
any two units only be tested together in a group if they have an identical
test history. Meanwhile, Procedure $S$ also belongs to the hierarchical class,
but has the restriction that in a positive group, individuals are tested one-
by-one until the first positive individual is identified, or until all
individuals but the last one are determined negative. Consequently, Procedure
$R_{3}$ and therefore $R_{1}$ rank higher than Procedure $S$. To the best of
our knowledge, no theoretical results compare optimal Procedures $D^{\prime}$
and $S$. It is important to note that for some values of $p$ and $N$, ties
among the procedures are possible (case $N=2$ was mentioned early in this
section).

##  3 Nested GT Procedures: heterogeneous $p$

The generalized group testing problem (GGTP), first introduced by Sobel
(1960), consists of $N$ stochastically independent units
$u_{1},u_{2},\ldots,u_{N}$, where unit $u_{i}$ has the probability $p_{i}$
($0<p_{i}<1$) to be defective and the probability $q_{i}=1-p_{i}$ to be non-
defective. We assume that the probabilities $p_{1},p_{2},\ldots,p_{N}$ are
known and that we can decide the order in which the units will be tested. All
units have to be classified as either non-defective or defective by group
testing. Since its introduction, GGTP has seen considerable theoretical
investigation (Lee and Sobel (1972); Nebenzahl and Sobel (1973); Katona
(1973); Hwang (1976a); Yao and Hwang (1988a, b); Kurtz and Sidi (1988); Kealy
et al. (2014); Malinovsky (2019b, 2020); Malinovsky et al. (2020)).

Dorfman and Sterrett Procedures

Ideally, under procedure $A$ ($A\in\left\\{D,D^{\prime},S\right\\}$) we are
interested in finding an optimal partition $\displaystyle\left\\{m_{1},\ldots
m_{I}\right\\}$ with $\displaystyle m_{1}+\ldots+m_{I}=N$ for some
$I\in\left\\{1,\ldots,N\right\\}$ such that the total expected number of tests
is minimal, i.e. ${\displaystyle\left\\{m_{1},\ldots
m_{I}\right\\}=\arg\min_{n_{1},\ldots,n_{J}}E_{A}\left(n_{1},n_{2},\ldots,n_{J}\right)}$
subject to ${\sum_{i=1}^{J}n_{i}=N,\,\,J\in\left\\{1,\ldots,N\right\\}}$,
where ${\displaystyle
E_{A}\left(n_{1},n_{2},\ldots,n_{J}\right)=E_{A}\left(1:n_{1}\right)+\cdots+E_{A}\left(1:n_{J}\right)}$,
and ${\displaystyle E_{A}\left(1:n_{j}\right)}$ is the total expected number
of tests (under procedure $A$) in a group of size $n_{j}$. This task is a hard
computational problem, and moreover impossible to perform because the total
number of possible partitions of a set of size $N$ is the Bell number
$B(N)=\left\lceil\frac{1}{e}\sum_{j=1}^{2N}\frac{j^{N}}{j\,!}\right\rceil$,
which grows exponentially with $N$. For example, $B(13)=27,644,437$. In fact,
the optimal partition is known only for Procedure $D$, due to Hwang (1975,
1981). Hwang proved that under Procedure $D$, an optimal partition is an
ordered partition (i.e. each pair of subsets has the property that the numbers
in one subset are all greater than or equal to every number in the other
subset); he also provided a dynamic programming algorithm for finding an
optimal partition with computational effort $O(N^{2})$. However, the ordered
partition is not optimal for Procedures $D^{\prime}$ and $S$ (Malinovsky,
2019b), and finding an optimal partition for these procedures is a hard
computational problem. That said, one can evaluate the optimal $D^{\prime}$
and $S$ algorithm under a predetermined order of p’s. In Table 2, we compare
Procedures $D,D^{\prime}$ and $S$ for ordered p’s, where the method for
Procedure $D$ was developed by Hwang (1975) and those for Procedures
$D^{\prime}$ and $S$ by (Malinovsky, 2019b).

Hierarchical and Nested Procedures

For the fixed predetermined order of $p_{1},p_{2},\ldots,p_{N}$ an optimal
nested and hierarchical procedures with respect to the expected total number
of tests were developed as DP algorithms in Kurtz and Sidi (1988) and in
Malinovsky et al. (2020), respectively.

Numerical comparisons

We generated the vector $\displaystyle p_{1},p_{2},\ldots,p_{100}$ from a Beta
distribution with parameters $\displaystyle\alpha=1,\beta=(1-p)/p$ such that
the expectation equals $p$. We repeat this process $M=1000$ times for each
value of $p$. Each time an optimal ordered partition with the corresponding
expected number of tests was found for Procedures $D$, $D^{\prime}$, and $S$,
the hierarchical (HL) and nested (ON) procedures were obtained using DP
algorithm (based on the previously mentioned references). Also, in the GGTP,
Shannon entropy
$\sum_{i=1}^{N}\left\\{p_{i}\log_{2}\frac{1}{p_{i}}+(1-p_{i})\log_{2}\frac{1}{1-p_{i}}\right\\}$
can serve as the information lower bound for the expected number of tests of
an optimal group testing procedure. The averages of 1000 repetitions are
presented in Table 2 below.

Table 2: Comparison of Procedures $D^{\prime}$, $S$, Hierarchical (HL), and Nested (ON). p | $N=100$ |
---|---|---
| $D^{{}^{\prime}}$ | $S$ | $HL$ | $ON$ | Shannon Entropy |
0.001 | 5.738 | 3.745 | 1.867 | 1.697 | 1.081 |
0.01 | 17.345 | 13.121 | 8.720 | 7.730 | 7.474 |
0.05 | 37.095 | 31.801 | 28.212 | 25.797 | 25.653 |
0.10 | 50.758 | 46.105 | 43.606 | 41.192 | 40.855 |
0.20 | 67.536 | 64.33 | 62.69 | 61.030 | 60.11 |
0.30 | 77.598 | 75.358 | 74.382 | 72.611 | 70.303 |

Table 2 shows the same ranking pattern among procedures as was observed in
Table 1 for the homogeneous $p$ case. This pattern can be explained along the
lines of the previous discussion concerning homogeneous $p$.

##  4 Related Issues

Unknown $p$
In many practical situations, the exact value $p$ of the probability of
disease prevalence is unknown or else only some limited information is
available, for example a range. Since all of the above-presented procedures
require knowledge of $p$, there is a need to evaluate $p$ during the process
of testing. For a nested algorithm $R1$, Sobel and Groll (1966) proposed a
Bayesian approach that uses upcoming information during testing to evaluate
and revaluate $p$. A minimax approach for Procedure $D$ was introduced by
Malinovsky and Albert (2015) and for Procedures $D^{\prime}$ and $S$ in
Malinovsky and Albert (2019).

Errors in the Testing
In many settings, particularly in biology and medicine, tests may be subject
to measurement error or misclassification. This issue occurs in individual
testing but may be enhanced in group testing. In particular, for many
applications, the sensitivity of a grouped test may decrease with group size
(this is often referred to as dilution). Graff and Roeloffs (1972) and Hwang
(1976b) recognized early that when tests are misclassified, the objective
function should not be the expected number of tests. Graff and Roeloffs (1972)
and Burns and Mauro (1987) proposed a modification of the Dorfman procedure
and searched for a design that minimized total cost as a linear function of
the expected number of tests, weighted the expected number of good items
misclassified as defective, and weighted the expected number of defective
items misclassified as good. Hwang (1976b) studied a group testing model with
the presence of a dilution effect, where a group containing a few defective
items may be misidentified as one containing no such items, especially when
the size of the group is large. He calculated the expected cost under the
Dorfman procedure in the presence of the dilution effect and derived the
optimal group sizes to minimize this cost. Malinovsky et al. (2016)
characterized the optimal design in the Dorfman procedure in the presence of
misclassification by maximizing the ratio between the expected number of
correct classifications and the expected number of tests. Haber et al. (2021)
proposed to minimize the expected number of tests while controlling overall
misclassification rates. In general, since it is expected that
misclassification may be related to group size, one has to be very cautious
about proposing Dorfman designs with large group sizes. Alternative designs
where groups are re-tested in different ways have been explored (Litvak et
al., 1994, 2020).

Incomplete identification
Consider a very large (infinite) population of items, where each item,
independent from the others, is either defective with probability $p$ or non-
defective with probability $1-p$. The goal is to identify a certain number of
non-defective items as quickly as possible. To the best of our knowledge, the
incomplete identification problem was introduced by Bar-Lev et al. (1990). For
recent developments and references, see Malinovsky (2018).

## References

  * Bar-Lev et al. (1990) Bar-Lev, S. K., Boneh, A., Perry, D. (1990).  Incomplete identification models for group-testable items.  _N_ av. Res. Logist. 37, 647–659.
  * Burns and Mauro (1987) Burns, K. C., Mauro, C. A. (1987).  Group testing with test error as a function of concentration.  _C_ ommunications in Statistics - Theory and Methods 16, 2821–2837.
  * Dorfman (1943) Dorfman, R. (1943).  The detection of defective members of large populations.  _T_ he Annals of Mathematical Statistics 14, 436–440.
  * Feller (1950) Feller, W. (1950).  An introduction to probability theory and its application. New York: John Wiley & Sons.
  * Gilstein (1985) Gilstein, C. Z. (1985).  Optimal partitions of finite populations for Dorfman-type group testing.  J. Stat. Plan. Inf. 12, 385–394.
  * Graff and Roeloffs (1972) Graff, L. E., Roeloffs, R.(1972).  Group testing in the presence of test error; an extension of the Dorfman Procedure.  Technometrics 14 Part B, 113–122.
  * Haber et al. (2021) Haber, G., Malinovsky Y., and Albert, P. S.(2021).  Is group testing ready for prime-time in disease identification?  Preprint arXiv: https://arxiv.org/abs/2004.04837 .
  * Huffman (1952) Huffman, D. A. (1952).  A Method for the Construction of Minimum-Redundancy Codes.  _P_ roceedings of the I.R.E. 40, 1098–1101.
  * Hwang (1975) Hwang, F. K. (1975).  A generalized binomial group testing problem.  _J_. Amer. Statist. Assoc. 70, 923–926.
  * Hwang (1976a) Hwang, F. K. (1976a).  An optimal nested procedure in binomial group testing.  Biometrics 32, 939–943.
  * Hwang (1976b) Hwang, F. K. (1976b).  Group testing with a dilution effect.  Biometrika 63, 671–680.
  * Hwang (1981) Hwang, F. K. (1981).  Optimal Partitions.  _J_. Optim. Theory Appl. 34, 1–10.
  * Hwang et al. (1981) Hwang, F. K., Pfeifer, C. J., and Enis, P. (1981).  An Optimal Hierarchical Procedure for a Modified Binomial Group-Testing Problem.  _J_. Amer. Statist. Assoc. 76, 947–949.
  * Johnson et al. (1991) Johnson, N. L., Kotz, S., Wu, X. Z. (1991).  Inspection errors for attributes in quality control.  Monographs on Statistics and Applied Probability, 44. Chapman $\&$ Hall, London.
  * Katona (1973) Katona, G. O. H. (1973).  Combinatorial search problems.  J.N. Srivastava et al., A Survey of combinatorial Theory, 285–308.
  * Kealy et al. (2014) Kealy, T., Johnson, O., and Piechocki, R. (2014).  The capacity of non-identical adaptive group testing.  _P_ roc. 52nd Annu. Allerton Conf. Commun. Control Comput., 101–108.
  * Kurtz and Sidi (1988) Kurtz, D., and Sidi, M. (1988).  Multiple access algorithms via group testing for heterogeneous population of users.  _I_ EEE Trans. Commun. 36, 1316–1323.
  * Kumar and Sobel (1971) Kumar, S., and Sobel, M. (1971).  Finding a single defective in binomial group-testing.  J. Amer. Statist. Assoc. 66, 824–828.
  * Lee and Sobel (1972) Lee, J.K., and Sobel, M. (1972).  Dorfman and $R_{1}$-type procedures for a generalized group testing problem.  Mathematical Biosciences 15, 317–340.
  * Litvak et al. (2020) Litvak, E., Dentzer, S., Pagano, M. (2020).  The Right Kind of Pooled Testing for the Novel Coronavirus: First, Do No Harm.  American Journal of Public Health 110, 1772–1773.
  * Litvak et al. (1994) Litvak, E., Tu, X. M., Pagano, M. (1994).  Screening for the presence of a disease by pooling sera samples.  J. Am. Stat. Assoc. 89, 424–434.
  * Malinovsky (2018) Malinovsky, Y. (2018).  On optimal policy in the group testing with incomplete identification.  _S_ tatist. Probab. Lett. 140, 44–47.
  * Malinovsky (2019a) Malinovsky, Y. (2019a).  End Notes.  _M_ ath. Mag. 92, 398.
  * Malinovsky (2019b) Malinovsky, Y. (2019b).  Sterrett procedure for the generalized group testing problem.  _M_ ethodology and Computing in Applied Probability. 21, 829–840.
  * Malinovsky (2020) Malinovsky, Y. (2020).  Conjectures on Optimal Nested Generalized Group Testing Algorithm.  _A_ pplied Stochastic Models in Business and Industry. 36, 1029–1036.
  * Malinovsky and Albert (2015) Malinovsky, Y., Albert, P. S. (2015). A note on the minimax solution for the two-stage group testing problem. The American Statistician 69, 45–52.
  * Malinovsky and Albert (2019) Malinovsky, Y., Albert, P. S. (2019). Revisiting nested group testing procedures: new results, comparisons, and robustness. The American Statistician 73, 117–125.
  * Malinovsky et al. (2016) Malinovsky, Y., Albert, P. S., Roy, A. (2016). Reader reaction: A note on the evaluation of group testing algorithms in the presence of misclassification. Biometrics 72, 299–302.
  * Malinovsky et al. (2020) Malinovsky, Y., Haber, G., Albert, P. S. (2020). An optimal design for hierarchical generalized group testing. J. R. Stat. Soc. Ser. C. Appl. Stat.  69, 607–621.
  * Moon and Sobel (1977) Moon, J. W., Sobel, M. (1977). Enumerating a class of nested group testing procedures. Journal of combinatorial theory, series B 23, 184–188.
  * Nebenzahl and Sobel (1973) Nebenzahl, E., and Sobel, M. (1973).  Finite and infinite models for generalized group-testing with unequal probabilities of success for each item.  in T. Cacoullos, ed., Discriminant Analysis and Aplications, New York: Academic Press Inc., 239–284.
  * Pfeifer and Enis (1978) Pfeifer, C. G., Enis, P. (1978).  Dorfman-type group testing for a modified binomial model.  J. Amer. Statist. Assoc. 73, 588–592.
  * Samuels (1978) Samuels, S. M. (1978).  The exact solution to the two-stage group-testing problem.  Technometrics 20, 497–500.
  * Sobel (1960) Sobel, M. (1960).  Group testing to classify efficiently all defectives in a binomial sample.  Information and Decision Processes (R. E. Machol, ed.; McGraw-Hill, New York), pp. 127-161.
  * Sobel (1967) Sobel, M. (1967).  Optimal group testing.  Proc. Colloq. on Information Theory, Bolyai Math. Society, Debrecen, Hungary.
  * Sobel and Groll (1959) Sobel, M., Groll, P. A. (1959).  Group testing to eliminate efficiently all defectives in a binomial sample.  Bell System Tech. J. 38, 1179–1252.
  * Sobel and Groll (1966) Sobel, M., Groll, P. A. (1966).  Binomial group-testing with an unknown proportion of defectives.  Technometrics  8, 631–656.
  * Sterrett (1957) Sterrett, A. (1957).  On the detection of defective members of large populations.  _T_ he Annals of Mathematical Statistics 28, 1033–1036.
  * Ungar (1960) Ungar, P. (1960). Cutoff points in group testing. Comm. Pure Appl. Math. 13, 49–54.
  * Yao and Hwang (1988a) Yao, Y. C., Hwang, F. K. (1988a).  A fundamental monotonicity in group testing.  _S_ IAM J. Disc. Math. 1, 256–259.
  * Yao and Hwang (1988b) Yao, Y. C., Hwang, F. K. (1988b).  Individual testing of independent items in optimum group testing.  _P_ robab. Eng. Inform. Sci. 2, 23–29.
  * Yao and Hwang (1990) Yao, Y. C., Hwang, F. K. (1990).  On optimal nested group testing algorithms.  J. Stat. Plan. Inf. 24, 167–175.
  * Zaman and Pippenger (2016) Zaman, N., and Pippenger, N. (2016).  Asymptotic analysis of optimal nested group-testing procedures.  Prob. Eng. Inform. Sci. 30, 547–-552.
  * Zimmerman (2017) Zimmerman, S. (2017).  Detecting deficiencies: an optimal group testing algorithm.  _M_ ath. Mag. 90, 167–178.