—This paper considers the transmission of a packet through a binary deletion channel with an unknown and arbitrar- ily high deletion probability. The deletion positions are unknown to both sender and receiver, and the number of bits received before channel closure is unknown to both sender and receiver. The number of received bits is in the range 1-100. This paper argues that, for such a channel, an encoding method that enables the calculation of probability masses for all possible packets is preferred to one which attempts perfect reconstruction of the transmitted packet. It then presents and analyzes such an encoding method. The presented method encodes information on the probability of receiving a 1 vs. a 0, rather than in the 1’s and 0’s themselves. The receiver decodes the information using Bayesian inference. Rather than transmitting the packet of interest, the encoding method transmits information about the packet of interest in order to guarantee information transfer for any nonzero number of bits received. This paper analyzes the statistics of convergence of this estimator for all numbers of received bits from 0 to 100. Index Terms —deletion channel, probabilistic transmission, spacecraft, starshot, estimation, encoding. I. I NTRODUCTION THIS paper presents and analyzes a method for proba- bilistically encoding a packet for transmission through a binary deletion channel with an arbitrarily high deletion prob- ability and unknown channel lifetime. The deletion channel takes an input sequence of Nbits,Xi. The value of N(the number of bits that the sender transmits before the channel closes) is unknown to both the sender and receiver and is assumed to be small ( <100bits). Each bit can be deleted with a probability p, which is unknown and may be arbitrarily close to 1. Neither the sender nor the receiver know the positions of the deleted bits. The output sequence, Yi, is the sequence of theXiwhich were not deleted, in the correct order and with no errors. The length of Yiis assumed to be at least 1 bit and less or equal toNbits with an expected length of N(1p). The transmission is not decoded to a single packet, but instead to a probability density function that assigns a probability density to every possible packet. Neither the sender nor the receiver know when the channel will close or which bits have been deleted. For that reason, each bit should include information about the entire packet that the sender is attempting to send through the channel. Other- wise there will be some minimum number of bits required for the receiver to recover any useful information about the packet. Lecturer of Mechanical and Aerospace Engineering, Cornell UniversityThis paper presents a method for encoding information about the entire packet in each bit. Using the proposed encoding, any number of bits recovered by the receiver (no matter how few) improves the receiver’s knowledge of the entire transmitted packet. This paper proposes to encode information in the following way. The sender and receiver both assume a ﬁxed, known packet length. The packet to be transmitted is interpreted as an integer. The ratio between this integer and the largest integer storable in the packet length is interpreted as a probability, x. The sender uses xto decide whether to transmit a binary 1 or 0. Each received bit is modeled as an independent and identically distributed Bernoulli random trial. The bit is 1 with probability xand 0 with probability (1x). The probability density function for xis calculated by the receiver via Bayesian inference. By encoding information in this way, every bit adds to the receiver’s knowledge of the transmitted information. Each subsequent bit improves the estimate for x, thereby tightening the probability density function for possible transmissions around fewer packets. The statistics of convergence are dis- cussed at length in this paper. Thus, even for a channel which may prevent reconstruction of the particular packet which the sender transmitted, the proposed encoding scheme allows the receiver to assign probability masses to each of every possible packet. The scope of application for this encoding method is limited to channels with the properties enumerated below. These are deletion channels with properties that do not guarantee the intact receipt of any packet larger than one bit, and that do not guarantee the receipt of enough bits to perfectly reconstruct packets longer than 1 bit from partial packets. For such channels, perfect reconstruction of a transmitted packet is sacriﬁced in lieu of probability masses over all possible packets in order to guarantee information transfer through the channel. Channel properties 1) The channel is a binary deletion channel. 2) The channel has unknown and arbitrary high deletion probability, p. 3) Deletion positions unkown to both sender and receiver. 4) The number of bits received before channel closure, n, is unknown to both sender and receiver and assumed greater than or equal to one bit and less than or equal to 100 bits. V . HUNTER ADAMS 2 Fig. 1. Probability density function for the value of the transmitted packet based on a number of received bits that varies from 0 (black) to 100 (red). Figure represents a particular instantiation of a random process. II. M OTIVATION The channel described in the introduction models the chan- nel which can likely be expected for the Breakthrough Starshot Project, which proposes to send a number gram-scale space- craft to the star Proxima Centauri — 4.22 light years from Earth. The spacecraft will use lasers to transmit information to the Earth. Photons from the lasers will be collected in telescopes on Earth and decoded into a bit string [1]. At these distances, tremendous amounts of data will be required in order to resolve even a single bit from background noise, and many bits will be deleted from the channel. Every recovered bit has far greater value than in conventional communications channels. The channel to each of the spacecraft is fragile and could be severed at any time, and many of the bits that the spacecraft send will not be recoverable by the receiver. The encoding method proposed in this paper is intended to maximize the scientiﬁc impact of every received bit. This paper proposes that the spacecraft used for the Break- through Starshot Project should not attempt to transmit a packet of information as a string of ones and zeros. If only a handful of bits are recovered from the deletion channel, there may be no recoverable information about the original packet. Instead, this paper proposes to encode the packet information in the probability of transmitting a 1 vs. a 0, as described in Section III. In doing so, any bit recovered from the channel adds information about the original transmitted packet. The packet is recovered with increasing certainty (the precise statistics of which are discussed in a Section VI) as more bits are recovered from the channel. The objective should not be to maximize data rate, but instead to guarantee information transfer. III. R ELATED WORK Binary deletion codes were introduced as a concept for study by Levenshtein in 1966 [2]. Since then, much of the research associated with deletion channels has been toward bounding the channel capacity, the precise calculation of whichremains an unsolved problem. Diggavi et al present the ﬁrst non-trivial upper bound for the capacity of a probabilistic deletion channel in [3]. In [4], Fertonani and Duman use the upper bound from [3] as a benchmark, and calculate a new state-of-the-art for the upper-bound channel capacity for most deletion probabilities. To my knowledge, theirs is the lowest bound for the upper limit of the channel capacity. Similar efforts have been made in calculating the lower bound, with the current state-of-the-art calculated by Drinea and Mitzenmacher in [5]. This paper does not attempt to bound the capacity of the deletion channel of interest, but instead presents an encoding strategy for guaranteeing communication of information through that channel. There has been related research on encoding strategies for deletion channels. In [6], Kanoria and Montanari develop an optimal code for a binary deletion channel with a small deletion probability. They do so by beginning with a channel with a deletion probability of zero, and assuming that a channel with a small deletion probability has a capacity that varies smoothly with the deletion probability. They compute the capacity as a series expansion over small deletion probability and ﬁnd an input distribution that achieves capacity up the the ﬁrst three terms in this expansion. The work in this paper departs from theirs in that the deletion probability may be arbitrarily large. It departs from the body of work surrounding deletion channels in other ways too. This work departs from existing work in that the objective is not to maximize data rate through a permanent channel. Instead, the objective to guarantee the communication of information about a packet of interest through a channel with an unknown and arbitrarily high deletion probability, unknown lifetime, and through which an unknown and small (1-100) number of bits can be recovered. For such a channel, intact receipt of the packet of interest cannot be guaranteed before the channel closes. Furthermore, a sufﬁcient number of partial packets for reconstructing the packet of interest cannot be guaranteed before the channel closes. This calls for an encoding method that enables the assignment of probability V . HUNTER ADAMS 3 masses to all possible packets rather than one which attempts perfect reconstruction of the packet. IV. E NCODING The sender interprets the packet to be transmitted as an integer. The length of the packet is ﬁxed and known by both the sender and receiver. The sender ﬁnds the ratio, x, between the packet integer value, v, and the maximum integer value that can be contained in a number of bits equal to the packet length, M.Mis 256 for 8-bit packets, for example. This calculation is shown in eqn. 1. x=v M(1) The sender interprets this ratio, which will be in the range [0,1], as a probability. Before transmitting each bit, a uniform random number generator onboard the sender generates a number in the range [0,1]. If the number is less than x, then the sender transmits a 1. If the number is greater than x, the sender transmits a 0. The receiver gathers these bits and uses Bayesian inference to assign a probability density to each of every possible packet value, v. V. D ECODING The transmission is not decoded to a single packet, but in- stead to a probability density function that assigns a probability density to every possible packet value. This is accomplished through a straightforward application of Bayes’ Rule, shown in eqn. 2. In eqn. 2, p(kjx)is the probability of receiving k ones conditioned on the probability of sending a 1. p(x)is the prior distribution on x, the probability of receiving a 1 (which may or may not be uniform, depending on the application). p(k)is the marginal probability of receiving k1’s. p(xjk) =p(kjx)p(x) p(k)(2) The receiver sporadically receives bits (1 or 0). Each bit has probabilityxof being 1 and probability (1x)of being 0. Thus, each received bit is a Bernoulli random trial. A sequence of such bits is a Bernoulli process with the probability mass function given by the binomial distribution shown in eqn. 3. The binomial distribution, with parameters, nandk, is the discrete probability distribution of the number of successes (1’s) in a sequence of nexperiments (received bits). This distribution, in other words, yields the probability of k1’s received in ntotal bits, conditioned on the probability of receiving a 1. This is the ﬁrst term in the numerator of Bayes’ Rule (eqn. 2). p(kjx) =n! k!(nk)!xk(1x)nk(3) One might choose any one of a number of distributions to represent the prior distribution on x,p(x). However, the beta distribution is the conjugate prior for the binomial distribution. Thus, by choosing to describe p(x)with a beta distribution, we know that p(xjk), the posterior distribution, will also be a beta function. and in eqn. 4 are hyper parameters thataffect the shape of the distribution. When = = 1, the beta distribution reduces to a uniform distribution (all packets equally likely). Other choices of and place more weight on various values for x. p(x) =( + ) ( )( )x 1(1x) 1(4) The marginal probability for receiving k1’s is calculable using the chain rule and the known solution to an Euler integral, as shown in eqn. 5. p(k) =Z kp(kjx)p(x)dx =n! k!(nk)!( + ) ( )( )(k+ )(nk+ ) (n+ + )(5) Eqns. 3-5 constitute all of the terms in Bayes’ Rule (eqn. 2). Substituting and solving yields eqn. 6. This equation represents the probability for each possible value for xgivenk(the number of 1’s received) and n(the total number of bits received). p(xjk) =p(kjx)p(x) p(k) =n! k!(nk)!xk(1x)nk( + ) ( )( )x 1(1x) 1 n! k!(nk)!( + ) ( )( )(k+ )(nk+ ) (n+ + ) =(n+ + ) (k+ )(nk+ )xk+ 1(1x)nk+ 1(6) The probability density function shown in eqn. 6 is renormal- ized such that the random variable is not the probability, x, but instead the range of all possible packet values. This is accomplished by a change of variables. v, the value of the transmitted packet, is a function of the random variable X, as shown in eqn. 7. V=MX (7) Min eqn. 7 is the maximum integer that can be stored in the packet length. A change of variables for eqn. 6 yields eqn. 8, the probability density function for all possible transmitted packets, given the number of received 1’s ( k) and the total number of received bits ( n). The probability that the trans- mitted packet is within a particular range of possible values is calculated by integrating this probability density function over that range of values. p(vjk) =(n+ + ) (k+ )(nk+ )v Mk+ 1   1v Mnk+ 1 1 M (8) VI. C ASE STUDY Consider the concrete example of a sender equipped with an 8-bit analog-to-digital converter (ADC). The sender must transmit an 8-bit unsigned measurement, v, from the ADC through the deletion channel. It does so by ﬁrst calculating x, as shown in eqn. 9. In the case of an 8-bit packet, M= 256 . x=v M=v 256(9) V . HUNTER ADAMS 4 Fig. 2. All a posteriori distributions for 100 transmissions of the same packet with 0 bits received, 10 bits received, 50 bits received, and 100 bits received A random number generator on the sender then generates uniformly distributed random numbers in the range [0,1]. In the case that a randomly generated number is less than x, the sender transmits a 1. In the case that the randomly generated number is greater than x, the sender transmits a 0. Each of these bits may be deleted by the channel with an unknown (and arbitrarily high) deletion probability p. The positions of these deletions are unknown to both the sender and the receiver. After sending Nbits (Nalso unknown to the receiver, and unknown a priori to the sender), the channel closes. The receiver recovers n(1nN)bits,kof which are 1’s. The receiver then uses eqn. 8 to determine the probability density for each possible packet, v, that may have been transmitted given the number of received 1’s, k, and the total number of received packets, n. We will assume that all packets are equally likely, and therefore assign hyperparameters and both value 1. Fig. 1 shows a particular instantiation of this random process as a concrete example. In the particular instantiation shown in Fig. 1, the maximum of the a posteriori distribution is near to the true value of the transmitted packet. However, the a posteriori distribution has nonzero probability density for all possible values for the transmitted packet. It is possible, therefore, for the maximum of the a posteriori distribution (which is the same as the maximum likelihood estimate in the case of a uniform prior) to be far from the true value, though this becomes increasingly rare as the number of received bits increases. This is illustrated in Fig. 2, which shows all of the a posteriori distributions for 100 transmissions of the same packet with 0 bits received, 10 bits received, 50 bits received, and 100 bits received. Fig. 2 shows that the maximum of thea posteriori distribution tends toward the true value as the number of bits increases, and that the variance of the distribution decreases. The statistics of this convergence are discussed in Section vII. VII. T HE STATISTICS OF CONVERGENCE Fig. 2 suggests that, as more bits are received, the expected value of the a posteriori distribution converges to the truetransmitted packet value (i.e. the estimator is consistent) and the variance decreases. This section proves those two observations and quantiﬁes the rate of convergence. Section VII.A ﬁnds the expected value of the a posteriori distribution as a function of k, , , andM. Section VII.B calculates the upper limit for the expected error between the expected value for the a posteriori distribution and the true transmitted packet value, and shows that this error goes to zero as napproaches inﬁnity. Section VII.C calculates the maximum and minimum variance of the a posteriori distribution for a uniform prior distribution. A. Expected a posteriori estimate The expected value for the a posteriori distribution is calculated in eqn. 10. ^vEAP =Z vvp(vjk)dv =ZM 0v(n+ + ) (k+ )(nk+ )v Mk+ 1   1v Mnk+ 1 1 M dv =Z1 0xM(n+ + ) (k+ )(nk+ )xk+ 1 (1x)nk+ 11 M Mdx =Mk+ n+ + (10) B. Upper bound on expected error of the expected a posteriori estimate The error between the expected value for the a posteriori distribution and the true transmitted packet value, ~vis calcu- lated in eqn. 11. ~v=v^vEAP =vMk+ n+ + (11) V . HUNTER ADAMS 5 Fig. 3. Range of possible variances for a posteriori distribution as a function of number of received bits, assuming an 8-bit packet. This error is a random variable, for which the expected value is calculated in eqn. 12. From eqn. 12, it can be seen that the expected value for the error goes to zero as napproaches inﬁnity. Thus, the estimator is consistent. E[~v] =E vMk+ n+ +  =vM n+ + (E[k] + ) =vM n+ + (xn+ ) =vM n+ + v Mn+  =v( + )M n+ + (12) Eqn. 13 is the particular form that eqn. 12 assumes under the assumption of a uniform prior distribution for v. E[~v] =2vM n+ 2(13) For a uniform prior distribution ( = = 1) and ﬁxed n, the expected error is maximized when vis at the limits of its range (0 or M). In the case of a uniform prior, an upper limit for the expected error can be found by setting v=M, as shown in eqn. 14. jE[~v]jM n+ 2(14) The upper bound for the expected value of the error goes to 0 asnapproaches inﬁnity (the estimator is consistent), and is less than 1 (the smallest value separating valid packets) when n > (M2). This does not guarantee that the expected a posteriori estimate for the packet value will be within 1 of the true value when n>(M2). The posterior distribution has variance about the expected value.C. Variance of the a posteriori distribution The variance for the a posteriori distribution is calculated as shown in eqn. 15. Var[v] =E v2 E[v]2 =E v2 ^v2 EAP (15) The second term in eqn. 15, ^vEAP is calculated in eqn. 12. The ﬁrst term, E[v2], is calculated in eqn. 16. E v2 =Z vv2p(vjk)dv =ZM 0v2(n+ + ) (k+ )(nk+ )v Mk+ 1   1v Mnk+ 1 1 M dv =M2 (k+ + 1)(k+ ) ( +n+ + 1)( +n+ )(16) The variance for vcan be calculated by substituting eqn. 12 and eqn. 16 into eqn. 15, as shown in eqn. 17. Var[v] = M2 (k+ + 1)(k+ ) ( +n+ + 1)( +n+ )  Mk+ n+ + 2 =M2(k+ )(nk+ )] ( +n+ + 1)( +n+ )2 (17) In the case of a uniform prior distribution for v(all packets equally likely), then = = 1 and eqn. 17 reduces to eqn. 18. Var[v] =M2(k+ 1)(nk+ 1)] (n+ 3)(n+ 2)2 (18) For a given n, this variance is maximized when k=n 2and minimized when k= 0 ork=n. Fig 3 shows the range of possible variances of the posterior distribution with increasing number of received bits, n, and in the particular case of an 8-bit packet. V . HUNTER ADAMS 6 Fig. 4. Upper bound on the number possible packet values contained within the 95 percent conﬁdence interval of the posterior distribution which maximizes variance for the particular case of an 8-bit packet (256 possible packets). VIII. B OUNDING THE CONFIDENCE INTERVAL OF THE POSTERIOR DISTRIBUTION FOR UNIFORM PRIOR DISTRIBUTION The posterior distribution, shown in eqn. 8, is a beta distribution that can be rewritten as shown in eqn. 19. From eqn. 8, it can be seen that the effective and values for the posterior distribution (denoted eand ein eqn. 19) are given by the expressions in eqn. 20-21. p(vjk) =( e+ e) ( e)( e)v M e1   1v M e1 1 M (19) The variance of this beta distribution is shown in eqn. 18. From eqn. 18, it can be seen that the variance is maximized whenk=n 2. e=k+ (20) e=nk+ (21) Under the assumption of a uniform prior distribution, = = 1. Substituting k=n 2yields the effective eand eshown in eqn. 22-23. e=n 2+ 1 (22) e=n 2+ 1 (23) When the and values for a beta distribution are equal, they are increasingly well approximated by a Gaussian distribution as their values increase. This is the case for the particular value of kwhich maximizes the variance, so the maximum conﬁdence intervals are well approximated by treating the posterior distribution with maximum variance as a Gaussian distribution with the same variance. Fig. 4 shows the number of possible packet values contained within the 95 percent conﬁdence interval of the maximum- variance posterior distribution as a function of the number of received bits. This plot is for the particular case of an8-bit packet. When only a single bit has been received, the 95 percent conﬁdence interval includes all possible packets. When 13 bits have been received, the 95 percent conﬁdence interval contains 128 of the 256 possible packets. When 100 bits have been received, the 95 percent conﬁdence interval includes approximately 50 of the 256 possible packets. These values empirically agree with Fig. 2. IX. C ONCLUSION This paper presents and analyzes a method for probabilis- tically encoding a packet for transmission through a binary deletion channel with an arbitrarily high deletion probability and unknown channel lifetime. The number of bits received before channel closure is unknown to both sender and receiver and assumed greater than or equal to one bit and less than or equal to 100 bits. The supposed deletion channel is one with properties that do not guarantee the intact receipt of any packet larger than one bit, and that do not guarantee the receipt of enough bits to perfectly reconstruct packets longer than 1 bit from partial packets. For such channels, this paper argues that the appropriate encoding method is one which enables the calculation of probability masses over all possible packets rather than one which attempts perfect reconstruction of the transmitted packet. This paper presents such an encoding method. This paper proposes to encode information in the probability of receiving a 1 vs. a 0 (rather than in the 1’s and 0’s themselves). Assuming a ﬁxed packet length, the packet to be transmitted is interpreted as an integer. The ratio between this integer and the largest integer storable in the packet length is interpreted as a probability, x. The sender uses x to decide whether to transmit a binary 1 or 0. Each received bit is modeled as an independent and identically distributed Bernoulli random trial. The bit is 1 with probability xand 0 with probability (1x). The probability density function for x is calculated by the receiver via Bayesian inference. This paper analyzes the statistics of convergence of this estimator and ﬁnds the upper bound for conﬁdence intervals for all numbers V . HUNTER ADAMS 7 of received bits from 0 to 100. It is shown that, for an 8- bit packet with 256 valid integer values, the upper bound for the 95 percent conﬁdence interval contains 128 of the 256 possible packets when 13 bits have been received. When 100 bits have been received, the 95 percent conﬁdence interval includes approximately 50 of the 256 possible packets. ACKNOWLEDGMENT Thank you to Kalani Danas Rivera, Joshua Umansky- Castro, and Rachel Miller for reviewing this work. [7] was used as a reference for the standard statistics equations used throughout this paper.