# Upper bounds on the Rate of Uniformly-Random Codes for the Deletion Channel

Berivan Isik, Francisco Pernice, Tsachy Weissman

###### Abstract

We consider the maximum coding rate achievable by uniformly-random codes for
the deletion channel. We prove an upper bound that’s within 0.1 of the best
known lower bounds for all values of the deletion probability $d,$ and much
closer for small and large $d.$ We give simulation results which suggest that
our upper bound is within 0.05 of the exact value for all $d$, and within
$0.01$ for $d>0.75$. Despite our upper bounds, based on simulations, we
conjecture that a positive rate is achievable with uniformly-random codes for
all deletion probabilities less than 1. Our results imply impossibility
results for the (equivalent) problem of compression of i.i.d. sources
correlated via the deletion channel, a relevant model for DNA storage.

##  1 Introduction

The _binary deletion channel_ takes as input a string of bits, and outputs a
random subsequence, chosen by deleting each bit of the input independently
with a fixed probability $d.$ The deletion channel is an example of a channel
with _memory_ : the action of the channel on different input bits cannot be
decoupled, due to the asynchrony between input and output that is introduced.
Memory vastly complicates the analysis of the fundamental limits of
communication through the deletion channel, i.e., its _capacity_. Indeed,
calculating the capacity of this channel as a closed-form expression has been
a notorious open problem in information theory for more than fifty years. For
channels without memory, the situation is much better understood. A single-
letter variational formula for the capacity has been known since Shannon
[Sha48], and for _symmetric_ memoryless channels, the capacity is explicitly
given by the mutual information between a uniformly-random (single-letter)
input and the corresponding output. This is equivalent to the statement that,
for a symmetric memoryless channel, a uniformly-random code achieves capacity
with high probability.

Given the success in understanding the capacity of memoryless channels, early
research on the deletion channel focused on extending Shannon’s techniques to
settings with memory. A major stride in this direction was made by Dobrushin
[Dob67], who showed that the capacity of the deletion channel, as well as a
large class of other channels with memory, is given by the following natural
extension of Shannon’s variational formula:

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\sup_{X^{n}}I(X^{n};Y^{n}),$ (1)

where $I(\cdot\,;\cdot)$ is the mutual information, the supremum is over the
distributions of the random variable $X^{n}$ supported on $\\{0,1\\}^{n}$, and
$Y^{n}$ is the output of the binary deletion channel on input $X^{n}$.111The
dependence on $d$ is suppressed. Unfortunately, the resulting variational
problem is now infinite-dimensional, and a daunting task to compute. And
indeed, appealing though it is, Dobrushin’s theorem has proved of little help
in obtaining an explicit handle on the capacity of the deletion channel.222A
notable exception is the work of Kirsch and Drinea [KD10], who improved on the
lower bound in [DM07] via Dobrushin’s theorem and purely information-theoretic
arguments.

Faced with the difficulty of the variational problem involved, it is tempting
to attempt “plugging in” the uniform distribution as the law of $X^{n},$ given
the success of this strategy for memoryless symmetric channels. This
corresponds to evaluating the performance of uniformly-random codes on the
deletion channel. Diggavi and Grossglauser [DG01] attempted this strategy, and
showed that uniformly-random codes can achieve a rate of at least $1-h(d),$
for $d\leq 1/2,$ where $h:[0,1]\to[0,1]$ is the binary entropy function, hence
re-proving a lower bound on the deletion channel capacity originally due to
Gallager [Gal61] and Levenshtein [Lev65]. However, in the same paper, Diggavi
and Grossglauser also obtained a better lower bound by generating a code with
a non-uniform input distribution. This was later improved upon by a series of
papers [DM07, MD06, KD10, Dal11, RD13], all of whom made use of non-uniform
input processes. In fact, we now know that a uniformly-random code _cannot_
attain the capacity of the deletion channel, e.g., by the results of Drmota,
Szpankowski and Viswanatha [DSV12], who showed that the rate achievable by
uniformly-random codes is $O((1-d)^{4/3}\log\frac{1}{1-d})$ as $d\to 1,$ while
for optimal codes it’s known to be $\Theta(1-d)$ [MD06].

Nevertheless, in this paper we advocate the view that the rate attainable by
uniformly-random codes for the deletion channel is well worth studying in its
own right. We offer three justifications, in increasing order of perceived
importance by the authors. First, as was pointed out by Mitzenmacher [Mit09],
and is easy to see, uniformly-random codes have a natural maximum a posteriori
(MAP) decoding rule: given a received string $Y,$ return the codeword $c$ for
which $Y$ appears as a subsequence the most times. As we illustrate in this
paper (and as was implicit in [HOS16]), this fact can be cast in information-
theoretic language, leading to a more concrete characterization of the maximum
rate achievable by uniformly-random codes than the limit of the mutual
information. Second, as is demonstrated by combining the results of this
manuscript with the lower bounds in [DG01, RD13, HOS16], by restricting
attention to uniformly-random codes, one can get much tighter lower and upper
bounds on the maximum achievable rate. This suggests that a characterization
of the maximum rate achievable by uniformly-random codes may be a fruitful
milestone in the long road towards understanding the deletion channel
capacity. Finally, as we describe in Section 1.1, the determination of the
maximum rate achievable by uniformly-random codes has a _direct_ application,
in addition to the indirect application of advancing our understanding of the
deletion channel capacity. Namely, after a simple transformation, the maximum
rate achievable by uniformly-random codes is equivalent to the minimum rate of
compression of a uniform source given side information that is correlated to
it via the deletion channel. This connection, which was explored in [MRT11,
MRT12], offers a natural generalization of the classical Slepian-Wolf theory
of distributed compression of sources with memoryless correlations, to the
setting of deletion-based correlations. As such, it has immediate relevance
for distributed DNA storage.

###  1.1 Slepian-Wolf Compression with Deletion Correlations

In this section, we give a brief self-contained overview of the classical
Slepian-Wolf theory of distributed compression of correlated sources [SW73].
For a more comprehensive introduction to the Slepian-Wolf theory, including
proofs, we refer the reader to [CT06, Chapter 15.4].

Shannon’s theory, among other applications, gives a fundamental limit on the
minimum achievable rate of compression of a source
$\\{X_{i}\\}_{i=1}^{\infty}:$ for an i.i.d. source, the simplest case, it is
given by the entropy $H(X_{1}).$ It’s natural to ask how this fundamental
limit may be extended to the case of multiple sources. It turns out that much
about the question is already captured by the case of jointly i.i.d. sources
$X:=\\{X_{i}\\}_{i=1}^{\infty}$ and $Y:=\\{Y_{i}\\}_{i=1}^{\infty}$, where
each pair $(X_{i},Y_{i})$ is sampled independently from a joint distribution
$p(x,y)$, or equivalently, where $X$ is i.i.d., and $Y$ is the output of a
memoryless channel on input $X.$ We wish to determine, for any given pair
$(R_{X},R_{Y})\in[0,1]^{2}$, whether it’s possible to compress $X$ at rate
$R_{X}$ and $Y$ at rate $R_{Y},$ i.e., to determine the _achievability region_
in the unit square. Slepian and Wolf showed that the achievability region is
given by

$\\{(R_{X},R_{Y}):R_{X}+R_{Y}\geq H(X_{1},Y_{1})\\}.$

The question becomes even more interesting when one imposes the further
restriction that the individual sources $X$ and $Y$ should be encoded
_independently_ , in a distributed fashion, such that the encoder of $X$
doesn’t have access to $Y$ and the encoder of $Y$ doesn’t have access to $X,$
and then decoded jointly. This is a model, for instance, of a data server with
multiple nodes, where communication between nodes is costly and hence each
node would like to perform their compression task independently, while taking
advantage of the correlations between nodes. Slepian and Wolf’s highly
unexpected insight was that, despite the distributed nature of the encoding,
the achievability region is

$\\{(R_{X},R_{Y}):R_{X}\geq H(X_{1}|Y_{1}),R_{Y}\geq
H(Y_{1}|X_{1}),R_{X}+R_{Y}\geq H(X_{1},Y_{1})\\}.$

Given these results, it is of interest to explicitly compute the achievability
region for natural choices of sources and correlations. A moment of thought
reveals that the problem reduces to calculating $H(X_{1}),H(Y_{1})$,
$H(X_{1}|Y_{1})$, and $H(Y_{1}|X_{1})$; the achievability region, in the
distributed case, is then given by the convex hull of the points

$\begin{cases}(H(X_{1}|Y_{1}),H(Y_{1})),\\\ (H(X_{1}),H(Y_{1}|X_{1})),\\\
(H(X_{1}|Y_{1}),1),\\\ (1,H(Y_{1}|X_{1})),\\\ (1,1).\end{cases}$

Hence, for sources $X$ and $Y$ with uniform marginals and memoryless
correlations, the problem is as easy and as hard as the determination of the
maximum rate achievable by uniform codes over the channels with transition
probabilities $p(x|y)$ and $p(y|x)$.

Given the subject of this paper, we’d like to extend this from the
correlations induced by memoryless channels to those induced by the deletion
channel. Ma, Ramchandran and Tse [MRT11] showed that the Slepian-Wolf results
extend almost verbatim (in the “corner point” case where one wants to compress
$X$ with $Y$ as side information) to the case where $X$ is uniform and $Y$ is
the output of the deletion channel on input $X.$ Their proof also easily
extends to the whole achievability region, e.g., by the information-spectrum
version of the Slepian-Wolf theorem [MK95], [Kog+13, Section 7.2]. One simply
has to replace all entropies $H(X_{1}),H(X_{1}|Y_{1}),$ etc. above by the
corresponding entropy rates

$H(X):=\lim_{n\to\infty}\frac{1}{n}H(X_{1}^{n}),\qquad
H(X|Y):=\lim_{n\to\infty}\frac{1}{n}H(X_{1}^{n}|Y_{1}^{n}),\qquad\text{etc.}$

Hence, in the setting of distributed compression of uniform sources correlated
via deletions, calculating the achievability region amounts to computing
$H(X|Y)$ and $H(Y|X)$333This suffices, since for $X$ uniform and $Y$ the
corresponding output through the deletion channel, it’s trivial that $Y$ is
also uniform and hence $H(X)=H(Y)=1.$ Once again, this is easily seen to be
equivalent to computing

$\lim_{n\to\infty}\frac{1}{n}I(X^{n};Y^{n}(X^{n}))=1-\lim_{n\to\infty}\frac{1}{n}H(X^{n}|Y^{n}(X^{n}))=1-d-\lim_{n\to\infty}\frac{1}{n}H(Y^{n}(X^{n})|X^{n}),$

where $X$ is uniform and now $Y^{n}(X^{n})$ is the output of the deletion
channel on input $X^{n},$ and _not_ the first $n$ coordinates of the process
$Y$ (hence the entropy rate of $Y^{n}(X^{n})$ is $1-d$ instead of 1). Namely,
calculating the minimum rate of Slepian-Wolf coding for uniform sources and
deletion correlations is equivalent to evaluating the performance of
uniformly-random codes through the deletion channel.

###  1.2 Our Results

Our main results are efficiently-computable upper bounds on the maximum rate
achievable through the deletion channel by uniformly-random codes. By the
discussion in Subsection 1.1, our results imply impossibility results for the
distributed compression of deletion-correlated sources. Unlike many of the
known lower and upper bounds related to the deletion channel, which often rely
on coding-theoretic arguments like side information or specific decoding
strategies, our approach is almost entirely based on tools from probability
theory.

We now state our results, and then we plot the resulting bounds at the end of
this subsection.

######  Theorem 1.1.

Let $C_{\text{unif}}:[0,1]\to[0,1]$ denote the maximum rate achievable through
the deletion channel by uniformly-random codes. For each $n\in\mathbb{N}$ and
$d\in[0,1],$ we have

$\displaystyle C_{\text{unif}}(d)\leq 1-d-h(d)+$
$\displaystyle\frac{1}{2n}\log(8\pi
e\max\\{d(1-d)n,1/6\\})+\sum_{u=0}^{n}\binom{n}{u}d^{u}(1-d)^{n-u}\Bigg{(}\frac{1}{n}\log\Pi_{n}^{u}[u]$
$\displaystyle+h(u/n)+\frac{1}{2n}\log(\max\\{2\pi u(n-u)/n,1\\})+\frac{\log
e}{6n\max\\{\min\\{u,n-u\\},1\\}}\Bigg{)}.$

where $h$ is the binary entropy function, and the function
$u\mapsto\Pi_{n}^{u}[u]$ can be computed in time $O(n^{3})$ and space
$O(n^{2}).$ In particular, our upper bound can be evaluated in time $O(n^{4})$
and space $O(n^{2}).$

We note that the explicit algorithm to compute $\Pi_{n}^{u}[u]$ is given in
Theorem 3.8. As a second result, we improve upon the runtime of Theorem 1.1,
at the cost of worse error terms.

######  Theorem 1.2.

For all $d\in(0,1),$ $n\in\mathbb{N},$ we have

$\displaystyle C_{\text{unif}}(d)$ $\displaystyle\leq
1-d+\inf_{\delta}\Bigg{[}\frac{1}{n}\log\Pi_{n}^{(d-\delta)n}[(d-\delta)n]+\delta+2^{-nD(d-\delta||d)}+\frac{1}{n}\log(\max\\{2\pi(d-\delta)(1-d+\delta)n,1\\})$
$\displaystyle\qquad\qquad\qquad+\frac{1}{n}\log(8\pi
e\max\\{d(1-d)n,1/6\\})+\frac{\log
e}{3n^{2}\min\\{\max\\{d-\delta,1-d+\delta\\},1\\}}\Bigg{]},$

where $u\mapsto\Pi_{n}^{u}[u]$ is the same function as in Theorem 1.1, and
$D(\cdot||\cdot):[0,1]^{2}\to\mathbb{R}_{+}$ is the (base 2) KL-divergence for
two Bernoulli distributions. The infimum is over the $\delta>0$ such that
$(d-\delta,d+\delta)\subseteq[0,1]$ and $\delta n\in\mathbb{N}.$ In
particular, this upper bound can be computed in time $O(n^{3})$ and space
$O(n^{2})$ by choosing a constant-sized grid to take the infimum over.

The following corollary, which immediately follows from Theorem 1.2,
simplifies the above expression at a small loss in the error terms.

######  Corollary 1.3.

For all $d\in(0,1)$, $\delta>0,n\in\mathbb{N}$ such that
$(d-\delta,d+\delta)\subseteq[0,1],\delta n\in\mathbb{N},$ and
$n\geq\min\\{d-\delta,1-d+\delta\\}^{-1},$ we have

$C_{\text{unif}}(d)\leq
1-d+\frac{1}{n}\log\Pi_{n}^{(d-\delta)n}[(d-\delta)n]+\delta+2^{-nD(d-\delta||d)}+\frac{1}{n}\log(\pi^{2}e^{4/3}n).$

Although Theorem 1.2 is asymptotically more efficient than Theorem 1.1, our
numerical calculations, all of which ran within a few hours on a personal
computer, were not large enough for this difference to be noticed. Hence our
best numerical upper bounds, plotted below, are given by Theorem 1.1. In
addition to our upper bounds and the lower bounds of [DG01, RD13, HOS16], we
also plot simulation-based upper and lower bounds on the exact value of
$C_{\text{unif}}$ for all deletion probabilities. These simulation results
suggest that our upper bounds are within 0.05 of the true value of
$C_{\text{unif}}$ for all values of $d.$ For a discussion on how accurate
these simulation-based bounds can be taken to be, including the exact method
and parameters with which they were calculated, we refer the reader to Section
4, which can be read immediately after Section 2. Finally, we mention that,
although our upper bound comes very close to zero for $d$ large, we conjecture
that $C_{\text{unif}}(d)$ is positive for all $d<1$ (see Section 5).

Figure 1: The blue curve is our upper bound on $C_{\text{unif}}(d)$ from
Theorem 1.1 for $n=1,000.$ The orange curve is the maximum, for each $d,$ of
the lower bounds in [DG01, RD13, HOS16]. The green and red curves, which
mostly overlap in the figure, are simulation-based (non-proven) upper and
lower bounds on $C_{\text{unif}}$, respectively.

###  1.3 More Prior Work

Here we review previously-known explicit bounds on the maximum rate achievable
with uniformly-random codes for the deletion channel.

##### Extremal Regimes.

Kanoria and Montanari [KM10] and Kalai, Mitzenmacher and Sudan [KMS10] showed
that the capacity of the deletion channel is $1-(1-o(1))h(d)$ as $d\to 0,$ and
this bound is attained by uniformly-random codes. Hence we also have
$C_{\text{unif}}(d)=1-(1-o(1))h(d)$ as $d\to 0.$ In the large-$d$ regime, as
we mentioned above, Drmota, Szpankowski and Viswanatha [DSV12] showed that
$C_{\text{unif}}(d)=O((1-d)^{4/3}\log\frac{1}{1-d})$ as $d\to 1.$

##### Non-Extremal Regime.

As we mentioned above, Diggavi and Grossglauser [DG01], Rahmati and Duman
[RD13] and Han, Ordentlich and Shayevitz [HOS16] gave lower bounds on
$C_{\text{unif}}$; the best of these bounds, for each $d$, is plotted in
Figure 1. Han, Ordentlich and Shayevitz [HOS16] and Drmota, Szpankowski and
Viswanatha [DSV12] also gave upper bounds on $C_{\text{unif}}$; we include
Figure 3 from [HOS16] below, which plots these bounds. As far as we know, the
upper bound of [HOS16] is the best known proved specifically for
$C_{\text{unif}}$, instead of the deletion channel capacity. However, it only
beats the best known upper bounds on the deletion channel capacity [DMP07,
FD10, RD15, Che19], which are of course automatically upper bounds on
$C_{\text{unif}}$, for $d$ greater than approximately $0.65.$ By comparison,
our bound from Figure 1 beats the best known upper bounds on the deletion
channel capacity, as well as the upper bounds on $C_{\text{unif}}$ of [DSV12,
HOS16], for all $d\in(0,1).$

Figure 2: ([HOS16, Figure 3]). The upper bounds on $C_{\text{unif}}$ of
[HOS16] (labelled “New Upper Bound”) and [DSV12] (labelled “Upper bound from
(50)”).

###  1.4 Organization

We organize the rest of the paper as follows. In Section 2, we review
background material and derive some simple results that will be crucial for
our main proofs. In Section 3, we prove our main results: in Subsection 3.1,
we carry out the main calculation at the heart of our proofs, which we apply
in Subsection 3.2 to obtain a warmup upper bound. Then in Subsection 3.3 we
improve upon this to obtain theorems 1.1 and 1.2. In Section 4, we discuss our
simulation results. Finally, in Section 5, these simulation results lead us to
some questions and conjectures, with which we hope to motivate further work.

##  2 Preliminaries

In this section, we establish some basic results that will be needed in
Section 3 for our proof of the upper bounds on the maximum rate achievable by
uniformly-random codes through the deletion channel. In Subsection 2.1 we fix
the notation for the rest of the paper. In Subsection 2.2, we give a simple
proof of a characterization of the maximum rate due to Ma, Ramchandran and Tse
[MRT11]. Along the way, we introduce important quantities that will play a
major role throughout the paper. We then point out a simple observation (which
was already implicit in [HOS16]) that leads to our approach for the rest of
the paper. Finally in Section 2.3, following the proof of similar results in
[Dal11, FD10, KM10], we bound the convergence rate of the main relevant
quantity (to be introduced below), which will be crucial to us in Section 3.

###  2.1 Notation

The function $C_{\text{unif}}:[0,1]\to[0,1]$ denotes the maximum rate
achievable by uniformly-random codes for the deletion channel, hereafter also
referred to as _the maximum rate_ for brevity. For $x\in\\{0,1\\}^{n},$ we let
$x_{i}^{j}\in\\{0,1\\}^{j-i+1}$ denote the substring of $x$ starting at index
$i$ and ending at $j,$ inclusive; unless otherwise specified, we let
$x_{i}:=x_{i}^{i}$ and $x^{i}:=x_{1}^{i}.$ For $x\in\\{0,1\\}^{n},$ we let
$|x|=n$ denote the string length and $w(x)$ the Hamming weight. For
$x\in\\{0,1\\}^{n},$ $\operatorname{\mathrm{BDC}}_{d}(x)$ denotes the output
of the deletion channel with deletion probability $d$ on input $x.$ As we
sometimes explicitly point out, we will often use the notation $X$ to refer to
a uniformly-distributed random variable in the support $\\{0,1\\}^{n}$, and
$Y=\operatorname{\mathrm{BDC}}_{d}(X)$. This suppression of the blocklength
$n$ in the notation leads to slightly confusing expressions like
$\lim_{n}\frac{1}{n}H(X|Y)$, but it will simplify notation immensely later
when we use the sub- and superscripts for parameters other than $n.$

For a deletion pattern $D\in\\{0,1\\}^{n}$ and an input $x\in\\{0,1\\}^{n}$,
we use the notation $D(x)$ to refer to the output that’s produced by applying
deletion pattern $D$ to input $x,$ namely, by deleting the $i$th bit of $x$ if
and only if $D_{i}=1.$ Hence with $X\sim Unif\\{0,1\\}^{n}$ and $D\sim
Ber(d)^{n}$ (the $n$-fold product of the Bernoulli measure), we have
$Y=\operatorname{\mathrm{BDC}}_{d}(X)=D(X).$ We also use the notation
$\operatorname{supp}(D)\subseteq[n]$ to refer to the set of indices $i\in[n]$
such that $D_{i}=1.$ For a set $A\subseteq[n],$ we denote by
$X_{A}\in\\{0,1\\}^{|A|}$ the subsequence of $X$ obtained by choosing the
indices in $A$ from $X.$ Hence we have e.g.
$D(X)=X_{\operatorname{supp}(D)^{c}}$, where $A^{c}:=[n]\setminus A$ for
$A\subseteq[n]$.

All logs (hence entropies, etc.) in this paper are in base two.

###  2.2 Initial Observations

Ma, Ramchandran and Tse [MRT11] observed that

$\displaystyle\lim_{n\to\infty}\frac{1}{n}H(X|Y)=d+h(d)-\lim_{n\to\infty}\frac{1}{n}H(D|X,Y),$
(2)

where $h$ is the binary entropy and $D\in\\{0,1\\}^{n}$ is the deletion
pattern that yielded $Y$ from $X$. This of course immediately implies, by
Dobrushin’s expression (1) for $C_{\text{unif}}$, that

$C_{\text{unif}}(d)=1-d-h(d)+\lim_{n\to\infty}\frac{1}{n}H(D|X,Y).$

Since (2) is the starting point of our work, and the proof in [MRT11] is more
general than what we need, here we give a very simple self-contained proof.
Along the way, we obtain explicit rates, which will be useful later.

We have

$\displaystyle H(X|Y)$ $\displaystyle=H(X,D|D(X))-H(D|X,Y)$
$\displaystyle=H(X_{\operatorname{supp}(D)},D)-H(D|X,Y)$
$\displaystyle=H(X_{\operatorname{supp}(D)})+H(D|w(D))-H(D|X,Y)$
$\displaystyle=H(X_{\operatorname{supp}(D)})+\mathbb{E}\left[\log\binom{n}{w(D)}\right]-H(D|X,Y),$

so to prove (2), it suffices to show that, as $n\to\infty,$ we have ($a$) that
$\frac{1}{n}H(X_{\operatorname{supp}(D)})\to d$, and ($b$) that
$\frac{1}{n}\mathbb{E}[\log\binom{n}{w(D)}]\to h(d)$. For claim $(a)$, let
$L:=|X_{\operatorname{supp}(D)}|=n-|Y|\sim Binom(n,d).$ We have

$\displaystyle dn$ $\displaystyle=\mathbb{E}_{\ell\sim L}[\ell]$
$\displaystyle=E_{\ell\sim L}[H(X_{\operatorname{supp}(D)}|L=\ell)]$
$\displaystyle=H(X_{\operatorname{supp}(D)}|L)$ $\displaystyle\leq
H(X_{\operatorname{supp}(D)})$
$\displaystyle=H(X_{\operatorname{supp}(D)}|L)+H(L)$ $\displaystyle\leq
dn+\frac{1}{2}\log(2\pi e(nd(1-d)+1/12)),$

so $dn\leq H(X_{\operatorname{supp}(D)})\leq dn+o(n),$ proving ($a$). Above,
we have used that the entropy of a binomial with variance $v$ is bounded by
$\frac{1}{2}\log(2\pi e(v+1/12))$ [Mas88]. For claim ($b$), note first that
since $\log\binom{n}{k}=\log\Gamma(n+1)-\log\Gamma(k+1)-\log\Gamma(n-k+1)$ and
$\Gamma$ is log-convex in $\mathbb{R}_{+}$, the extended function $[0,n]\ni
x\mapsto\log\binom{n}{x}$ is concave. Using this and that
$\frac{1}{n}\log\binom{n}{w(D)}\in[0,1]$, and taking $\delta>0$ such that
$(d-\delta,d+\delta)\subseteq[0,1],$ we get

$\displaystyle\mathbb{P}((d-\delta)n\leq
w(D)\leq(d+\delta)n)\inf_{d^{\prime}\in(d-\delta,d+\delta)}\frac{1}{n}\log\binom{n}{d^{\prime}n}$
$\displaystyle\leq\frac{1}{n}\mathbb{E}\left[\log\binom{n}{w(D)}\right]\leq\frac{1}{n}\log\binom{n}{dn}.$

By concentration of $w(D)$ and uniform convergence on the left hand side
(guaranteed by Dini’s theorem444Dini’s theorem states that a monotone limit of
continuous functions (to a continuous limit) in a compact set is uniform. That
$\frac{1}{n}\log\binom{n}{dn}\uparrow h(d)$, with $d\mapsto\binom{n}{dn}$
continuously extended via the $\Gamma$ function as above, is a standard
fact.), we get

$\displaystyle\inf_{d^{\prime}\in(d-\delta,d+\delta)}h(d^{\prime})\leq\liminf_{n}\frac{1}{n}\mathbb{E}\left[\log\binom{n}{w(D)}\right]\leq\limsup_{n}\frac{1}{n}\mathbb{E}\left[\log\binom{n}{w(D)}\right]\leq
h(d),$

and taking $\delta\to 0$, the continuity of $h$ yields claim ($b$), proving
(2).

Given the formula (2), to obtain the maximum rate it remains to calculate the
term $E_{\infty}$ defined below:

$\displaystyle E_{n}=E_{n}(d):=\frac{1}{n}H(D|X,Y),$ $\displaystyle\qquad
E_{\infty}=E_{\infty}(d):=\lim_{n\to\infty}E_{n}(d).$ (3)

We then have

$\displaystyle C_{\text{unif}}(d)=1-d-h(d)+E_{\infty}(d).$ (4)

Our work begins with the following observation, which was essentially made in
[HOS16] in a more general setting.555In [HOS16], the same observation is made
in a more general context, but under a further assumption. In the case of the
deletion channel, this assumption specializes to the fact that the deletion
pattern $D$ has the uniform distribution in some set. Of course, this is not
directly true: the law $Ber(d)^{n}$ of $D$ is not uniform. But it’s easy to
see, as was pointed out in [HOS16], that this point is superficial: $D$ can be
taken uniform in the strings of weight $dn$ without changing the asymptotics.
We will use this fact later as well.

######  Observation 2.1.

The distribution of $D$ conditioned on $X=x$ and $Y=y$ is uniform in the
set666Below, the font D is used to denote a realization of the random variable
$D.$

$\mathcal{D}(x,y):=\\{{\small{\textsc{D}}}\in\\{0,1\\}^{n}:{\small{\textsc{D}}}(x)=y\\}.$

This is intuitively clear, but since the rest of our work relies on this
observation, we give a proof.

###### Proof of Observation 2.1.

Take ${\small{\textsc{D}}}\in\mathcal{D}(x,y).$ We have

$\displaystyle\mathbb{P}(D={\small{\textsc{D}}}|X=x,Y=y)$
$\displaystyle=\frac{\mathbb{P}(X=x,Y=y|D={\small{\textsc{D}}})\mathbb{P}(D={\small{\textsc{D}}})}{\mathbb{P}(X=x,Y=y)}$
$\displaystyle=\frac{\mathbb{P}(X=x)}{\mathbb{P}(X=x,Y=y)}\mathbb{P}(Y=y|D={\small{\textsc{D}}},X=x)\mathbb{P}(D={\small{\textsc{D}}})$
$\displaystyle=\frac{\mathbb{P}(X=x)}{\mathbb{P}(X=x,Y=y)}d^{|x|-|y|}(1-d)^{|y|}.$

But the last expression is a function of only $x$ and $y$ (and not of D). ∎

From Observation 2.1, we obtain the following re-writing of $E_{n}$:

$\displaystyle E_{n}$
$\displaystyle=\frac{1}{n}\mathbb{E}[\log|\mathcal{D}(X,Y)|],$ (5)

where as before $X\sim Unif\\{0,1\\}^{n}$ and
$Y=\operatorname{\mathrm{BDC}}_{d}(X).$ In words: draw $X$ uniformly at random
and pick a random subsequence from it, where you select each bit in $X$
independently with probability $1-d$; what’s the exponent (in expectation) of
the number of times your chosen subsequence appears in $X$?

######  Remark 2.2.

As we suggested in the introduction, Observation 2.1 implies the simplicity of
the MAP decoding rule for uniformly-random codes, and hence it allows us to
cast this fact in information-theoretic language via (5). Indeed, when
decoding uniformly-random codes, one can simply output the codeword $x$ for
which the received string $y$ appears as a subsequence the most often, i.e.
the $x$ which maximizes $|\mathcal{D}(x,y)|$, because for
${\small{\textsc{D}}}\in\mathcal{D}(x,y)$ we have

$\displaystyle\mathbb{P}(X=x|Y=y)$
$\displaystyle=\frac{\mathbb{P}(X=x,D={\small{\textsc{D}}}|Y=y)}{\mathbb{P}(D={\small{\textsc{D}}}|Y=y,X=x)}$
$\displaystyle=|\mathcal{D}(x,y)|\frac{\mathbb{P}(D={\small{\textsc{D}}})\mathbb{P}(X=x|D={\small{\textsc{D}}})\mathbb{P}(Y=y|X=x,D={\small{\textsc{D}}})}{\mathbb{P}(Y=y)}$
$\displaystyle=|\mathcal{D}(x,y)|d^{|x|-|y|}(1-d)^{|y|}\frac{\mathbb{P}(X=x)}{\mathbb{P}(Y=y)}.$

###  2.3 Convergence Rate

In this subsection, we derive a bound on the speed of convergence of $E_{n}$
to $E_{\infty},$ as defined in (3). Analogous bounds, with a similar proof,
have appeared in the literature [Dal11, FD10, KM10].

We go back to our original expression for $E_{n},$ namely
$E_{n}=\frac{1}{n}H(D|X,Y).$ Let $J$ be the index of $Y$ such that the
substring $Y^{J}$ is the output of the first half of the deletion pattern $D$
on the first half of the input $X,$ i.e. $Y^{J}=D^{n/2}(X^{n/2}).$ We have

$\displaystyle E_{n}$ $\displaystyle=\frac{1}{n}H(D|X,Y)$
$\displaystyle=\frac{1}{n}H(D,J|X,Y)$
$\displaystyle=\frac{1}{n}[H(J|X,Y)+H(D|X,Y,J)]$
$\displaystyle=\frac{1}{n}[H(J|X,Y)+2H(D^{n/2}|X^{n/2},Y^{J})]$
$\displaystyle=\frac{1}{n}H(J|X,Y)+E_{n/2}.$

Hence

$\displaystyle 0\leq E_{n}-E_{n/2}\leq\frac{1}{n}H(J).$

Now, again using that for a binomial $J$ with variance $v$, we have
$H(J)\leq\frac{1}{2}\log(2\pi e(v+1/12))$ [Mas88], we get

$\displaystyle 0\leq E_{n}-E_{n/2}\leq\frac{1}{2n}\log(\pi e(d(1-d)n+1/6)).$
(6)

From this we can deduce a bound on the convergence rate.

######  Lemma 2.3.

For each $n\in\mathbb{N},$ we have

$\displaystyle 0\leq E_{\infty}-E_{n}\leq\frac{1}{2n}\log(8\pi
e\max\\{d(1-d)n,1/6\\}).$

###### Proof.

For $k\in\mathbb{N}$, by (6) we have

$\displaystyle 0\leq E_{2^{k}n}-E_{n}$
$\displaystyle=\sum_{j=1}^{k}E_{2^{j}n}-E_{2^{j-1}n}$
$\displaystyle\leq\frac{1}{2n}\sum_{j=1}^{k}\frac{1}{2^{j}}\log(2\pi
e\max\\{d(1-d)2^{j}n,1/6\\})$
$\displaystyle\leq\frac{1}{2n}\left[\sum_{j=1}^{k}\frac{j}{2^{j}}+\log(2\pi
e\max\\{d(1-d)n,1/6\\})\sum_{j=1}^{k}\frac{1}{2^{j}}\right],$

and taking $k\to\infty$ yields the lemma. ∎

As a gauge of the speed of convergence guaranteed by Lemma 2.3, note that at
$d=1/2$ (where our bound is loosest), we have shown

$0\leq E_{\infty}-E_{10,000}\leq 0.00087.$

##  3 Upper Bounds

So far, we have shown convergence rates of $E_{n}$ to $E_{\infty},$ but we
haven’t given any quantitative information on $E_{\infty}$, or equivalently,
on $C_{\text{unif}}$. In this section we prove our main result: an upper bound
on $E_{\infty}$, and hence on $C_{\text{unif}}$. In Section 3.1, we give an
exact expression, derived through analysis of random walks, for the
probability that two independent outputs of the $\operatorname{\mathrm{BDC}}$
(not necessarily with the same deletion probability) on a common uniformly
random input agree. In Section 3.2, we use this expression to give an
efficient algorithm to compute an upper bound on $E_{n}$ (and hence, after the
appropriate upwards shift from Section 2.3, on $E_{\infty}$). At the end of
Section 3.2, we point out a subtle issue that accounts for much of the loss
incurred in this first upper bound. Finally in Section 3.3, we correct this
issue, to obtain substantially improved upper bounds, which are also
efficiently computable.

###  3.1 Probability That Two Subsequences Agree

For $\alpha,\beta\in[0,1]$, let $D^{\alpha}\sim Ber(\alpha)^{n}$ and
$D^{\beta}\sim Ber(\beta)^{n}$ be independent. The objective of this section
is to give an explicit expression for
$\mathbb{P}(D^{\alpha}(X)=D^{\beta}(X)),$ where $X\sim Unif\\{0,1\\}^{n}.$ In
that direction, consider the differences

$\displaystyle\xi_{i}$
$\displaystyle=D_{i}^{\alpha}-D_{i}^{\beta}\in\\{-1,0,1\\},$ (7)

and the random walk $W=\\{W_{j}\\}_{j=1}^{n}$ defined by

$\displaystyle W_{j}$ $\displaystyle=\sum_{i=1}^{j}\xi_{i};\qquad W_{0}:=0.$
(8)

We then define the filtration

$\displaystyle\mathcal{F}_{j}:=\sigma(W_{i},D^{\alpha}_{i}:i\leq
j)=\sigma(D^{\beta}_{i},D^{\alpha}_{i}:i\leq j),$ (9)

and the process $\\{P_{j}\\}_{j=1}^{n}$ adapted to
$\\{\mathcal{F}_{j}\\}_{j=1}^{n}$ by

4 &1 if ξ_j ∈{±1}  and  W_j-1=0  or ξ_j=sgn(W_j-1),
1/2 if ξ_j ∈{±1}  and W_j-1≠0  and ξ_j≠sgn(W_j-1),
1 if ξ_j=0 and W_j-1=0,
1 if ξ_j=0 and W_j-1≠0 and D_j^α= 1,
1/2 if ξ_j=0 and W_j-1≠0 and D_j^α=0,

where $\operatorname{sgn}:\mathbb{R}\setminus\\{0\\}\to\\{\pm 1\\}$ denotes
the sign. Next, we need a definition.

######  Definition 3.1.

We say two strings $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{m}$ are _prefix-
equal_ , and write
$x\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny pr}}}}{{=}}}y$
if we have $x^{\min\\{n,m\\}}=y^{\min\\{n,m\\}}.$

We can now state our proposition.

######  Proposition 3.2.

We have
$\mathbb{P}(D^{\alpha}(X)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}D^{\beta}(X)|\mathcal{F}_{n})=\prod_{j=1}^{n}P_{j}$.

Before the proof, we record several important simplifications and
consequences. We first define the more restricted filtration
$\mathcal{G}_{j}:=\sigma(W_{i}:i\leq j)\subseteq\mathcal{F}_{j}.$ We note
that, conditioned on $\mathcal{G}_{n},$ the random variables
$\\{P_{j}\\}_{j=1}^{n}$ are mutually independent, and moreover we have
$\mathbb{E}[P_{j}|\mathcal{G}_{k}]=P_{j}^{\prime}$ for any $k\geq j,$ where

4 &1 if ξ_j ∈{±1}  and  W_j-1=0  or ξ_j=sgn(W_j-1),
1/2 if ξ_j ∈{±1}  and W_j-1≠0  and ξ_j≠sgn(W_j-1),
1 if ξ_j=0 and W_j-1=0,
αβ\+ (1-α)(1-β)/2αβ\+ (1-α)(1-β) if ξ_j=0 and W_j-1≠0.

By the conditional mutual independence, we therefore have

$\displaystyle\mathbb{P}(D^{\alpha}(X)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}D^{\beta}(X)|\mathcal{G}_{n})$
$\displaystyle=\mathbb{E}\left[\prod_{j=1}^{n}P_{j}\;\Bigg{|}\;\mathcal{G}_{n}\right]$
$\displaystyle=\prod_{j=1}^{n}P_{j}^{\prime},$

and thus

$\mathbb{P}(D^{\alpha}(X)=D^{\beta}(X)|\mathcal{G}_{n})=\mathbbm{1}_{w(D^{\alpha})=w(D^{\beta})}\prod_{j=1}^{n}P_{j}^{\prime}=\mathbbm{1}_{W_{n}=0}\prod_{j=1}^{n}P_{j}^{\prime}.$

We can simplify this further with a simple observation. A moment of thought
reveals that $W_{n}=0$ implies that the number of $j\in[n]$ such that
$P_{j}^{\prime}$ is of type (11) must equal the number of $j$ such that
$P_{j}^{\prime}$ is of type (11). Hence, defining the new “symmetrized”
process $\\{P_{j}^{\text{sym}}\\}_{j=1}^{n}$ as

$\displaystyle P_{j}^{\text{sym}}$
$\displaystyle=\begin{cases}1/\sqrt{2}\qquad&\text{if }\xi_{j}\in\\{\pm
1\\},\\\ 1&\text{if }\xi_{j}=0\text{ and }W_{j}=0,\\\
\frac{\alpha\beta+(1-\alpha)(1-\beta)/2}{\alpha\beta+(1-\alpha)(1-\beta)}&\text{if
}\xi_{j}=0\text{ and }W_{j}\neq 0,\end{cases}$

we immediately obtain the following corollary.

######  Corollary 3.3.

We have
$\mathbb{P}(D^{\alpha}(X)=D^{\beta}(X))=\mathbb{E}[\mathbbm{1}_{W_{n}=0}\prod_{j=1}^{n}P_{j}^{\text{sym}}].$

We finally prove the proposition.

###### Proof of Proposition 3.2.

We proceed by induction on $n.$ For $n=1$ we clearly have
$1=\mathbb{P}(D^{\alpha}(X)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}D^{\beta}(X)|W)=P_{1}.$ Now suppose we have the desired formula
for $n-1$. We consider first the case where $W_{n-1}=0,$ i.e. where
$(D^{\alpha})^{n-1}(X^{n-1})$ and $(D^{\beta})^{n-1}(X^{n-1})$ have the same
length. If $\xi_{j}\in\\{\pm 1\\}$, we have

$\displaystyle\\{(D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})\\}$
$\displaystyle=\\{(D^{\alpha})^{n-1}(X^{n-1})=(D^{\beta})^{n-1}(X^{n-1})\\}$
$\displaystyle=\\{(D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})\\}.$

Moreover if $\xi_{j}=0,$ either $X_{n}$ is deleted by both deletion patterns,
or it’s deleted by neither and appears as the last bit of both
$(D^{\alpha})^{n}(X)$ and $(D^{\beta})^{n}(X)$. Hence in all cases where
$W_{n-1}=0$, we have

$\displaystyle\mathbb{P}((D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})|W^{n})$
$\displaystyle=1\cdot\mathbb{P}((D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})|W^{n-1})$
$\displaystyle=P_{n}\cdot\mathbb{P}((D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D\beta)^{n-1}(X^{n-1})|W^{n-1}),$

and by inductive hypothesis we obtain the desired formula for $n.$ Finally we
consider the case where $W_{n-1}\neq 0,$ and assume without loss of generality
that $W_{n-1}>0$, i.e. that $(D^{\alpha})^{n-1}(X^{n-1})$ is _shorter_ than
$(D^{\beta})^{n-1}(X^{n-1}).$ Note first that $\xi_{n}=1$ again implies that

$\\{(D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})\\}=\\{(D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})\\},$

and in this case we also appropriately have $P_{n}=1.$ Next if $\xi_{n}=-1,$
then $X_{n}$ is deleted by $\widetilde{D}^{n}$ and not by $D^{n}.$ Hence the
last bits of $\widetilde{D}^{n}(X^{n})$ and $D^{n}(X^{n})$ come from different
indices in $X,$ and they agree with probability $1/2,$ yielding

$\mathbb{P}((D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})|W^{n})=\frac{1}{2}\mathbb{P}((D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})|W^{n-1}).$

Lastly if $\xi_{n}=0,$ then if $D^{\alpha}_{n}=1,$ we had
$D_{n}^{\alpha}=D^{\beta}_{n}=1,$ and if $D^{\alpha}_{n}=0,$ we had
$D^{\alpha}_{n}=D^{\beta}_{n}=0.$ In the former case, we again have
$\\{(D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})\\}=\\{(D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})\\},$ while in the latter case we again have
$\mathbb{P}((D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})|W^{n})=\frac{1}{2}\mathbb{P}((D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})|W^{n-1}).$ Therefore again

$\displaystyle\mathbb{P}((D^{\alpha})^{n}(X^{n})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n}(X^{n})|W^{n})=P_{n}\cdot\mathbb{P}((D^{\alpha})^{n-1}(X^{n-1})\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
pr}}}}{{=}}}(D^{\beta})^{n-1}(X^{n-1})|W^{n-1}),$

and by inductive hypothesis we have corroborated the case $W_{n-1}\neq 0,$
proving the proposition. ∎

###  3.2 Warmup: Uniform Measure Upper Bound

In this section, we give a first (naive) upper bound on $E_{n}$, as defined in
(3), and hence, by our formula (4), we obtain a first upper bound on
$C_{\text{unif}}.$ At the heart of our proof is an application of the formula
derived in the last subsection.

We begin with an application of Jensen’s inequality:

$\displaystyle E_{n}$
$\displaystyle=\frac{1}{n}\mathbb{E}_{X,Y}\log|\mathcal{D}(X,Y)|$
$\displaystyle\leq\frac{1}{n}\log\mathbb{E}_{X,Y}|\mathcal{D}(X,Y)|.$

We wish to calculate $\mathbb{E}_{X,Y}|\mathcal{D}(X,Y)|$, at fixed $n,$
exactly and efficiently. Letting $\widetilde{D}\sim
Unif\\{0,1\\}^{n}=Ber(1/2)^{n},$ we can re-write
$\mathbb{E}_{X,Y}|\mathcal{D}(X,Y)|=2^{n}\mathbb{P}(D(X)=\widetilde{D}(X))$,
where as before $D\sim Ber(d)^{n}$ and $X\sim Unif\\{0,1\\}^{n}$. We combine
this with Lemma 2.3 and (4), and record it below.

######  Lemma 3.4 (Warmup Upper Bound).

For each $n\in\mathbb{N}$ and $d\in[0,1]$, we have

$\displaystyle C_{\text{unif}}(d)\leq
2-d-h(d)+\frac{1}{n}\log\mathbb{P}(D(X)=\widetilde{D}(X))+\frac{1}{2n}\log(8\pi
e\max\\{d(1-d)n,1/6\\}),$

where $D\sim Ber(d)^{n}$ and $\widetilde{D}\sim Unif\\{0,1\\}^{n}$

We note that the name of this subsection comes from the fact that the law of
$\widetilde{D}$ is chosen uniform in $\\{0,1\\}^{n};$ in the next subsection,
we obtain an improvement by choosing a non-uniform measure. For now, we
proceed by applying Corollary 3.3 with $\alpha=d,\beta=1/2$, to obtain

$\displaystyle\mathbb{P}(D(X)=\widetilde{D}(X))$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{W_{n}=0}\prod_{j=1}^{n}U_{j}\right]$
(12)

with

$\displaystyle U_{j}$ $\displaystyle=\begin{cases}1/\sqrt{2}\qquad&\text{if
}\xi_{j}\in\\{\pm 1\\},\\\ 1&\text{if }\xi_{j}=0\text{ and }W_{j}=0,\\\
(1+d)/2&\text{if }\xi_{j}=0\text{ and }W_{j}\neq 0,\end{cases}$

and $\\{\xi_{j}\\}_{j=1}^{n}$, $\\{W_{j}\\}_{j=1}^{n},$ defined as in (7),
(8), respectively. From this we derive an algorithm to compute
$\mathbb{P}(D(X)=\widetilde{D}(X))$.

######  Theorem 3.5.

Consider the domain $A:=\\{(n,k):n\geq-1,|k|\leq
n+1\\}\subseteq\mathbb{Z}^{2}$, and its interior $A^{\circ}=\\{(n,k):n\geq
0,|k|\leq n\\}$. Define a function $R:A\to\mathbb{R}_{+}$ by the initial value
$R(0,0)=1,$ the recurrence relation

$R(n,k)=R(n-1,k)\cdot\frac{1}{2}\left(1-\frac{1-d}{2}\mathbbm{1}_{\\{k\neq
0\\}}\right)+R(n-1,k-1)\cdot\frac{d}{2\sqrt{2}}+R(n-1,k+1)\cdot\frac{1-d}{2\sqrt{2}}$

on $A^{\circ}\setminus\\{(0,0)\\},$ and the boundary condition $R\equiv 0$ on
$A\setminus A^{\circ}.$ Then we have
$\mathbb{P}(\widetilde{D}(X)=D(X))=R(n,0).$ In particular,
$\mathbb{P}(\widetilde{D}(X)=D(X))$ can be computed exactly in time $O(n^{2})$
and space $O(n).$

###### Proof.

We will prove that, on $A^{\circ},$ we have

$\displaystyle
R(n,k)=\mathbb{E}\left[\mathbbm{1}_{W_{n}=k}\prod_{j=1}^{n}U_{j}\right].$ (13)

The first part of the theorem then immediately follows from (12). We proceed
by induction on $n$. The validity of (13) for the initial condition $n=0$ is
immediate: we have $W_{0}=0$ with probability 1, and an empty product
evaluates to 1 by convention. Assume (13) holds for $n-1.$ For a point
$(n,k)\in A^{\circ},$ consider the filtration
$\mathcal{G}_{n}=\sigma(W_{j}:j\leq n)$ defined above. We have

$\displaystyle\mathbb{E}\left[\mathbbm{1}_{W_{n}=k}\prod_{j=1}^{n}U_{j}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{j=1}^{n-1}U_{j}\mathbb{E}\left[\mathbbm{1}_{W_{n}=k}U_{n}\;\Bigg{|}\;\mathcal{G}_{n-1}\right]\right].$

But

$\displaystyle\mathbb{E}[\mathbbm{1}_{W_{n}=k}\cdot
U_{n}\;|\;\mathcal{G}_{n-1}]$
$\displaystyle=\mathbb{E}[(\mathbbm{1}_{W_{n-1}=k}+\mathbbm{1}_{W_{n-1}=k-1}+\mathbbm{1}_{W_{n-1}=k+1})\mathbbm{1}_{W_{n}=k}\cdot
U_{n}\;|\;\mathcal{G}_{n-1}]$
$\displaystyle=\mathbbm{1}_{W_{n-1}=k}\cdot\frac{1}{2}\left(\mathbbm{1}_{k=0}+\mathbbm{1}_{k\neq
0}\frac{1+d}{2}\right)+\mathbbm{1}_{W_{n-1}=k-1}\cdot\frac{d}{2}\cdot\frac{1}{\sqrt{2}}+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\mathbbm{1}_{W_{n-1}=k+1}\cdot\frac{(1-d)}{2}\cdot\frac{1}{\sqrt{2}},$
$\displaystyle=\mathbbm{1}_{W_{n-1}=k}\cdot\frac{1}{2}\left(1-\frac{1-d}{2}\mathbbm{1}_{\\{k\neq
0\\}}\right)+\mathbbm{1}_{W_{n-1}=k-1}\cdot\frac{d}{2\sqrt{2}}+\mathbbm{1}_{W_{n-1}=k+1}\cdot\frac{1-d}{2\sqrt{2}}.$

Finally for points $(n,k)$ adjacent to the boundary, note that, if
$(n-1,\ell)\in A\setminus A^{\circ},$ for $\ell\in\\{k-1,k,k+1\\},$ we have
$\mathbbm{1}_{W_{n-1}=\ell}\equiv 0.$ Thus, by inductive hypothesis, we have
(13), and hence the first part of the theorem.

For the second part of the theorem, the bound on the time complexity is
obvious from the first part. To justify the space bound, note that our
recursive formula for $R(n,k)$ only involves terms of the form $R(n-1,\ell)$
for some $\ell.$ Hence, we can compute $R$ on the strip
$(\\{n\\}\times\mathbb{Z})\cap A$ as a function of only
$R|_{(\\{n-1\\}\times\mathbb{Z})\cap A}$, so at any given time we only need to
store the value of $R$ at two adjacent strips $n$-strips, yielding $O(n)$
space. ∎

Below we plot the upper bound of Lemma 3.4 for $C_{\text{unif}}$, and its
implied upper bound on $E_{\infty}$ via (4). We compute these bounds using
Theorem 3.5 with $n=10,000.$ We also plot the lower bounds of [DG01, RD13,
HOS16] and our simulation results. We note that the numerical bound we obtain
from this naive upper bound in fact improves upon the numerical bound from
Theorem 1.1 that we presented in Section 1.2 for the range of
$d\in[0.54,0.7]$, and by up to 0.008 at $d\approx 0.63$. This is simply
because the lower time complexity of this naive bound allows us to easily
compute it for larger $n.$

(a) Our upper bound on $C_{\text{unif}}$ (blue), the corresponding
best lower bound (orange), and the simulation-based
lower (red) and upper (green) bounds.

(b) Our upper bound on $E_{\infty}$ (blue), the best lower bound on
$E_{\infty}$ implied by the lower bounds on $C_{\text{unif}}$ from subfigure
(a) (orange), and the simulation-based lower (red) and upper (green) bounds.

Figure 3: Our upper bounds from Lemma 3.4 (blue), for $n=10,000$, plotted with
the best known corresponding lower bounds (orange), and the simulation-based
lower (red) and upper (green) bounds. The orange lower bounds are obtained by
taking the maximum of the results in [DG01, RD13, HOS16] for each $d.$

The gap in our upper bound can be qualitatively understood. The only loss we
incurred came from our application of Jensen’s inequality at the beginning of
this section. Since we’re dealing with an exponential-sized object
$|\mathcal{D}(X,Y)|,$ its expectation can be wildly swayed by events of
exponentially small probability. An example of such an event is that the
length of the output $L=|Y|$ deviates from its expectation $(1-d)n$ by a
constant multiple $\delta$ of $n.$ This happens with probability $O(2^{-\alpha
n})$ for some $\alpha=\alpha(\delta)>0$, but if the expected increase

$\displaystyle\log\left(\frac{\mathbb{E}[|\mathcal{D}(X,Y)|\;|\;|L-(1-d)n|>\delta
n]}{\mathbb{E}[|\mathcal{D}(X,Y)|\;|\;|L-(1-d)n|\leq\delta n]}\right)$ (14)

is greater than $\alpha,$ then the regime where $|L-(1-d)n|>\delta n$ will
impact the value of $\log\mathbb{E}|\mathcal{D}(X,Y)|.$ A moment of thought
reveals that (14) is small whenever $d$ is at a maximum of $d\mapsto
E_{n}(d)$; hence in this case the loss in our approximation cannot be
explained by deviations of $L$ away from its expectation. On the other hand if
$E_{n}(d)$ is increasing at $d,$ then $\mathbb{E}|\mathcal{D}(X,Y)|$ will be
exponentially swayed upwards by the contribution of the event
$L\geq(1-d+\delta)n.$ Symmetrically, if $E_{n}$ is decreasing at $d,$ then
$\mathbb{E}|\mathcal{D}(X,Y)|$ will be exponentially swayed upwards by the
contribution of the event $L\leq(1-d-\delta)n.$ And indeed, that our bound is
loose when $d\mapsto E_{n}(d)$ is increasing or decreasing, and close to tight
when it’s at a maximum, is exactly what we observe in Figure 3(b).

###  3.3 Non-Uniform Measure Upper Bound

At the end of the last section we observed qualitatively that our naive bound
was loosened substantially by the exponentially-unlikely event that
$||Y|-(1-d)n|=\Omega(n).$ Now, what we ultimately want to upper bound is
$E_{n}=\frac{1}{n}\mathbb{E}\log|\mathcal{D}(X,Y)|,$ which can’t possibly be
swayed by such events by virtue of $\frac{1}{n}\log|\mathcal{D}(X,Y)|$ being
in $[0,1]$. In this section, we obtain an improved upper bound by “removing”
these unlikely events from the expectation altogether.

We begin with a definition.

######  Definition 3.6.

For $X\sim Unif\\{0,1\\}^{n}$ and $u\in[n],$ we let $Y[u]$ denote the random
variable obtained by deleting _exactly_ $u$ uniformly-chosen bits from $X.$ We
distinguish this from the notation $Y(d):=\operatorname{\mathrm{BDC}}_{d}(X).$

To improve our upper bound on $E_{\infty}$, our approach will be to upper
bound

$E_{n}^{\prime}=E_{n}^{\prime}[u]:=\frac{1}{n}\mathbb{E}\log|\mathcal{D}(X,Y[u])|.$

It’s not hard to see that $E_{n}^{\prime}[dn]\to E_{\infty}(d)$ as
$n\to\infty$ (this follows, e.g., by [Dal11, Theorem 1]), but we’d like to get
a non-asymptotic version of that statement so that we can relate our upper
bound on $E_{n}^{\prime}$ to $E_{\infty}$, and hence $C_{\text{unif}}.$
Unfortunately, our arguments from Subsection 2.3 no longer work because the
different bits in the deletion pattern are now dependent. We temporarily
disregard this issue, and in Subsection 3.3.1, we focus on upper bounding
$E_{n}^{\prime}$ using the methods of subsections 3.1 and 3.2. Then in
Subsection 3.3.2, we show a simple way to circumvent the issue of convergence
of $E_{n}^{\prime}$ to $E_{\infty},$ by directly upper bounding $E_{n}$ by an
averaging of $E_{n}^{\prime}$ values, and then applying the results from
Subsection 2.3 to relate $E_{\infty}$ to $E_{n}.$ This yields a proof of
Theorem 1.1. This method has the advantages of being very simple to prove
(once one has an upper bound on $E_{n}^{\prime}$), and of having error terms
which sharply decay with $n.$ However, it has the disadvantage of making the
runtime jump to $O(n^{4}).$ In Subsection 3.3.3, we instead get a non-
asymptotic handle on $E_{\infty}$ in this setting by relating $E_{n}(d)$ to
$E_{n}^{\prime}[(d\pm\delta)n],$ for $\delta$ small. This reduces the runtime
to $O(n^{3})$, but introduces error terms which decay more slowly. In
practice, the best numerical upper bounds are still obtained by the simpler
approach of Subsection 3.3.2

####  3.3.1 Upper bounding $E_{n}^{\prime}$

In this section, we apply the techniques from subsections 3.1 and 3.2 to
obtain an upper bound on $E_{n}^{\prime}[u],$ for $u\in\\{0,1,\dots,n\\}$. As
in Subsection 3.2, by Jensen we can write

$\displaystyle E_{n}^{\prime}[u]$
$\displaystyle=\frac{1}{n}\mathbb{E}[\log|\mathcal{D}(X,Y[u])|]$
$\displaystyle\leq\frac{1}{n}\log\mathbb{E}[|\mathcal{D}(X,Y[u])|].$

Letting $D,D^{\prime}\sim_{iid}Ber(u/n)^{n}$, we have

$\displaystyle\mathbb{E}[|\mathcal{D}(X,Y[u])|]$
$\displaystyle=\binom{n}{u}\mathbb{P}(D(X)=D^{\prime}(X)|w(D)=w(D^{\prime})=u)$
$\displaystyle=\frac{1}{\binom{n}{u}d^{2u}(1-d)^{2(n-u)}}\mathbb{P}(D(X)=D^{\prime}(X),\;w(D)=w(D^{\prime})=u),$

so defining

$\displaystyle\Pi_{n}^{\ell}[u]$
$\displaystyle:=\mathbb{P}(D(X)=D^{\prime}(X),\;w(D)=w(D^{\prime})=u),\qquad\qquad
D,D^{\prime}\sim_{iid}Ber(\ell/n)^{n},$ (15)

we have shown

$\displaystyle E_{n}^{\prime}[u]$
$\displaystyle\leq\frac{1}{n}\log\Pi_{n}^{u}[u]-\frac{1}{n}\log\binom{n}{u}+2h(u/n).$

Using Lemma A.2 from the appendix, we get

$\displaystyle E_{n}^{\prime}[u]$
$\displaystyle\leq\frac{1}{n}\log\Pi_{n}^{u}[u]+h(u/n)+\frac{1}{2n}\log(\max\\{2\pi
u(n-u)/n,1\\})+\frac{\log e}{6n\max\\{\min\\{u,n-u\\},1\\}}.$ (16)

Our remaining task in this section is to efficiently compute $\Pi_{n}^{u}[u].$
From Proposition 3.2, setting $\alpha=\beta=\ell/n,$ for
$D,D^{\prime}\sim_{iid}Ber(\ell/n)^{n}$ we have

$\mathbb{P}(D(X)=D^{\prime}(X),w(D)=w(D^{\prime})=u|\mathcal{F}_{n})=\mathbbm{1}_{W_{n}=0,\,w(D)=u}\cdot\prod_{j=1}^{n}P_{j}.$

By the same argument as in Subsection 3.2, we can replace $P_{j}$ by the
symmetrized process

$\displaystyle V_{j}=\begin{cases}1/\sqrt{2}\qquad&\text{if }\xi_{j}\in\\{\pm
1\\},\\\ 1&\text{if }\xi_{j}=0\text{ and }W_{j-1}=0,\\\ 1&\text{if
}\xi_{j}=0\text{ and }W_{j-1}\neq 0\text{ and }D_{j}=1,\\\ 1/2&\text{if
}\xi_{j}=0\text{ and }W_{j-1}\neq 0\text{ and }D_{j}=0,\end{cases}$

from which we obtain the following corollary of Proposition 3.2.

######  Corollary 3.7.

Let $\Pi_{n}^{\ell}[u]$ be defined by (15). We have

$\displaystyle\Pi_{n}^{\ell}[u]=\mathbb{E}\left[\mathbbm{1}_{W_{n}=0,\,w(D)=u}\cdot\prod_{j=1}^{n}V_{j}\right],$

where $V_{j}$ is defined as above with $D,D^{\prime}\sim Ber(\ell/n)^{n}.$

Using this, we obtain a recursive relation analogous to Theorem 3.5 to
calculate $\Pi_{n}^{u}[u]$ efficiently.

######  Theorem 3.8.

Consider the domain $B:=\\{(n,k,u):n\geq-1,|k|\leq n+1,0\leq u\leq
n+1\\}\subseteq\mathbb{Z}^{3},$ and its interior $B^{\circ}:=\\{(n,k,u):n\geq
0,|k|\leq n,0\leq u\leq n\\}.$ For $\ell\in\\{0,1,\dots,n\\},$ define a
function $S^{\ell}:B\to\mathbb{R}_{+}$ by the initial value
$S^{\ell}(0,0,0)=1,$ the recurrence relation

$\displaystyle S^{\ell}(n,k,u)$
$\displaystyle=(\ell/n)^{2}S^{\ell}(n-1,k,u-1)+\frac{(\ell/n)(1-(\ell/n))}{\sqrt{2}}\left(S^{\ell}(n-1,k-1,u-1)+S^{\ell}(n-1,k+1,u)\right)$
$\displaystyle\qquad\qquad+(1-(\ell/n))^{2}\left(1-\frac{1}{2}\mathbbm{1}_{k\neq
0}\right)S^{\ell}(n-1,k,u).$

on $B^{\circ}\setminus\\{(0,0,0)\\}$, and the boundary condition
$S^{\ell}\equiv 0$ on $B\setminus B^{\circ}.$ Then, if $\Pi_{n}^{\ell}[u]$ is
defined by (15), we have $\Pi_{n}^{\ell}[u]=S^{\ell}(n,0,u).$ In particular,
$\Pi_{n}^{u}[u]$ can be computed in time $O(n^{3})$ and space $O(n^{2}).$

###### Proof.

For simplicity, we drop the superscript $\ell$ in the notation and set
$d=\ell/n.$ The proof is analogous to that of Theorem 3.5. We will prove that,
on $B^{\circ},$ we have

$\displaystyle S(n,k,u)$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{W_{n}=k,\,w(D)=u}\cdot\prod_{j=1}^{n}V_{j}\right].$
(17)

The first part of the theorem then follows from Corollary 3.7. We proceed by
induction on $n.$ The validity of (17) for the initial condition $n=0$ is
immediate: we have $W_{0}=0$ and $w(D^{0})=w(\emptyset)=0$ with probability 1,
and an empty product evaluates to 1 by convention. Assume (17) holds for
$n-1.$ For a point $(n,k,u)\in B,$ consider the filtration
$\mathcal{F}_{n}=\sigma(W_{i},D_{i}:i\leq n)$. We have

$\mathbb{E}\left[\mathbbm{1}_{W_{n}=k,\,w(D)=u}\cdot\prod_{j=1}^{n}V_{j}\right]=\mathbb{E}\left[\prod_{j=1}^{n-1}V_{j}\cdot\mathbb{E}\left[\mathbbm{1}_{W_{n}=k,\,w(D)=u}\cdot
V_{n}\;\Bigg{|}\;\mathcal{F}_{n-1}\right]\right].$

But

$\displaystyle\mathbb{E}\left[\mathbbm{1}_{W_{n}=k,\,w(D)=u}\cdot
V_{n}\;|\;\mathcal{F}_{n-1}\right]$
$\displaystyle=\mathbb{E}[(\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}+\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}+\mathbbm{1}_{W_{n-1}=k-1,w(D^{n-1})=u-1}$
$\displaystyle\qquad\qquad+\mathbbm{1}_{W_{n-1}=k+1,w(D^{n-1})=u})\mathbbm{1}_{W_{n}=k,w(D)=u}\cdot
V_{n}\;|\;\mathcal{F}_{n-1}]$
$\displaystyle=\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}d^{2}\cdot
1+\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}d(1-d)\cdot\frac{1}{\sqrt{2}}$
$\displaystyle\qquad+\mathbbm{1}_{W_{n-1}=k-1,w(D^{n-1})=u-1}(1-d)d\cdot\frac{1}{\sqrt{2}}$
$\displaystyle\qquad+\mathbbm{1}_{W_{n-1}=k+1,w(D^{n-1})=u}(1-d)^{2}\cdot\left(\mathbbm{1}_{W_{n}=0}+\frac{1}{2}\mathbbm{1}_{W_{n}\neq
0}\right)$ $\displaystyle=\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}d^{2}\cdot
1+\mathbbm{1}_{W_{n-1}=k,w(D^{n-1})=u-1}d(1-d)\cdot\frac{1}{\sqrt{2}}$
$\displaystyle\qquad+\mathbbm{1}_{W_{n-1}=k-1,w(D^{n-1})=u-1}(1-d)d\cdot\frac{1}{\sqrt{2}}$
$\displaystyle\qquad+\mathbbm{1}_{W_{n-1}=k+1,w(D^{n-1})=u}(1-d)^{2}\cdot\left(1-\frac{1}{2}\mathbbm{1}_{W_{n}\neq
0}\right).$

Finally for points $(n,k,u)$ adjacent to the boundary, note that if
$(n-1,\ell,t)\in B\setminus B^{\circ},$ for
$(\ell,t)\in\\{(k,u-1),(k-1,u-1),(k+1,u),(k,u)\\},$ we have
$\mathbbm{1}_{W_{n-1}=\ell,w(D^{n-1})=t}\equiv 0$. Thus, by inductive
hypothesis, we have (17), and hence the first part of the theorem.

For the second part of the theorem, again the bound on the time complexity is
obvious from the first part. The justification on the space bound is the same
as in Theorem 3.5: we can compute $S$ on the strip
$(\\{n\\}\times\mathbb{Z}^{2})\cap B$ as a function of only the values of the
previous strip $(\\{n-1\\}\times\mathbb{Z}^{2})\cap B$. Hence all other values
can be discarded, yielding $O(n^{2})$ space and hence the theorem. ∎

####  3.3.2 Proof of Theorem 1.1

We let $L:=w(D)$ denote the number of deleted bits, for $D\sim Ber(d)^{n}.$ By
the tower property of conditional expectation, we have

$\displaystyle E_{n}(d)$
$\displaystyle=\mathbb{E}[\mathbb{E}[\log|\mathcal{D}(X,Y)|\;|L]]=\mathbb{E}E_{n}^{\prime}[L].$
(18)

Hence an upper bound on $E_{n}^{\prime}[u]$ for all $u\in[n]$ implies an upper
bound on $E_{n}(d)$ for all $d,$ and thus on $C_{\text{unif}}$. We now prove
Theorem 1.1.

###### Proof of Theorem 1.1.

Noting that $L\sim Binom(n,d),$ we get
$\mathbb{P}(L=u)=\binom{n}{u}d^{u}(1-d)^{n-u}.$ Combining this with (18),
(16), (4) and Lemma 2.3 yields

$\displaystyle C_{\text{unif}}(d)\leq 1-d-h(d)+$
$\displaystyle\frac{1}{2n}\log(8\pi
e\max\\{d(1-d)n,1/6\\})+\sum_{u=0}^{n}\binom{n}{u}d^{u}(1-d)^{n-u}\Bigg{(}\frac{1}{n}\log\Pi_{n}^{u}[u]$
$\displaystyle+h(u/n)+\frac{1}{2n}\log(\max\\{2\pi u(n-u)/n,1\\})+\frac{\log
e}{6n\max\\{\min\\{u,n-u\\},1\\}}\Bigg{)}.$

The computability of $\Pi_{n}^{u}[u]$ in time $O(n^{3})$ and space $O(n^{2})$
is guaranteed by Theorem 3.3. Since for each $d$ we have to compute
$\Pi_{n}^{u}[u]$ for $u\in\\{0,1,\dots,n\\},$ the overall complexity is
$O(n^{4})$ time and $O(n^{2})$ space. This completes the proof. ∎

We repeat the figure of Subsection 1.2 with the explicit evaluation of our
bound. We also include here the corresponding implied upper bound on
$E_{\infty}.$

(a) Our upper bound on $C_{\text{unif}}$ (blue), the corresponding
best lower bound (orange), and the simulation-based
lower (red) and upper (green) bounds.

(b) Our upper bound on $E_{\infty}$ (blue), the best lower bound on
$E_{\infty}$ implied by the lower bounds on $C_{\text{unif}}$ from subfigure
(a) (orange), and the simulation-based lower (red) and upper (green) bounds.

Figure 4: Our upper bounds from Theorem 1.1 (blue), for $n=1,000$, plotted
with the best known corresponding lower bounds (orange), and the simulation-
based lower (red) and upper (green) bounds. The orange lower bounds are
obtained by taking the maximum of the results in [DG01, RD13, HOS16] for each
$d.$

####  3.3.3 Proof of Theorem 1.2

In the last subsection, we obtained an improvement over the naive bound of
Subsection 3.2, but the runtime jumped from $O(n^{2})$ to $O(n^{4}).$ In this
subsection, we improve this runtime to $O(n^{3}),$ at the cost of worse error
terms.

We first collect a useful lemma.

######  Lemma 3.9.

The function $k\mapsto H(X|Y[k])$ is monotone-increasing.

The (elementary) proof is in the appendix. From this we obtain the following
bounds, which are a simple sharpening of [Dal11, Lemma 4].

######  Lemma 3.10.

For all $d,\delta\in[0,1],$ we have

$\displaystyle\frac{H(X|Y[(d-\delta)n])}{n}-2^{-nD(d-\delta||d)}$
$\displaystyle\leq\frac{H(X|Y(d))}{n}\leq\frac{H(X|Y[(d+\delta)n])}{n}+2^{-nD(d+\delta||d)},$

where $D(\cdot||\cdot):[0,1]^{2}\to\mathbb{R}_{+}$ is the (base 2) KL-
divergence for two Bernoulli distributions.

###### Proof.

For $K\sim Binom(n,d),$ we can write

$\displaystyle H(X|Y(d))$ $\displaystyle=\mathbb{E}_{k\leftarrow
K}[H(X|Y[k])].$

But from Lemma 3.9 and the fact that $H(X|Y[k])/n\in[0,1]$ for all $k\in[n]$,
we immediately deduce

$\displaystyle(1-\mathbb{P}(K\leq(d-\delta)n))\frac{H(X|Y[(d-\delta)n])}{n}\leq\frac{H(X|Y(d))}{n}\leq\frac{H(X|Y[(d+\delta)n])}{n}+\mathbb{P}(K\geq(d+\delta)n).$

The lemma then follows by a standard large-deviations bound on the binomial
distribution, and again the fact that $H(X|Y[(d-\delta)n])/n\leq 1.$ ∎

Now we perform the derivation analogous to (2) for the case of $H(X|Y[\alpha
n]),$ for $\alpha\in[0,1].$ Noting that the deletion pattern, denoted
$D^{\prime},$ is now distributed uniformly in the strings of Hamming weight
$\alpha n,$ we have

$\displaystyle H(X|Y[\alpha n])$
$\displaystyle=H(X,D^{\prime}|D^{\prime}(X))-H(D^{\prime}|X,Y[\alpha n])$
$\displaystyle=H(X_{\operatorname{supp}(D^{\prime})})+H(D^{\prime})-H(D^{\prime}|X,Y[\alpha
n])$ $\displaystyle=dn+\log\binom{n}{\alpha n}-n\cdot E_{n}^{\prime}[\alpha
n].$

In the last step we have used the fact that, conditioned on $X=x$ and
$Y[\alpha n]=y,$ $D^{\prime}$ is again uniform on $\mathcal{D}(x,y)$, which
follows by a trivial modification of our proof of Observation 2.1. Putting
this together with Lemma 3.10 and our bounds obtained in the derivation of
(2), we get

$\displaystyle
d-\delta+\frac{1}{n}\log\binom{n}{(d-\delta)n}-E_{n}^{\prime}[(d-\delta)n]-2^{-nD(d-\delta||d)}$
$\displaystyle\leq d+\frac{1}{2n}\log(2\pi
e(nd(1-d)+1/12))+\frac{1}{n}\log\binom{n}{dn}-E_{n}(d).$

Reordering and combining with Lemma 2.3 yields the following: for all
$d\in(0,1)$ and $n\in\mathbb{N},$ we have

$\displaystyle E_{\infty}(d)$
$\displaystyle\leq\inf_{\delta>0}E^{\prime}_{n}[(d-\delta)n]+\delta+2^{-nD(d-\delta||d)}+\frac{1}{n}\left[\log\binom{n}{dn}-\log\binom{n}{(d-\delta)n}+\log(8\pi
e\max\\{d(1-d)n,1/6\\})\right],$ (19)

where the infimum is over the $\delta>0$ such that $d-\delta\geq 0.$ We can
now prove Theorem 1.2.

###### Proof of Theorem 1.2.

Putting together (19) and (16), and using that
$\frac{1}{n}\log\binom{n}{dn}\leq h(d)$ for all $n,$ we get

$\displaystyle E_{\infty}(d)$
$\displaystyle\leq\inf_{\delta>0}\frac{1}{n}\log\Pi_{n}^{(d-\delta)n}[(d-\delta)n]+h(d)+\delta+2^{-nD(d-\delta||d)}$
$\displaystyle\qquad\qquad+2\left[h(d-\delta)-\frac{1}{n}\log\binom{n}{(d-\delta)n}\right]+\frac{1}{n}\log(8\pi
e\max\\{d(1-d)n,1/6\\}).$

Combining this with Lemma A.2 in the appendix and (4) yields

$\displaystyle C_{\text{unif}}(d)$ $\displaystyle\leq
1-d+\inf_{\delta}\Bigg{[}\frac{1}{n}\log\Pi_{n}^{(d-\delta)n}[(d-\delta)n]+\delta+2^{-nD(d-\delta||d)}+\frac{1}{n}\log(\max\\{2\pi(d-\delta)(1-d+\delta)n,1\\})$
$\displaystyle\qquad\qquad\qquad+\frac{1}{n}\log(8\pi
e\max\\{d(1-d)n,1/6\\})+\frac{\log
e}{3n^{2}\max\\{\min\\{d-\delta,1-d+\delta\\},1\\}}\Bigg{]},$

as desired. The final part of the theorem, regarding runtime, is true by
Theorem 3.8, as in the proof of Theorem 1.1. ∎

##  4 Simulating $E_{n}$

Given $x$ and $y,$ the quantity $|\mathcal{D}(x,y)|$ can be calculated in time
$O(|x||y|)$ and auxiliary space $O(|y|)$ by a standard dynamic programming
algorithm (see, e.g., [Lot05, Mit09]). We define an array $a$ of length equal
to $|y|.$ We iterate an index $i=0,\dots,|x|-1.$ At each fixed value of $i,$
the idea is to update our array $a$ such that, for each $j=0,\dots,|y|-1,$ the
value $a[j]$ counts the number of times that $y^{j+1}$ appears as a
subsequence in $x^{i+1}.$ For fixed $i$, this can be computed as a function of
$x_{i+1},y_{j+1}$, and the previous values of $a[j-1],a[j]$ (from iteration
$i-1$): if $x_{i+1}=y_{j+1}$, we can now extend all our subsequences $y^{j}$
from the previous iteration by appending $x_{i}$ to them; hence
$a[j]+=a[j-1]$. Otherwise if $x_{i+1}\neq y_{j+1}$, we leave the value $a[j]$
unchanged in this iteration. The formal algorithm is below.

Algorithm 1 A standard algorithm to compute the number of times that $y$
appears as a subsequence of $x.$

Input: $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{m},n\geq m.$

$a\leftarrow$ Array of length $m.$

for $i\in\\{0,1,\dots,n-1\\}$ do

for $j\in\\{m-1,m-2,\dots,1\\}$ do

if $x_{i+1}=y_{j+1}$ then $a[j]\leftarrow a[j]+a[j-1]$

end if

end for

if $x_{i+1}=y_{1}$ then $a[0]\leftarrow a[0]+1$

end if

end for

return $a[m-1]$

######  Remark 4.1.

Note two subtleties. First, we treat the case of $j=0$ separately: $a[0]$
counts the number of times that the bit $y_{1}$ appears in $x$, so here a
match $x_{i+1}=y_{1}$ results in an increment of $a[0]$ by 1. Second, we are
iterating over $y$ backwards: this is so that our updates of $a[j]$ at a fixed
outer iteration $i$ don’t interfere with each other.

Using this algorithm to calculate $|\mathcal{D}(X,Y)|$ for several
independently-sampled $(X,Y)$ pairs, where $X\sim Unif\\{0,1\\}^{n}$ and
$Y=\operatorname{\mathrm{BDC}}_{d}(X),$ taking log, dividing by $n$, and
averaging, we can simulate the value of
$E_{n}=\frac{1}{n}\mathbb{E}\log|\mathcal{D}(X,Y)|$. By Lemma 2.3, our
simulated value of $E_{n}$ gives a simulation-based lower bound on
$E_{\infty}$, and after an upward shift by $\frac{1}{2n}\log(8\pi
e\max\\{d(1-d)n,1/6\\})$, we obtain a simulation-based upper bound. The
simulation-based lower and upper bounds of figures 1, 3 and 4 were obtained by
this method, all with $n=1,000$ and by averaging $1,000$ independent samples.

It’s natural to ask how accurate these simulation results should be expected
to be. A complete answer to this question would require a good understanding
of the concentration properties of the random variable
$\frac{1}{n}\log|\mathcal{D}(X,Y)|$, which seems like a very challenging
problem. Simulation results suggest that it concentrates very strongly (see
conjectures 5.1 and 5.2 in the next section). However, we note that
_something_ can be said just from the fact that
$\frac{1}{n}\log|\mathcal{D}(X,Y)|\in[0,1]$ almost surely. Namely, letting
$Z_{n}^{t}$ be the empirical average of $t$ independent samples equal in
distribution to $\frac{1}{n}\log|\mathcal{D}(X,Y)|,$ by Hoeffding’s inequality
we have

$\mathbb{P}(|Z_{n}^{t}-E_{n}|\geq\gamma)\leq 2e^{-2\gamma^{2}t}$

for any $\gamma>0.$ This implies, for instance, a $99\%$ confidence interval
around our simulated lower and upper bounds of width equal to $2\cdot 0.0514$,
since $2e^{-2(0.0514)^{2}1000}\approx 0.01$. However, this is of course very
weak, and in fact already implied by our upper bounds and the lower bounds of
[DG01, RD13, HOS16]. This confidence interval could be easily tightened by
running larger simulations, but we didn’t attempt to do this since the
empirically-observed concentration is so strong.

##  5 Conjectures and Open Problems

We conclude by collecting some conjectures and open problems with which we
hope to motivate further work. We begin with the concentration properties of
$\frac{1}{n}\log|\mathcal{D}(X,Y)|,$ which we already discussed in the last
section. An initial conjecture, which may not be so hard to prove, is the
following.

######  Conjecture 5.1 (Concentration conjecture, weak form.).

$\frac{1}{n}\log|\mathcal{D}(X,Y)|\to E_{\infty}$ almost surely.

The following strengthening implies Conjecture 5.1 by Lemma 2.3 and the Borel-
Cantelli lemma.

######  Conjecture 5.2 (Concentration conjecture, strong form.).

For any $\gamma>0,$ we have

$\mathbb{P}\left(\left|\frac{1}{n}\log|\mathcal{D}(X,Y)|-E_{n}\right|\geq\gamma\right)\leq
e^{-\Omega(n/\operatorname{\mathsf{poly}}(\log(n)))}.$

Finally, we turn to what we consider to be a fascinating question.

######  Question 5.3.

Determine the value $d^{*}_{\text{unif}}\in[\frac{1}{2},1]$ when
$C_{\text{unif}}$ first becomes equal to zero. Formally, determine

$d^{*}_{\text{unif}}:=\sup\\{d\in[0,1]:C_{\text{unif}}(d)>0\\}.$

Based on simulation results, we put forth the following.

######  Conjecture 5.4.

$d^{*}_{\text{unif}}=1.$

We remark that, as far as we know, the state of the art is that
$\frac{1}{2}\leq d^{*}_{\text{unif}}\leq 1,$ i.e., we don’t have a lower bound
that beats 1/2. Given the recent progress on the analogous question for the
case of the adversarial deletion channel capacity [GHL22], perhaps related
techniques could be applied here as well.

##  6 Acknowledgement

The second author is grateful to Amir Dembo, Mary Wootters, and Ray Li for
helpful discussions.

## References

  * [Sha48] C.. Shannon  “A mathematical theory of communication”  In _The Bell System Technical Journal_ , 1948
  * [Gal61] Robert G. Gallager  “SEQUENTIAL DECODING FOR BINARY CHANNELS WITH NOISE AND SYNCHRONIZATION ERRORS”, 1961
  * [Lev65] Vladimir I. Levenshtein  “Binary codes capable of correcting deletions, insertions, and reversals”  In _Soviet physics. Doklady_ 10, 1965, pp. 707–710
  * [Dob67] Roland L’vovich Dobrushin  “Shannon’s theorems for channels with synchronization errors”  In _Problemy Peredachi Informatsii_ , 1967
  * [SW73] D. Slepian and J. Wolf  “Noiseless coding of correlated information sources”  In _IEEE Transactions on Information Theory_ 19.4, 1973, pp. 471–480  DOI: 10.1109/TIT.1973.1055037
  * [Mas88] James L Massey  “On the entropy of integer-valued random variables”  In _Procs. of Int. Workshop on Information Theory, Beijing, China_ , 1988, pp. C1
  * [MK95] Shigeki MIYAKE and Fumio KANAYA  “Coding theorems on correlated general sources”  In _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ 78.9 The Institute of Electronics, InformationCommunication Engineers, 1995, pp. 1063–1070
  * [DG01] Suhas Diggavi and Matthias Grossglauser  “On Transmission Over Deletion Channels”  In _Proc. Annu. Allerton Conf. Commun. Control Comput_ , 2001
  * [Lot05] M. Lothaire  “Applied Combinatorics on Words (Encyclopedia of Mathematics and Its Applications)”  USA: Cambridge University Press, 2005
  * [CT06] Thomas M. Cover and Joy A. Thomas  “Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)”  USA: Wiley-Interscience, 2006
  * [MD06] M. Mitzenmacher and E. Drinea  “A Simple Lower Bound for the Capacity of the Deletion Channel”  In _IEEE Transactions on Information Theory_ , 2006
  * [DMP07] Suhas Diggavi, Michael Mitzenmacher and Henry D. Pfister  “Capacity Upper Bounds for the Deletion Channel”  In _2007 IEEE International Symposium on Information Theory_ , 2007, pp. 1716–1720  DOI: 10.1109/ISIT.2007.4557469
  * [DM07] Eleni Drinea and Michael Mitzenmacher  “Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels”  In _IEEE Transactions on Information Theory_ , 2007
  * [Mit09] Michael Mitzenmacher  “A survey of results for deletion channels and related synchronization channels”  In _Probability Surveys_ Institute of Mathematical StatisticsBernoulli Society, 2009, pp. 1–33
  * [FD10] Dario Fertonani and Tolga M. Duman  “Novel Bounds on the Capacity of the Binary Deletion Channel”  In _IEEE Trans. Inf. Theor._ 56.6 IEEE Press, 2010, pp. 2753–2765  DOI: 10.1109/TIT.2010.2046210
  * [KMS10] Adam Kalai, Michael Mitzenmacher and Madhu Sudan  “Tight asymptotic bounds for the deletion channel with small deletion probabilities”  In _2010 IEEE International Symposium on Information Theory_ , 2010, pp. 997–1001  DOI: 10.1109/ISIT.2010.5513746
  * [KM10] Yashodhan Kanoria and Andrea Montanari  “On the deletion channel with small deletion probability”  In _2010 IEEE International Symposium on Information Theory_ , 2010, pp. 1002–1006  DOI: 10.1109/ISIT.2010.5513745
  * [KD10] Adam Kirsch and Eleni Drinea  “Directly Lower Bounding the Information Capacity for Channels With I.I.D. Deletions and Duplications”  In _IEEE Transactions on Information Theory_ 56.1, 2010, pp. 86–102  DOI: 10.1109/TIT.2009.2034883
  * [Dal11] Marco Dalai  “A new bound on the capacity of the binary deletion channel with high deletion probabilities”  In _2011 IEEE International Symposium on Information Theory Proceedings_ , 2011
  * [MRT11] Nan Ma, Kannan Ramchandran and David Tse  “Efficient file synchronization: A distributed source coding approach”, 2011, pp. 583–587  DOI: 10.1109/ISIT.2011.6034196
  * [DSV12] Michael Drmota, Wojciech Szpankowski and Krishnamurthy Viswanathan  “Mutual information for a deletion channel”  In _2012 IEEE International Symposium on Information Theory Proceedings_ , 2012, pp. 2561–2565  DOI: 10.1109/ISIT.2012.6283980
  * [MRT12] Nan Ma, Kannan Ramchandran and David Tse  “A compression algorithm using mis-aligned side-information”  In _2012 IEEE International Symposium on Information Theory Proceedings_ , 2012, pp. 16–20  DOI: 10.1109/ISIT.2012.6283542
  * [Kog+13] H Koga  “Information-spectrum methods in information theory”  Springer Science & Business Media, 2013
  * [RD13] Mojtaba Rahmati and Tolga Duman  “Bounds on the Capacity of Random Insertion and Deletion-Additive Noise Channels”  In _Information Theory, IEEE Transactions on_ 59, 2013, pp. 5534–5546  DOI: 10.1109/TIT.2013.2262019
  * [RD15] Mojtaba Rahmati and Tolga M. Duman  “Upper Bounds on the Capacity of Deletion Channels Using Channel Fragmentation”  In _IEEE Transactions on Information Theory_ , 2015
  * [HOS16] Yanjun Han, Or Ordentlich and Ofer Shayevitz  “Mutual Information Bounds via Adjacency Events”  In _IEEE Transactions on Information Theory_ 62.11, 2016, pp. 6068–6080  DOI: 10.1109/TIT.2016.2609390
  * [Che19] Mahdi Cheraghchi  “Capacity Upper Bounds for Deletion-Type Channels”  In _J. ACM_ , 2019
  * [GHL22] Venkatesan Guruswami, Xiaoyu He and Ray Li  “The zero-rate threshold for adversarial bit-deletions is less than 1/2”  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 727–738  DOI: 10.1109/FOCS52979.2021.00076

##  Appendix A Omitted Proofs

######  Lemma A.1 (Lemma 3.9 in the main text).

The function $k\mapsto H(X|Y[k])$ is monotone-increasing.

###### Proof.

Take $0\leq i\leq j\leq n.$ We wish to prove that $H(X|Y[i])\leq H(X|Y[j]).$
Since $X\to Y[i]\to Y[j]$ forms a Markov chain, by the data processing
inequality we have $I(X;Y[i])\geq I(X;Y[j]).$ But since $H(X)=n,$ this implies
$H(X|Y[i])\leq H(X|Y[j]),$ as desired. ∎

######  Lemma A.2.

For $u\in\\{0,1,\dots,n\\}$ and $n\geq 1$, we have

$\frac{1}{n}\log\binom{n}{u}\geq h(u/n)-\frac{1}{2n}\log(\max\\{2\pi
u(n-u)/n,1\\})-\frac{\log e}{6n\max\\{\min\\{u,(n-u)\\},1\\}}.$

###### Proof.

The lemma follows from Stirling’s approximation

$m\log m-m\log e+\frac{1}{2}\log(2\pi m)+\frac{1}{12m+1}\log e\leq\log m!\leq
m\log m-m\log e+\frac{1}{2}\log(2\pi m)+\frac{1}{12m}\log e$

applied to each term in the expression $\log\binom{n}{u}=\log
n!-\log(u)!-\log(n-u)!,$ and the simple inequality

$\frac{1}{12n-1}-\frac{1}{12u}-\frac{1}{12(n-u)}\geq\frac{-1}{6n\min\\{u,n-u\\}}.$

We skip the details of the computation. The maxima with 1 are to fix the cases
where $u=0$ or $n.$ ∎


# Roles of positively charged dust, ion fluid temperature, and nonthermal
electrons in the formation of modified-ion-acoustic solitary and shock waves

R. K. Shikha111Corresponding author<EMAIL_ADDRESS>M. M. Orani, and
A. A. Mamun  Department of Physics & Wazed Mia Science Research Centre,
Jahangirnagar University, Savar, Dhaka-1342, Bangladesh

###### Abstract

The dusty plasma system (containing nonthermally distributed inertialess
electron species, warm inertial ion species, and positively charged stationary
dust species) is considered. The basic features of subsonic and supersonic
modified-ion-acoustic solitary and shock waves formed in such a dusty plasma
system have been investigated by the reductive perturbation method. It has
been shown that positively charged dust species plays a new role in favor of
the formation of subsonic solitary and shock waves. On the other hand, the ion
fluid temperature (represented by the parameter $\sigma$) and the electron
nonthermal parameter (represented by $\alpha$) play new significant roles in
against the formation of subsonic solitary and shock waves, and give rise to
the formation of the supersonic solitary and shock waves after their
($\sigma$’s and $\alpha$’s) certain values. It is also shown that after a
certain value of the nonthermal parameter $\alpha$, the subsonic as well as
supersonic solitary and shock waves are formed with negative potential. The
important applications of the results of this theoretical investigation in
space and laboratory dusty plasma systems are pinpointed.

###### pacs:

52.27.Lw; 52.35.Sb; 52.35.Tc

##  I Introduction

There has been a great deal of renewed interest in understanding the role of
positively charged dust (PCD) species in modifying the existing features as
well as in introducing new features of linear and nonlinear propagation of the
modified-ion-acoustic (MIA) waves propagating in space Havnes96 ; Gelinas98 ;
Mendis04 ; Dovner94 ; Cairns95 ; Horanyi96 ; Mamun04 ; Tsintikidis96 ;
Horanyi93 ; Markus99-NLCs  and laboratory Khrapak01 ; Fortov03 ; Davletov18
dusty plasma systems, where the PCD species coexists with the electron-ion
plasmas. The dust species in such systems are positively charged Fortov98  due
to (i) secondary emission of electrons from the dust grain surface by the
impact of high energetic plasma particles like electrons or ions Chow93 , (ii)
thermionic emission of electrons from the dust grain surface by the intense
radiative or thermal heating Rosenberg95 , (ii) photo-emission of electrons
from the dust grain surface by the interaction of high energy photons with the
dust grain surfaceRosenberg96 , etc.

The dispersion relation for the MIA waves in an electron-ion-PCD plasma system
(containing inertialess Maxwellian electron species, inertial cold ion
species, and stationary PCD species) is Mamun20 ; Mamun21

$\displaystyle\frac{\omega}{kC_{i}}=\frac{1}{\sqrt{1+\mu+k^{2}\lambda_{D}^{2}}},$
(1)

where $\omega$ ($k$) is the MIA wave angular frequency (propagation constant);
$C_{i}=(z_{i}k_{B}T_{e}/m_{i})^{1/2}$ is the MIA speed in which $k_{B}$ is the
Boltzmann constant, $T_{e}$ is the electron temperature, and $m_{i}$ is the
ion mass; $\lambda_{D}=(k_{B}T_{e}/4\pi z_{i}n_{i0}e^{2})^{1/2}$ is the MIA
wave-length scale in which $n_{i0}$ ($z_{i}$) is the number density (charge
state) of the ion species at equilibrium, and $e$ is the magnitude of an
electronic charge; $\mu=z_{d}n_{d0}/z_{i}n_{i0}$ with $n_{d0}$ ($z_{d}$) being
the number density (charge state) of the PCD species at equilibrium for which
$n_{e0}=z_{d}n_{d0}+z_{i}n_{i0}$. This means that $\mu=0$ corresponds to the
electron-ion plasma, and $\mu\rightarrow\infty$ corresponds to electron-dust
plasma Mamun04 ; Khrapak01 ; Fortov03 ; Davletov18 . Thus, $0<\mu<\infty$ is
valid for the electron-ion-PCD plasmas. The dispersion relation (1) for the
long-wavelength limit ($k\lambda_{D}\ll 1$) becomes

$\displaystyle\frac{\omega}{kC_{i}}\simeq\sqrt{\frac{1}{1+\mu}}.$ (2)

The dispersion relation (2) indicates that the phase speed of the MIA waves
decreases with the rise of the value of $\mu$ due to the reduction of the
space charge electric field by the presence of the PCD species.

Recently, due to this new linear feature of the MIA waves, the subsonic
solitary and shock waves exist in a dusty plasma system containing Maxwellian
electron, cold ion, and PCD species Mamun21 ; Mamun20 . However, as indicated
by (2) the reduction of the MIA wave phase speed due to the presence of the
PCD species can also make the MIA phase speed comparable with the ion thermal
speed $V_{Ti}=(k_{B}T_{i}/m_{i})^{1/2}$ (where $T_{i}$ is the ion fluid
temperature) so that the effect of the ion-thermal pressure cannot be
neglected. On the other hand, the electron species in many space environments
does not always follow the Maxwellian velocity distribution function. This
means that the dispersion relation (2), and the works Mamun21 ; Mamun20  are
valid only for two limiting cases: (i) cold ion ($T_{i}=0$) and (ii)
Maxwellian electron species.

To overcome these two limitations, we consider (i) warm ion fluid ($T_{i}\neq
0$) Mamun97  and (ii) nonthermal electron species following the Cairns
velocity distribution function in the form Cairns95

$f(v)=\frac{1+\alpha(v^{2}-2\phi)^{2}}{(1+3\alpha)\sqrt{2\pi}}\exp\left[-\frac{1}{2}(v^{2}-2\phi)\right],$
(3)

where $\phi$ is the MIA wave potential normalized by $k_{B}T_{e}/e$, $\alpha$
is a parameter determining the population of the fast (energetic) particles
present in the plasma system under consideration. We note that the
distribution function defined by (3) is identical to the Maxwellian electron
distribution function for $\alpha=0$. How this nonthermal parameter $\alpha$
modifies the Maxwell distribution curve of the electron species is shown in
figure 1.

Figure 1: How the different values of $\alpha$ [viz. $\alpha=0$ (solid curve),
$\alpha=0.2$ (dotted curve), and $\alpha=0.4$ (dashed curve)] deviate from the
curve corresponding to the Maxwellian distribution function to that
corresponding to the Cairns distribution function Cairns95 . We note that
$\phi=0.5$ is used.

The effects of the Cairns nonthermal electron distribution ($\alpha$) and the
ion fluid temperature ($\sigma=T_{i}/z_{i}T_{e}$) reduces the dispersion
relation (2) for the long wavelength MIA waves to

$\displaystyle\frac{\omega}{kC_{i}}=\sqrt{\sigma+\frac{1+3\alpha}{(1+\mu)(1-\alpha)}}.$
(4)

The dispersion relation (4) indicates that as $\alpha$ and $\sigma$ increase,
the phase speed of the MIA waves increases and decreases the ion Landau
damping Mamun11 . This is due to the enhancement of the space charge electric
field by the nonthermal electron species and by the thermal temperature of ion
species. The aim of this work is to investigate the combined effects of the
PCD species, Cairns nonthermal electron species, and ion fluid temperature on
the basic features of the MIA solitary (shock) waves in the electron-ion-PCD
plasma system by deriving the Korwege-de Vries (KDV) equaion Washimi66 ;
Deeba12  (Burgers equation Deeba12 ; Mamun09 ; Mamun19 ).

The manuscript is structured in the following manner. The governing equations
are provided in section II. The basic features of solitary (shock) waves, are
investigated by making use of the reductive perturbation method Washimi66 ;
Deeba12 ; Mamun09 ; Mamun19  in section III (IV). A brief discussion on our
theoretical work is presented in section V.

##  II Governing equations

We consider a plasma system containing nonthermally distributed inertialess
electron species [following the Cairns distribution function represented by
(3)], isothermal warm inertial ion species, and stationary PCD species. The
nonlinear dynamics of the MIA waves in this electron-ion-PCD plasma system is
governed by the normalized equations in the form

$\displaystyle\frac{\partial n_{i}}{\partial t}+\frac{\partial}{\partial
x}(n_{i}u_{i})=0,$ (5) $\displaystyle\frac{\partial u_{i}}{\partial
t}+u_{i}\frac{\partial u_{i}}{\partial x}=-\frac{\partial\phi}{\partial
x}-\frac{\sigma}{n_{i}}\frac{\partial n_{i}}{\partial
x}+\eta\frac{\partial^{2}u_{i}}{\partial x^{2}},$ (6)
$\displaystyle\frac{\partial^{2}\phi}{\partial x^{2}}=(1+\mu)n_{e}-n_{i}-\mu,$
(7)

where $n_{i}$ ($n_{e}$) is the ion (electron) number density normalized by
$n_{i0}$ ($n_{e0}$); $u_{i}$ is the ion fluid speed normalized by $C_{i}$; $x$
($t$) is the space (time) co-ordinate normalized by $\lambda_{D}$
($\omega_{pi}^{-1}$); $\eta$ is the ion fluid kinematic viscosity coefficient
Mamun20  normalized by $\omega_{pi}\lambda_{D}^{2}$.

The expression for $n_{e}$ is obtained by integrating the non-thermal Cairns
distribution function [defined by (3)] over the whole velocity space, i.e.

$\displaystyle
n_{e}=\int_{-\infty}^{\infty}f(v)dv=(1-\beta\phi+\beta\phi^{2})\exp(\phi),$
(8)

where $\beta=4\alpha/(1+3\alpha)$. It indicates for $\alpha=0$ that
$n_{e}=\exp(\phi)$ yielding the Maxwellian electron species.

##  III KDV Soltary Waves

To study the nature of the KDV solitary waves in the electron-ion-PCD plasma
system under consideration, we first stretch the independent variables $x$ and
$t$ as Washimi66 ; Deeba12

$\displaystyle\zeta=\epsilon^{\frac{1}{2}}(x-{\cal V}_{p}t),$ (9)
$\displaystyle\tau=\epsilon^{\frac{3}{2}}t,$ (10)

where $\epsilon$ is the small dimensionless expansion parameter, ${\cal
V}_{p}$ is the MIA wave phase speed normalized by $C_{i}$ indicating ${\cal
V}_{p}=\omega/kC_{i}$, and $\zeta$ ($\tau$) is normalized as $x$ ($t$) is. We
then expand the dependent variables $n_{i}$, $u_{i}$, and $\phi$ as Washimi66
; Deeba12

$\displaystyle n_{i}=1+\epsilon
n_{i}^{(1)}+\epsilon^{2}n_{i}^{(2)}+\cdot\cdot\cdot,$ (11) $\displaystyle
u_{i}=0+\epsilon u_{i}^{(1)}+\epsilon^{2}u_{i}^{(2)}+\cdot\cdot\cdot,$ (12)
$\displaystyle\phi=0+\epsilon\phi^{(1)}+\epsilon^{2}\phi^{(2)}+\cdot\cdot\cdot.$
(13)

We now develop the equations in various powers of $\epsilon$. To the lowest-
order approximation, we obtain

$\displaystyle n_{i}^{(1)}=\frac{1}{{\cal V}_{p}^{2}-\sigma}\phi^{(1)},$ (14)
$\displaystyle u_{i}^{(1)}=\frac{{\cal V}_{p}}{{\cal
V}_{p}^{2}-\sigma}\phi^{(1)},$ (15) $\displaystyle{\cal
V}_{p}=\sqrt{\sigma+\frac{1+3\alpha}{(1+\mu)(1-\alpha)}}.$ (16)

This is the linear dispersion for the MIA waves in the electron-ion-PCD plasma
system, and is identical to (4) since ${\cal V}_{p}=\omega/kC_{i}$. The
interpretation of (4) is verified graphically by displaying the figures 2 and
3 which show how ${\cal V}_{p}$ varies with $\mu$, $\alpha$, and $\sigma$.

Figure 2: The variation of $V_{p}$ with $\mu$ for different values of $\alpha$
[viz. $\alpha=0$ (solid curve), $\alpha=0.1$ (dotted curve), and $\alpha=0.2$
(dashed curve)] and $\sigma=0.1$. Figure 3: The variation of $V_{p}$ with
$\mu$ for different values of $\sigma$ [viz. $\sigma=0$ (solid curve),
$\sigma=0.1$ (dotted curve), and $\sigma=0.2$ (dashed curve) and $\alpha=0$.

To the next higher order approximation, we obtain

$\displaystyle\frac{\partial n_{i}^{(1)}}{\partial\tau}-{\cal
V}_{p}\frac{\partial n_{i}^{(2)}}{\partial\zeta}+\frac{\partial
u_{i}^{(2)}}{\partial\zeta}+\frac{\partial}{\partial\zeta}\left[n_{i}^{(1)}u_{i}^{(1)}\right]=0,$
(17) $\displaystyle\frac{\partial u_{i}^{(1)}}{\partial\tau}-{\cal
V}_{p}\frac{\partial u_{i}^{(2)}}{\partial\zeta}+\gamma
u_{i}^{(1)}\frac{\partial
u_{i}^{(1)}}{\partial\zeta}=-\frac{\partial\phi^{(2)}}{\partial\zeta}-\sigma\frac{\partial
n_{i}^{(2)}}{\partial\zeta},$ (18)
$\displaystyle\frac{\partial^{2}\phi^{(1)}}{\partial\zeta^{2}}=(1+\mu)(1-\beta)\phi^{(2)}+\frac{1}{2}(1+\mu)\left[{\phi^{(1)}}\right]^{2}-n_{i}^{(2)},~{}~{}$
(19)

where $\gamma=1+\sigma/{\cal V}_{p}^{2}$, which is obtained from (14) and
(15). We finally use (14)$-$(19) to obtain the KDV equation in the form

$\displaystyle\frac{\partial\phi^{(1)}}{\partial\tau}+{\cal
A}\phi^{(1)}\frac{\partial\phi^{(1)}}{\partial\zeta}+{\cal
B}\frac{\partial^{3}\phi^{(1)}}{\partial\zeta^{3}}=0,$ (20)

where ${\cal A}$ and ${\cal B}$ denote the nonlinear and dispersion
coefficients, which are, respectively, given by

$\displaystyle{\cal A}=\left[\frac{(3{\cal V}_{p}^{2}+\sigma)-(1+\mu)({\cal
V}_{p}^{2}-\sigma)^{3}}{2{\cal V}_{p}({\cal V}_{p}^{2}-\sigma)}\right],$ (21)
$\displaystyle{\cal B}=\frac{({\cal V}_{p}^{2}-\sigma)^{2}}{2{\cal V}_{p}}.$
(22)

Figure 4: ${\cal A}=0$ surface plot showing the parametric regimes for the
existence of the KDV solitary waves with $\phi>0$ (parametric space {$\mu$,
$\alpha$, $\sigma$} above ${\cal A}=0$) surface) and $\phi<0$ (parametric
space {$\mu$, $\alpha$, $\sigma$} below ${\cal A}=0$ surface).

The stationary solitary wave solution of the KDV equation (20) is derived by
considering a moving frame $\xi=\zeta-{\cal U}_{0}\tau$ (moving with a
constant speed ${\cal U}_{0}$), where $\xi$ is normalized as $\zeta$ is, and
${\cal U}_{0}$ is normalized by $C_{i}$. Now, imposing the appropriate
boundary conditions, viz. $\phi^{(1)}\rightarrow 0$,
$d\phi^{(1)}/d\zeta\rightarrow 0$, and $d^{2}\phi^{(1)}/d\zeta^{2}\rightarrow
0$ at $\xi\rightarrow\pm\infty$. These assumptions lead to the stationary
solitary wave solution of the KDV equation (20) in the form

$\displaystyle\phi^{(1)}=\phi_{m}^{(1)}{\rm
sech^{2}}\left(\frac{\xi}{\Delta}\right).$ (23)

where $\phi^{(1)}$ ($\Delta$) is the amplitude (width) of the MIA solitary
waves, and are written as

$\displaystyle\phi_{m}^{(1)}=\frac{3{\cal U}_{0}}{{\cal A}}~{}~{}{\rm
and}~{}~{}\Delta=\sqrt{\frac{4{\cal B}}{{\cal U}_{0}}},$ (24)

respectively. It is clear from (23)$-$(24) that the subsonic and supersonic
solitary waves (of amplitude $3{\cal U}_{0}/{\cal A}$ and width $\sqrt{4{\cal
B}/{\cal U}_{0}}$) exist with $\phi^{(1)}>0$ [$\phi^{(1)}<0$] for ${\cal A}>0$
[${\cal A}<0$] since ${\cal U}_{0}>0$ and ${\cal B}>0$ are always valid, and
that amplitude (width) of the MIA solitary waves increases (decreases)
directly with ${\cal U}_{0}$ ($\sqrt{{\cal U}_{0}}$). The parametric regimes
corresponding to ${\cal A}>0$ and ${\cal A}<0$ are shown by displaying the
${\cal A}=0$ surface plot in figure 4. To observe how the basic features
(polarity, amplitude, and width) of the MIA solitary waves are modified by the
number density of the stationary PCD species (represented by $\mu$), the ion
fluid temperature (represented by $\sigma$), and the nonthermal parameter
$\alpha$ (representing the population of the fast or energetic electrons), we
have graphically represented (23) for the different values of $\mu$, $\sigma$,
and $\alpha$. The results are displayed in figures 5$-$8.

Figure 5: The solitary potential profiles for ${\cal U}_{0}=0.1$,
$\sigma=0.1$, $\alpha=0.1$, $\mu=0.2$ (solid curve), $\mu=0.3$ (dotted curve),
and $\mu=0.4$ (dashed curve). Figure 6: The solitary potential profiles for
${\cal U}_{0}=0.1$, $\mu=0.3$, $\alpha=0.1$, $\sigma=0$ (solid curve),
$\sigma=0.2$ (dotted curve), and $\sigma=0.4$ (dashed curve). Figure 7: The
solitary potential profiles for ${\cal U}_{0}=0.1$, $\mu=0.3$, $\sigma=0.1$,
$\alpha=0.1$ (solid curve), $\alpha=0.125$ (dotted curve), and $\alpha=0.15$
(dashed curve). Figure 8: The solitary potential profiles for ${\cal
U}_{0}=0.1$, $\mu=0.3$, $\sigma=0.1$, $\alpha=0.3$ (solid curve),
$\alpha=0.35$ (dotted curve), and $\alpha=0.4$ (dashed curve).

##  IV Burgers Shock Waves

To study Burgers shock waves in the dissipative electron-ion-PCD plasma system
under consideration, we first stretch the independent variables $x$ and $t$ as
Deeba12 ; Mamun09 ; Mamun19

$\displaystyle\zeta=\epsilon(x-{\cal V}_{p}t),$ (25)
$\displaystyle\tau=\epsilon^{2}t.$ (26)

We then expand the dependent variables $n_{i}$, $u_{i}$, and $\phi$ by (11),
(12), and (13), respectively. We again develop the equations in various powers
of $\epsilon$. To the lowest-order approximation, we obtain a linear set of
equations, which are given by (14)$-$(16).

To the next higher order approximation, we obtain

$\displaystyle\frac{\partial n_{i}^{(1)}}{\partial\tau}-{\cal
V}_{p}\frac{\partial n_{i}^{(2)}}{\partial\zeta}+\frac{\partial
u_{i}^{(2)}}{\partial\zeta}+\frac{\partial}{\partial\zeta}\left[n_{i}^{(1)}u_{i}^{(1)}\right]=0,$
(27) $\displaystyle\frac{\partial u_{i}^{(1)}}{\partial\tau}-{\cal
V}_{p}\frac{\partial u_{i}^{(2)}}{\partial\zeta}+u_{i}^{(1)}\frac{\partial
u_{i}^{(1)}}{\partial\zeta}=-\frac{\partial\phi^{(2)}}{\partial\zeta}-\sigma\frac{\partial
n_{i}^{(2)}}{\partial\zeta}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sigma
n_{i}^{(1)}\frac{\partial
n_{i}^{(1)}}{\partial\zeta}+\eta\frac{\partial^{2}u_{i}^{(1)}}{\partial\zeta^{2}},$
(28) $\displaystyle
0=(1+\mu)(1-\beta)\phi^{(2)}+\frac{1}{2}(1+\mu)\left[{\phi^{(1)}}\right]^{2}-n_{i}^{(2)}.$
(29)

We finally use (14)$-$(16) and (27)$-$(29) to obtain the Burgers equation in
the form

$\displaystyle\frac{\partial\phi^{(1)}}{\partial\tau}+{\cal
A}\phi^{(1)}\frac{\partial\phi^{(1)}}{\partial\zeta}={\cal
C}\frac{\partial^{2}\phi^{(1)}}{\partial\zeta^{2}},$ (30)

where ${\cal A}$ (${\cal C}$) is the coefficient of nonlinearity
(dissipation). The nonlinear coefficient ${\cal A}$ is by (21), and the
dissipative coefficient ${\cal C}$ is given by ${\cal C}=\eta/2$.

Figure 9: The shock potential profiles for ${\cal U}_{0}=0.1$, $\sigma=0.1$,
$\alpha=0.1$, $\eta=0.1$, $\mu=0.2$ (solid curve), $\mu=0.3$ (dotted curve),
and $\mu=0.4$ (dashed curve). Figure 10: The shock potential profiles for
${\cal U}_{0}=0.1$, $\mu=0.3$, $\alpha=0.1$, $\eta=0.1$, $\sigma=0.1$ (solid
curve), $\sigma=0.2$ (dotted curve), and $\sigma=0.3$ (dashed curve). Figure
11: The shock potential profiles for ${\cal U}_{0}=0.1$, $\mu=0.3$,
$\sigma=0.1$, $\eta=0.1$, $\alpha=0.1$ (solid curve), $\alpha=0.125$ (dotted
curve), and $\alpha=0.15$ (dashed curve). Figure 12: The shock potential
profiles for ${\cal U}_{0}=0.1$, $\mu=0.3$, $\sigma=0.1$, $\eta=0.1$,
$\alpha=0.3$ (solid curve), $\alpha=0.35$ (dotted curve), and $\alpha=0.4$
(dashed curve).

To obtain the stationary shock wave solution of the Burgers equation (30), we
again consider a moving frame moving with the speed ${\cal U}_{0}$, i.e.
$\xi=\zeta-{\cal U}_{0}\tau$, and impose the appropriate boundary conditions
($\phi^{(1)}\rightarrow 0$ and $d\phi^{(1)}/d\xi\rightarrow 0$ at
$\xi\rightarrow\infty$). These assumptions lead to the stationary shock wave
solution of the Burgers equation (30) in the form

$\displaystyle\phi^{(1)}=\phi^{(1)}_{m}\Big{[}1-\tanh\bigg{(}\frac{\xi}{\Delta}\bigg{)}\Big{]},$
(31)

where $\phi^{(1)}_{m}$ is the amplitude and $\Delta$ is the width of the shock
waves, are given by

$\displaystyle\phi^{(1)}_{m}=\frac{{\cal U}_{0}}{\cal A},~{}~{}{\rm
and}~{}~{}\Delta=\frac{\eta}{{\cal U}_{0}}.$ (32)

It is obvious from (31) and (32) with figures 2-4 that the subsonic and
supersonic shock waves are formed with $\phi>0$ ($\phi<0$) for ${\cal A}>0$
(${\cal A}<0$). It also clear that the width of the shock waves is directly
(inversely) proportional to $\eta$ (${\cal U}_{0}$). However, to observe how
the basic features (polarity, amplitude, and width) of the shock waves are
modified by the number density of the stationary PCD species (represented by
the parameter $\mu$), the ion fluid temperature (represented by the parameter
$\sigma$), and the nonthermal parameter $\alpha$ (representing the population
of the fast or energetic electrons), we have graphically represented (31) for
the different values of $\mu$, $\sigma$, and $\alpha$. The results are
displayed in figures 9$-$12.

##  V Discussion

The dusty plasma system (containing inertialess nonthermal electron, warm
inertial ion, and stationary PCD species) is considered. The roles of the
stationary PCD species, ion fluid temperature, and nonthermal electrons in the
linear and nonlinear propagation of the long (compared to $\lambda_{D}$)
wavelength MIA waves in such a plasma system are identified. They can be
pointed as follows:

  * •

The phase speed of the long wavelength MIA waves decreases with the rise of
the number density and charge of the stationary PCD species. This is due to
the reduction of the space charge electric field (caused by the PCD species)
in the electric field of the MIA waves in which inertia is provided by the
positive ion fluid.

  * •

The phase speed of the long wavelength MIA waves increases with the increase
in the ion fluid temperature as well as in the fraction of the energetic
electrons. This is due to the enhancement of the space charge electric field
(caused by the more flexibility of the ion fluid and by the excess energy of
the energetic/fast particles) in the electric field of the MIA waves in which
restoring force comes from the electron species.

  * •

The possibility for the formation of the subsonic solitary and shock waves
increases with the rise of the number density and charge of the stationary PCD
species, since the latter reduces the phase speed to its values of the
subsonic range. But, this possibility decreases with the rise of the ion fluid
temperature and with the rise of the fraction of the fast/energetic electrons
since the latter enhance the phase speed to the supersonic range.

  * •

The possibility for the formation of the subsonic solitary and shock waves
with negative potential increases with the rise of the fraction of the
fast/energetic electrons. But this possibility decreases with the rise of the
number density and charge of the stationary PCD species as well as with the
rise of the ion fluid temperature.

  * •

The amplitude of the solitary and shock waves decreases with rise of the
values of number density and charge of the PCD species and with the ion fluid
temperature, but increases with the increase in the faction of the
fast/energetic electrons. The amplitude of the solitary waves is three times
larger than that of the shock waves, but the nature of the variation of the
shock and solitary wave amplitude are identical since the nonlinear
coefficient in KDV and Burgers equations are identical.

  * •

The width of the solitary waves increases with rise of the values of the
number density and charge of the PCD species and with the ion fluid
temperature, but decreases with the increase in the fraction of the
fast/energetic electrons.

It is important to mention that to derive KDV equation, we use the stretched
or rescaled co-ordinates Washimi66 , which is valid only when the effect of
dissipation is negligible in comparison with that of the dispersion, and that
to derive Burgers equation, we use the stretched or rescaled co-ordinates
Mamun09 , which is valid only when the effect of dispersion is negligible in
comparison with that of the dissipation. We have used the reductive
perturbation method with these KDV Washimi66  and Burgers Mamun09  stretching
to derive the KDV and Burgers equations, respectively.

The limitation of the reductive perturbation method is that it is not valid
for the arbitrary amplitude solitary and shock waves. To overcome this
limitation, one has to develop a numerical code to simulate the basic
equations (5)$-$(7). This type of numerical simulation will be able to show
the time evolution of arbitrary amplitude solitary and shock waves. This is,
of course, a challenging research problem, but beyond the scope of our present
work. However, the results of our present work should be useful in
understanding the ion-acoustic disturbances in different space (viz. Earth’s
mesosphere Havnes96 ; Gelinas98 ; Mendis04 , upper part of ionosphere Dovner94
; Cairns95 , cometary tails Horanyi96 ; Mamun04 , Jupiter’s surroundings
Tsintikidis96 , Jupiter’s magnetosphere Horanyi93 , noctilucent clouds
Markus99-NLCs , etc.) and laboratory Khrapak01 ; Fortov03 ; Davletov18  dusty
plasma systems, where the PCD species coexists with the electron-ion plasmas.

Barkan et al. Barkan96  have performed a laboratory experiment on the
propagation of the MIA waves in plasma system containing electron, ion, and
negatively charged dust (NCD) species, and have shown that the presence of NCD
species enhances the phase speed of the MIA waves. This experimental setup of
Barkan et al. Barkan96  is expected to verify our result that the presence of
the PCD species reduces the phase speed of the MIA waves by using PCD species
instead of NCD species. On the other hand, Nakamura et al. Nakamura01 ;
Nakamura99  have performed two laboratory experiments on the formation of
solitary Nakamura01  and shock Nakamura99  waves in electron-ion-NCD plasmas.
The basic features of the solitary and shock waves predicted in our present
investigation can be tested by the experimental setup of Nakamura et al.
Nakamura01 ; Nakamura99  by replacing the NCD species by the PCD species.

## References

  * (1) O. Havnes, J. Trøim, T. Blix, W. Mortensen, L. I. Næsheim, E. Thrane, and T. Tønnesen, J. Geophys. Res. 101, 10839 (1996).
  * (2) L. J. Gelinas, K. A. Lynch, M. C. Kelley, S. Collins, S. Baker, Q. Zhou, and J. S. Friedman, Geophys. Res. Lett. 25, 4047 (1998).
  * (3) D. A. Mendis, Wai-Ho Wong, and M. Rosenberg, Phys. Scripta T113, 141 (2004).
  * (4) P. O. Dovner, A. I. Eriksson and Boström, Geophys. Res. lett. 21, 1827 (1994).
  * (5) R. A. Cairns, A. A. Mamun, R. Bingham, R. Boström, R. O. Dendy, C. M. C. Nairn, and P. K. Shukla, Geophys. Res. Lett. 22, 2709 (1995).
  * (6) M. Horányi, Annu. Rev. Astron. Astrophys. 34, 383 (1996).
  * (7) A. A. Mamun and P. K. Shukla, Geophys. Res. Lett. 31, L06808 (2004).
  * (8) D. Tsintikidis, D. A. Gurnett, W. S. Kurth, and L. J. Granroth, Geophys. Res. Lett. 23, 997 (1996).
  * (9) M. Horányi, G. E. Morfill, and E. Grün, Nature London 363, 144 (1993).
  * (10) M. Rapp and F. J. Lübken, Earth. Planet. Sp. 51, 799 (1999).
  * (11) S. A. Khrapak and G. Morfill, Phys. Plasmas 8, 2629 (2001).
  * (12) V. E. Fortov, A. P. Nefedov, O. S. Vaulina, O. F. Petrov, I. E. Dranzhevski, A. M. Lipaev, and Y. P. Semenov, New J. Physics 5, 102 (2003).
  * (13) A. E. Davletov, F. Kurbanov, and Y. S. Mukhametkarimov, Phys. Plasmas 25, 120701 (2018).
  * (14) V. E. Fortov, A. P. Nefedov, O. S. Vaulina, A. M. Lipaev, V. I. Molotkov, A. A. Samaryan et al., J. Exp. Theor. Phys. 87, 1087 (1998).
  * (15) V. W. Chow, D. A. Mendis, and M. Rosenberg, J. Geophys. Res. 98, 19065 (1993).
  * (16) M. Rosenberg and D. A. Mendis, IEEE Trans. Plasma Sci. 23, 117 (1995).
  * (17) M. Rosenberg, D. A. Mendis, and D. P. Sheehan, IEEE Trans. Plasma Sci. 24, 1422 (1996).
  * (18) A. A. Mamun, Contrib. Plasma Phys. 61, e202000192 (2021).
  * (19) A. A. Mamun and B. E. Sharmin, AIP Advances 10, 125317 (2020).
  * (20) A. A. Mamun, Phys. Rev. E 55 (2) (1997).
  * (21) A. A. Mamun and P. K. Shukla, J. Plasma Phys. 77, 437 (2021).
  * (22) H. Washimi and T. Taniuti, Phys. Rev. Lett. 17, 996 (1996).
  * (23) F. Deeba, S. Tasnim, and A. A. Mamun, IEEE Trans. Plasma Sci. 40, 2247 (2012).
  * (24) A. A. Mamun and R. A. Cairns, Phys. Rev. E 79, R055401 (2009).
  * (25) A. A. Mamun, Phys. Plasmas 26, 084501 (2019).
  * (26) A. Barkan, N. D’Angelo, and R. L. Merlino, Planet. Space Sci. 44, 239 (1996).
  * (27) Y. Nakamura and A. Sharma, Phys. Plasmas 8, 3921 (2001).
  * (28) Y. Nakamura, H. Bailung, and P. K. Shukla, Phys. Rev. Lett. 83, 1602 (1999).