{'fraction_non_alphanumeric': 0.049062016209816955, 'fraction_numerical': 0.017143247427374556, 'mean_word_length': 3.7054097482592394, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Transmission of a Bit over a Discrete Poisson Channel with Memory

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated to the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large.


I. INTRODUCTION
Discrete Poisson channels are widely used to model molecular and optical communication channels [1]- [10]. In particular, the Poisson distribution is used to model one of the main types of noise in molecular communication, namely the counting noise. Moreover, discrete Poisson channels with memory are also used to model molecular transmitters [11,Sec. 3.6] [12], [13]. Poisson channels (e.g. [4]- [10]). Also various modulation techniques are proposed for this channel [14]- [17]. For instance [14] designs codes without any access to the channel state information.
Three key parameters in the problem of communicating a message over a discrete Poisson channel are (i) the length of the message, (ii) the number of times the channel is used, and (iii) the error probability of the transmission. On the one hand, the classical notion of capacity assumes transmission of a long message of length N R bits over N uses of the channel with a vanishing probability of error. The receiver waits to receive the entire N output symbols in order to decode the N R message bits. On the other hand, practical modulation schemes usually code a few bits of information over a few channel uses with a given probability of error in each transmission block; decoding is performed over smaller chunks over smaller chunks of output symbols (the decoder can decode each transmission block separately). Unlike capacity achieving codes, the error probability of a modulation scheme cannot converge to zero when the number of channel uses is limited. In this paper, we consider the latter setting and study the problem of finding an optimal coding scheme to send a message of length one bit over a block of length N with the lowest possible probability of error. Since we consider the problem of transmission of a bit B ∈ {1, 2}, the receiver has to distinguish between two possibilities based on its received output sequence. Once the two codewords are designed and fixed, the problem at the receiver reduces to that of a hypothesis testing problem, the optimal decoder is an ML decoder, and the probability of error can be computed. We are interested to find the best choice of codewords that minimize the error probability of the ML decoder The problem of communicating a bit using a fixed number of channel uses is of relevance for the following reason: firstly, it ensures that the transmitted bit is decoded after receiving a fixed number of output symbols; in order words, if we repeatedly use the coding scheme to send multiple bits over consecutive blocks, the receiver can decode the transmitted bits one by one, with limited decoding delay and complexity. Secondly, some applications in molecular communication require only the transmission of a few bits of information (low rate communication). In diffusion based molecular communication, carriers of information are molecules which physically travel from transmitters to receivers. The diffusion process is usually slow and low rate communication is of relevance in this context. Several applications of data transmission at low rates is reviewed in [18]. For instance, in targeted drug delivery applications there is a control node which orders DRAFT another center to release the drug or stop it (a one-bit message) [19]. Moreover, as argued in the literature, molecular transmitters and receivers may be resource-limited devices, and utilizing sophisticated coding schemes with long blocklengths may not be practically feasible in molecular communication. Therefore, considering codes with small blocklengths (and therefore low rates) are of particular relevance to molecular communication. Very short blocklengths are also of relevance in certain wireless applications (see [20], [21] for a list of applications).
The authors in [22] study the transmission of a single symbol over a memoryless additive white Gaussian noise (AWGN) channel where the decoding delay is assumed to be zero. The authors in [21], [23], consider the transmission of up to two bits of information over memoryless BEC, BSC and Z-channels and derive the optimal codes of arbitrary blocklength (the problem is open for more than two bits of information). The key difficulty in finding the optimal codewords is that the exact error probability does not have a nice expression. It is shown in [24] that taking "the minimum distance" of a code as a proxy for its error probability can be misleading. Thus, one has to consider the exact structure of the codes, and cannot simply work with certain code parameters (as commonly adopted in coding theory). Similarly, inequalities on the error probability such as the one by Gallager on the error probability [25,Ex. 5.19] are not immediately helpful.
In this paper, we consider the problem of communicating a bit over discrete Poisson channels.
In other words, we consider the same problem as considered in [21] for discrete Poisson channels. However, our setup is different from that of [21] as we also consider channels with memory.
A challenge in the study of the Poisson channels is that we are using the optimal maximumlikelihood decoding at the receiver. It turns out that to follow the ML decoding rule for a Poisson channel with memory, the decoder needs to take a threshold and compare a weighed linear sum of its received sequence with that threshold. In other words, because of the memory of the channel, a transmission at a certain time slot will affect multiple received symbols at the receiver. This complicates the expression of the exact error probability which will also be in terms of Poisson tails that do not have explicit analytical closed forms. Since we are interested in the optimal codewords, an approximation of the Poisson tail with a Gaussian tail can be suboptimal. The problem is further complicated by the fact that the first derivative and second derivative conditions are complicated-looking expressions and are not easily amenable to analysis. Furthermore, we show that the problem of finding the optimal code is a nonconvex optimization problem. Thus, DRAFT to circumvent local minima, in one of the proofs we relax the optimization problem of finding the best code in such a way that the local minima are eliminated while the global minimum is preserved.
The main results of this paper are as follows: 1) For blocklengths larger than channel memory, we provide an optimal code under the totalpower constraint. A partial result is provided for the case of blocklengths less than the channel memory.
2) For any arbitrary blocklength N the optimal code is derived under the peak-power constraint in the high-power regime. In this case, the strategy of setting input at its maximum possible value for one input message, and setting the input to zero for the other input message (on/off keying strategy) is shown to be optimal.
3) Under both peak-power and total-power constraints, an optimal code is derived in the high-power regime for Poisson channels without memory. This paper is organized as follows. In Section II we introduce the system model and formally state our problem. Section III presents our main results. In Section IV we provide the proofs of our theorems and lemmas that help to prove theorems. Some of the lemmas and proofs are moved to appendices.

II. PROBLEM FORMULATION
In this section, we describe the system model in details. The section begins by giving the mathematical formulation of a discrete-time Poisson channel. While we consider memoryless channels as well as channels with memory, we do not assume output feedback from the receiver to the transmitter. Next, the transmitter and receiver models are defined.
Channel Model: We begin by defining a Poisson channel without memory. A memoryless Poisson channel takes an input X ∈ [0, ∞) and outputs a symbol Here, d ∈ [0, ∞) is the dark background noise. In other words, the conditional distribution of output given input is as follows: DRAFT If a memoryless channel is used N times, the input sequence X = [X 0 , X 1 , . . . , A Poisson channel with memory is defined as follows (see [4], [26]): if the channel has memory of order K , we associate the channel with a sequence π = [π 0 , π 1 , . . . , π K−1 ] of length K. We call this sequence the channel coefficients. To clarify the physical meaning of the channel coefficients π j , consider a transmitter which is able to release molecules into the environment every T s seconds. The transmitter can choose the number of released molecule at the beginning of each time-slot. The released molecules move randomly and diffuse into the environment, until they hit the receiver upon which they are absorbed. The channel coefficient π j indicates the probability that a molecule released by the transmitter at the beginning of time slot i hits the receiver during the i + j-th time slot. The sequence π i sums up to a number less than one (as some released molecules may not hit the receiver surface at all). We refer the readers to [26, p. 9, Sec. II.D.2] for a more detailed explanation. Assume that the channel is used N times.
Then, the input to the channel is a sequence [X 0 , X 1 , . . . , X N −1 ]. We assume that X i = 0 for i < 0 or i > N − 1 (meaning that transmission occurs only from time instance 0 ≤ i ≤ N − 1).
The output at time instance is given by The physical meaning of the above equation can be found at [26, p. 9, Sec. II.D.2]. In Fig.1, for N = 3 and π = (0.5, 0.5), we sketch a Poisson channel with memory. Each output symbol follows a Poisson distribution whose mean is depicted in this figure. Briefly speaking, Poisson(X i−j ) molecules are transmitted at the beginning of time slot i − j; a fraction of these molecules hit the receiver during the i-th time slot. This fraction of molecules is distributed according to Poisson(π j X i−j ). It can be shown that the total number of received molecules equals Poisson K−1 j=0 π j X i−j plus the background noise distributed according to Poisson(d).

Poisson Channel Channel Input
Channel Output's Mean Values Fig. 1: A Poisson channel with memory π = (0.5, 0.5). Given an input (x = (x 0 , x 1 , x 2 )) of three non-negative real numbers, the outputs is a sequence of non-negative integers ( where Y i has a Poisson distribution whose mean value is depicted. For instance, Y 0 has a Poisson distribution with mean 0.5x 0 + d, while Y 1 follows a Poisson distribution with mean 0.5x 0 + 0.5x 1 + d. The dark noise d is illustrated in gray in this figure. Observe for times 0 ≤ i ≤ N + K − 2 has the following conditional distribution given the input sequence: Observe that when π = [π 0 , π 1 , . . . , π K−1 ] = [1, 0, 0, . . . , 0], the channel with memory reduces to a memoryless channel.
Transmitter Model: The transmitter has a uniform bit B ∈ {1, 2} that wishes to communicate to the receiver. For a blocklength N , the transmitter sends the codeword We say that the codewords satisfy the peak-power constraint A if x ji ≤ A for j ∈ {1, 2}, i ∈ {0, 1, . . . , N − 1}. The codewords satisfy the total-power constraint P if x ji ≤ P, j = 1, 2.
DRAFT In the context of molecular communication, the peak-power corresponds to the maximum number of molecules that could be potentially produced and released by the transmitter during each transmission time slot. However, the transmitter might not be able to maintain this maximum production during the entire transmission period. The total-power constraint corresponds to the total number of molecules that could be produced during the entire transmission period.
The following notation is used throughout the paper: we set and where * denotes the convolution operator. We also assume that λ i = µ i = 0 for i < 0 or Receiver Model: Throughout the paper, we assume that the receiver uses the maximumlikelihood decoding on the received sequence [y 0 , y 1 , . . . , y N +K−2 ] to produce an estimate of the input bitB. Given that each codewords has an equal a priori probability, the optimal receiver with minimum error probability is the ML receiver, and the decision rule (DR) is derived as follows: using the values of λ i and µ i from (3) and (4), the probability of observing (Y 0 , Y 1 , · · · , Y N +K−2 ) while the probability of observing (Y 0 , Y 1 , · · · , Y N +K−2 ) when B = 2 equals where a i = log λ i +d µ i +d and b = N +K−2 i=0 (λ i − µ i ). We decodeB = 2 if the right hand side is greater than the left hand side. The average error probability is the probability thatB is not equal to B. We are interested in optimal codewords x 1 and x 2 that minimize the average error probability under given total-power and/or peak-power constraints on the codewords. DRAFT

III. MAIN RESULTS
In this section, we present our main results. This section is divided into three subsections which classify the results based on the assumptions made about total-power and peak-power constraints.
A. Code design subject to a total-power constraint In this section, we only consider a total-power constraint on the individual codewords (P is finite but A = ∞). Our first result in Theorem 1 identifies a particular structure for the codewords when the blocklength N is strictly larger than the channel memory K. This structure can be suboptimal for blocklengths N ≤ K. To illustrate this, we find the optimal codewords for the special case of N = K = 2. Finding the optimal codewords for blocklengths N ≤ K (in the general case) seems to be difficult.
Theorem 1. Consider a discrete Poisson channel with memory of order K and dark noise d > 0.
Assume that blocklength N is greater than or equal to K + 1, and the two codewords x 1 and x 2 satisfy the total-power constraint P in (2). Then, the following codeword pair is optimal in the sense of minimizing the ML decoder error probability: We remark that the above theorem does not claim that the sequences given in (6) is the only optimal codeword pairs. It just claims that (6) is an optimal codeword pair that minimizes the error probability of the ML receiver.
Proof of the above theorem is given in Section IV-B based on a suitable relaxation of the optimization problem of finding the best code. As shown later in Remark 5, the problem of finding the optimal code is a nonconvex optimization problem, and the relaxation technique is used to circumvent local minima.
An interesting observation here is that the error probability for N = K + 1 is the same as the error probability for any blocklength N > K + 1, i.e., increasing N beyond K + 1 does not decrease the error probability.   Poisson channel without memory. Here, a total-power constraint P = 20 is assumed. According to Theorem 1, the code in (8) is optimal for the both the channels for any value of d.

Corollary 2.
If the channel is without memory (K = 1), an optimal codeword pair for blocklength Since the channel is without memory, any column-permutation of the construction in (7) also yields an optimal code.
Numerical Simulations: In Figure 2, we illustrate the error probability of ML-decoding for the following code: for two channels, one with memory K = 2 and the channel coefficients π = (1/2, 1/2) (Fig. 2a) and another one without memory (i.e. π = (1)). This code is optimal for both channels used in this figure due to Theorem 1. Firstly, observe that the channel memory has a severe impact   on the error probability (in both cases we use the same total-power P = 20). As expected, we observe that the error probability increases as we increase the background noise. This figure also shows that a channel without memory is more sensitive to an increase of the background noise from d = 1 to d = 5 (one curve is almost linear while the other curve is exponential).
In Figure 3 we compare the error probabilities of three different coding schemes for a channel without memory (Fig. 3b) and for a channel with memory π = (1/2, 1/2) (Fig. 3a). In both case, the background dark noise is set to be d = 0.25. The three codes used are as follows: Code C 1 corresponds to on/off keying strategy and its error probability as a function of P is illustrated in red. Code C 2 is a symmetric strategy and its error probability is illustrated in green for both channel. The last coding scheme is C 3 that is the optimal one (according on Theorem 1) for the both channels and its error probability as a function of P is illustrated in blue. This  (11) and (12) for channel (11) is less than the error of (12) and is colored with orange otherwise.
shows that the on/off keying codeword has the worst performance, and its gap with the other two strategies is more significant when there is no channel memory.
We now turn to the case of N ≤ K. Here, we only consider the special case of N = K = 2.
Theorem 3. Consider a discrete Poisson channel with memory of order K = 2 and dark noise d > 0. Assume that the blocklength N = 2 and we have a total-power constraint x 10 + x 11 ≤ P and x 20 + x 21 ≤ P . Then, there are optimal codewords of the form Proof of the above theorem is given in Section IV-C. shows that for channel coefficients [π 0 , π 1 ] = [0.6, 0.4], the optimal codewords are with an error probability of 0.0092. In this example, the codeword pair has an error probability of 0.0095 and is not optimal. This shows that in this example the following holds: (i) the codeword structure given in (6) is not optimal , and (ii) as x 11 = x 21 = 0, the error probability for N = 2 is the same as the error probability for blocklength one. Next, in blue if the first error is less than the second one and is colored with orange otherwise. Note that the patterns are symmetrical with respect to line π 0 − π 1 = 0. This is due to the particular structure of the codes in (11) and (12) whose error probabilities will be symmetric functions of π 0 and π 1 . Note that the code given in (12) is the same as the one given in Theorem 1. However,  Error Probability the assumption of Theorem 1 (N ≥ K + 1) is violated here. This figure confirms that the code given in Theorem 1 may fail to be optimal without this assumption.
Remark 5. Proof of Theorem 3 shows that any codeword that is "locally" optimal (i.e., is not improved by local changes) must be of the following form: Figure 5 plots the error probability of the code given in Theorem 3 in terms of x for the following channel π = [0.5, 0.5], with dark noise d = 0.1. The curve is not convex which indicates that the problem of finding the optimal codewords is not a convex optimization problem.
B. Code design subject to a peak-power constraint In this section, we only consider a peak-power constraint on the individual codewords (P = ∞ but A is finite).
Theorem 6. Consider a discrete Poisson channel with memory of order K ≥ 1 and dark noise d > 0. Then there exists a constant A * depending on the blocklength N , the channel coefficients DRAFT and dark noise level d such that the following holds: for codewords with peak-power constraint A ≥ A * , the optimal codeword pair is More specifically, the above code construction is optimal if A satisfies e −(N +K−1) Proof of the above theorem is given in Section IV-D.
In Fig. 6 we compare the error probabilities of three coding schemes. The channels used for this plot are the as those used in Fig. 3. The three codes are as follows: Code C 1 corresponds to an on/off keying strategy which is the optimal code (according to Theorem 6) for the both channel models when A is sufficiently large. Its error probability is illustrated in blue. Note that the code C 1 generally beats the codes C 2 and C 3 even for small values of A. However, in Fig. 7 we we zoom Fig. 6a around A = 1.5. As one can observe, for A = 1.5, the error probability of code C 1 is 0.0504 whereas the error probability of the code C 3 is 0.0485 which is smaller. This indicates that for small values of A, it is not necessarily true that the code C 1 has the smallest error probability among all possible codes.
C. Code design subject to both peak and total-power constraints Assume that K = 1 (no channel memory) and that we have both peak and total-power constraints and their ratio is β, i.e., P = Aβ. If N ≤ β , the amplitude constraint implies A * which depends only on β, d and N such that the following holds: for a given peak-power constraint A ≥ A * and total-power constraint P = Aβ, the optimal codeword pair x 1 and x 2 is where κ and η are sequences of infinite length defined as follows for noninteger β: where β and {β} are the integer and fractional parts of β respectively. For integer β, the sequences κ and η are defined as follows: More specifically, the above code construction is optimal if A satisfies where and Proof of the above theorem is given in Section IV-E.

IV. PROOFS
In the proofs of Theorem 1 and Theorem 6, we use the majorization and some related concepts that are reviewed in Subsection IV-A.

A. Majorization
Majorization is a preorder on vectors of real numbers. We say that a sequence a ∈ R n weakly majorizes b ∈ R n from below and write it as a w b (equivalently, we say that b is weakly majorized by a from below, written as where a ↓ (b ↓ ) is the vector with the same components with a (b) that is sorted in the descending order. If a w b and in addition n i=1 a i = n i=1 b i we say that a majorizes b written as a b.
DRAFT Definition 8. A Robin Hood operation on a nonnegative sequence a replaces two elements a i and a j < a i by a i − and a j + , respectively, for some ∈ (0, a i − a j ) [27]. An Anti-Robin Hood operation (AR) does the opposite on nonnegative sequences. That is, for a sequence a with nonnegative entries, it replaces a i and a j < a i by a i + and a j − , for some ∈ (0, a j ]. Lemma 9 ( [27](p. 11)). Take two nonnegative sequences λ and π of the same length satisfying λ ≺ π. Then starting from λ, we can produce π by a finite number of AR operations. Equivalently we can reach λ from π with the finite sequence of Robin Hood operations.

B. Proof of Theorem 1
The error probability depends on the two codewords x 1 and x 2 through vectors λ = x 1 * π and µ = x 2 * π as defined in equations (3) and (4). In particular, for a given dark noise d, we can view the error probability as a function of the pair (λ, µ). We can write this as P e (λ, µ).
To solve this problem, we first relax the above optimization problem by defining a set T satisfying T ⊂ T , and consider arg min We find a solution (λ , µ ) of the relaxed problem in (18) and verify that the optimizer pair (λ , µ ) belongs to T . This shows that the answers to the original and relaxed problems in (17) and (18) are the same. We highlight a crucial difference between the optimization problems in (17) and (18) that is very helpful to our proof: given a pair (λ, µ) ∈ T , if we apply the same permutation on the sequences λ and µ, we obtain a pair in T . However, given a pair (λ, µ) ∈ T , it is not necessarily true that we remain in T after permuting the two sequences. Let That is, T is the set of pairs (λ, µ) of sequences of length N + K − 1 that are weakly majorized from below by the sequence [P π, 0 N −1 ]. Here, [P π, 0 N −1 ] is a sequence of length N + K − 1 formed by concatenating the sequence P π of length K with the all zero sequence 0 N −1 of length Lemma 10. The relation T ⊂ T holds.
Proof. We need to show that if λ = x 1 * π and µ = x 2 * π for some nonnegative sequences x 1 and x 2 satisfying the total-power constraint P in (2) then We define a function Z(·, ·) that takes in an integer and a sequence of real numbers, and outputs another sequence of real numbers as follows: be a sequence of length N + K − 1 formed by padding zeros to the beginning and end of the sequencexπ.Then, Observe that λ is expressed as a convex combination of the sequences Z (xπ, i). Each of the . Therefore, from [27, We claim that an optimal solution for (18) is as follows: This claim would conclude the proof of the theorem since (λ , µ ) ∈ T as λ = x 1 * π and µ = x 2 * π for (x 1 , x 2 ) given in the statement of the theorem.
It remains to prove that (λ , µ ) is an optimal solution. To show this, we start from an arbitrary pair (λ, µ) and alter the sequences λ and µ in a finite number of steps such that • the error probability does not increase in each step; • we end up with the sequences (λ , µ ).
Therefore, (λ , µ ) is a solution with the minimum error probability. To see this, take an arbitrary pair (λ,μ) with the error probability P e (λ,μ). Then we can alter the pair (λ,μ) in a finite steps and end up with the pair (λ , µ ) while the error probability does not increase in each step. As a result the error probability at the final step should be less than or equal to the error probability of the initial pair. In other words, P e (λ , µ ) ≤ P e (λ,μ). Since the pair (λ,μ) was arbitrary, we conclude that (λ , µ ) is a minimizer of the error probability. Please note that this does not imply that the pair (λ , µ ) is a unique minimizer, and we do not make this claim in the statement of the theorem.
Take an arbitrary pair (λ, µ) of nonnegative real vectors of length Phase 1: Using Lemma 11 we can decrease λ i , i ∈ A c and µ i , i ∈ A to zero and produce λ , µ such that the error probability does not increase. Since λ ≺ w λ and µ ≺ w µ, we obtain that λ , µ ≺ w [P π, 0 N −1 ].
Phase 3: Since the length of λ and µ are greater than or equal to 2K, based on Lemma 11 we can increase the elements of λ and reach [π K , 0 N −1 ]. Similarly (after reordering of indices) from DRAFT µ we can reach [0 N −1 , π K ] such that the error probability does not increase. With reordering the columns we reach λ , µ given in (19). The proof is complete.
We utilize the fact that if a codeword pair (x 1 , x 2 ) is optimal, it must satisfy the necessary conditions given in Lemma 17. Assume that we have a pair of codewords that is not of the following form: Then, one of the following three cases hold: 1-One of the codewords (without loss of generality x 1 ) satisfies the following conditions: x 10 + x 11 < P, x 10 , x 11 > 0.
Hence D 0 = a, D 1 = −a π 0 π 1 and D 2 = a π 0 π 1 2 for some a ∈ R. Therefore, the signs of D i , 0 ≤ i ≤ 2 have three different possibilities as follows: DRAFT For each case, we can use Lemma 17 to find an equivalent condition for decision rule coefficients a i . Using the definition of a i given in (5) and the definitions of λ and µ given in (20), we obtain the following conditions for the three cases respectively: x 10 < x 20 , x 11 < x 21 , x 11 π 0 + x 10 π 1 > x 20 π 0 + x 21 π 1 ; x 10 > x 20 , x 11 > x 21 , x 11 π 0 + x 10 π 1 < x 20 π 0 + x 21 π 1 ; x 10 = x 20 , x 11 = x 21 , One can directly verify that in the first two cases, the inequalities contradict each other.
The third case implies that the two codewords are equal, which is clearly the worst possible choice for the two codewords.
From Lemma 17 we have which results in From π 1 , π 2 > 0, the sign of D i can have the following possibilities: We show that in each case (if it can occur), we can reach to [P, 0] or [0, P ] from x 1 without increasing the error probability. to zero, the error probability would not increase. Next, if x 11 π 1 ≤ x 10 π 0 , Lemma 12 shows that increasing x 10 to P and decreasing x 11 to 0 would not increase the error probability. A similar argument works for x 11 π 1 ≥ x 10 π 0 .
(g): This case is similar to case (f). For the first one if xπ 1 ≥ x π 0 we can increase x to P and else increase x to P . Hence the optimal code has to have the following structure for some 0 ≤ x ≤ P :   x 1

D. Proof of Theorem 6
Take an arbitrary codeword pair (x 1 , x 2 ). The error probability of the codeword pair ( The idea of the proof is as follows: we alter the pair (λ, µ) in a number of steps such that (i) in each alteration step, the error probability of the altered pair is less than or equal to the error probability of the unaltered pair, and (ii) at the end of the alteration steps, we either reach the pair corresponding to the one given in the statement of the theorem, or we reach a pair whose error probability is greater than or equal to the one given in the statement of the theorem provided that A is sufficiently large. This shows the optimality of the codeword pair given in the statement of the theorem.
By operations of Lemma 11, we can reach from (λ, µ) to (λ , µ ) without increasing the error probability. However, observe that it may not be possible to express (λ , µ ) as π * x 1 , π * x 2 for some codewords x 1 and x 2 . Nonetheless, we can identify two new codewords x 1 and x 2 whose error probability is less than or equal to that of the pair (λ , µ ).
If |{i : λ i > 0}| = N +K −1, we have µ = 0. Since λ ≺ w λ = x 1 * π ≺ w x 1 * π = λ , where where λ is sorted in the descending order and 0 ≤ r 1 ≤ λ t+1 . We can move from λ to λ 1 with AR operations using Lemma 9. Corollary 13 guarantees that the error probability does not increase during these AR operations. Using Lemma 11 we can increase the elements of λ 1 and reach to λ = x 1 * π with power N A K−1 i=0 π i without increasing the error probability. Therefore, the error probability of (λ, µ) is greater than or equal to the error probability of If 0 < |{i : λ i > 0}| < N + K − 1, we have µ j > λ j for some j. Without loss of generality assume that the power of λ is greater than or equal to the power of µ (otherwise, we can swap the two). We claim that the power of λ is less than or equal to max j∈{0,...,K−1} This holds if x 1i = 0 for some 0 ≤ i ≤ N + K − 2 as the total would be at most in this case. Thus, assume that x 1i > 0 for all Suppose that the first index j where µ j > λ j isj. The weight of λ equals i:λ i =0 λ i . We In the above derivation, the step (a) follows from λ = x 1 * π and nonnegativity of x 1 and π which imply that the total-power of λ (sum of its elements) is not greater than the total-power of x 1 times the total-power of π.
Step (b) follows from x 1i ≤ A for 0 ≤ i ≤ N − 1 (the peak-power constraint). The step (c) follows from λ = x 1 * π and the nonnegativity of x 1 and π which Finally (d) follows from the fact that a linear function of x ∈ [a, b] takes its maximum at a or b.
Since π j > 0 for all j, we have max j∈{0,...,K−1} From Lemma 16, we can find the upper bound e −(N +K−1) on the error probability of the code (λ , µ ). For sufficiently large A we obtain that e −(N +K−1) since the left hand side decays faster than the right hand side to zero as A tends to infinity by (22). Thus, for large values of A, the error probability of the pair (λ , µ ) is greater than the error probability of the code given in the statement of the theorem.

E. Proof of Theorem 7
Consider two arbitrary codewords x 1 and x 2 . Consider the case that x 1i and x 2i are both positive for some i. Let us assume that x 1i ≤ x 2i (the other case is similar). Then, using Lemma 11, reducing x 1i to zero would not increase the error probability. This change would DRAFT also does not increase the power of the codeword x 1 . Thus, using Lemma 11 repeatedly, we can reach to codewords of the following form without increasing the error probability: Using Corollary 13, we can reach the following codewords without increasing the error probability (with AR operations): for some positive x 1n and x 2n and n ≤ (N − 1). Without loss of generality assume that x 2i , else we can switch the two codewords. Using Lemma 11, increasing x 1n or x 2n would decrease the error probability of the code. Thus, x 1n or x 2n can be increased as long as the power constraint allow it. This implies that x 1n and x 2n can be increased to either A or A{β}.
Two cases are possible: if N −1 i=0 x 1i = Aβ, then the error probability of the codeword given in (24) is greater than equal error probability of the codes given in the statement of the theorem by Lemma 11. Else if N −1 i=0 x 1i < Aβ, since x 1n is either A or A{β}, we deduce that where Γ > 0 is a constant defined as follows: DRAFT Similarly, from Lemma 16, we can find the lower bound on the error probability of the code in (24). This proves that the code given in the statement of the theorem has a smaller probability if A is sufficiently large such that Observe that for large enough A, the above equation holds since the right hand side of of the order O e −Aβ log (Aβ) n/log(Aβ) as A tends to infinity while n < N is fixed, which vanishes faster than the left hand side of (27) as A tends to infinity.

V. CONCLUSION
In this paper, we studied transmission of a bit over a discrete Poisson channel with memory under a peak-power or total-power constraint. For the case of having a total-power constraint, the optimal codewords for N > K (code length greater than memory length) are derived. An simple "bursty" code was shown to be optimal in this case. Interestingly, the codewords do not depend on the channel memory coefficients, meaning that the knowledge of channel memory coefficients is not necessary at the transmitter if N > K. The problem seems to be difficult to solve when N ≤ K. In particular, Example 4 shows that the channel memory coefficients affect the structure of the optimal code in this case. This special case is left as a future work. When the peak-power constraint is imposed, an on/off keying strategy is shown to be optimal in the high-power regime regardless of the values of the channel coefficients. Finally, we also investigated the case that both the peak-power constraint and the total-power constraint are imposed. We only provided a result for a channel without memory in the high-power regime. It does not seem easy to explicitly identify the optimal codewords for the most general case.
DRAFT APPENDIX A SOME LEMMAS Take an arbitrary pair (λ, µ) of nonnegative real vectors of length N + K − 1. Let and Then, the decision rule given in (5) can be written as follows. (28) and P e (α, β) is the error probability under the optimal decision rule for the pair (α, β).
Proof. P e (λ , µ ) is the error probability under the optimal decision rule for the pair (λ , µ ). If we use a different decision rule, the resulting error probability will be greater than or equal to P e (λ , µ ). We show that if we use the optimal decision rule of (λ, µ) for the pair (λ , µ ), the error probability will be less than or equal to P e (λ, µ). This shows that P e (λ, µ) ≥ P e (λ , µ ).
Let a i and b be defined as in (30) where Y i 's are mutually independent under each hypothesis. DRAFT With the decision rule given by a i and b, the error probability for the pair (λ , µ ) is equal tõ To show that the expression given in (34) is less than or equal to P e (λ, µ), it suffices to show We prove the first equation. The proof for the second one is similar.
and Y i ∼ Poisson (λ i + d) be independent Poisson random variables. It suffices to show that To show (35), let Z i ∼ Poisson (λ i − λ i ) for i ∈ A be mutually independent of each other and of previously defined variables.
has the same distribution as Y i . Since Z i ≥ 0, where the last step utilizes the fact thatỸ i has the same distribution as Y i . The proof of (36) is similar and follows by defining Lemma 12. Take some pair (λ, µ). Let a i be defined as in (30). Assume that a j ≥ a k . Let λ be equal to λ in all indices except for indices j, k, i.e., λ i = λ i for i / ∈ {j, k}. Furthermore, λ j = λ j + and λ k = λ k − for some ≤ λ k . Then, P e (λ, µ) ≥ P e (λ , µ).
Corollary 13. Let λ be the result of applying an AR operation on indices j, k of λ, and µ j = µ k then P e (λ, µ) ≥ P e (λ , µ) since the condition a j ≥ a k is equivalent with λ j ≥ λ k .
Proof. As in the proof of Lemma 11, it suffices to show that if we use the optimal decision rule of (λ, µ) for the pair (λ , µ), the error probability will be less than or equal to P e (λ, µ). More specifically, let a i and b be defined as in (30) and (31). We use the decision rule given in (32) for the pair (λ , µ). With this decision rule, the error probability under the hypothesis B = 2 is the same for the pairs (λ, µ) and (λ , µ). Therefore, it remains to show that where Y i ∼ Poisson (λ i + d) and Y i ∼ Poisson (λ i + d) are mutually independent Poisson random variables. We now use the following fact about Poisson random variables: given an arbitrary random variable W ∼ Poisson(α 1 +α 2 ), we can decompose W as W = W 1 +W 2 (with probability one) where W 1 ∼ Poisson(α 1 ) and W 2 ∼ Poisson(α 2 ) are independent. Random variables W 1 and W 2 can be constructed from W using the thinning property of the Poisson random variable.
Using this fact, we can find mutually independent random variablesỸ j ∼ Poisson (λ i + d) and mutually independent random variables, the random variablesỸ j and Z j can be also assumed to be independent of Y i for all i = j. Next, By the above equation, with probability one we have The proof is finished by noting thatỸ i 's are mutually independent and have the same distribution as Y i 's.
Lemma 15. Let C be a code (λ, µ) with length N as follows: The error probability of the ML receiver over a Poisson channel with dark noise d > 0 is of Proof. The error probability for ML receiver is derived as follows: where Y [α] denotes a Poisson random variable with mean α and M = N A log((A+d)/d) ≥ 0. Therefore, On the other hand, we can bound the error probability from above by utilizing the Chernoff bound on both terms of the error probability in (43). Since N (A + d) ≥ M , we have (see [28, Eq. 4.1]) where Next, the condition A ≥ 2d implies N d ≤ M and we can also write the following Chernoff bound (see [28,Eq. 4.4]) One can directly verify that where M = N A log((A+d)/d) . Therefore we have u 1 = u 2 . Hence these two upper bounds imply the upper bound in (42).
Lemma 16. Take some arbitrary blocklength N and a code C with the following structure where O(·) refers to the case in which P tends to infinity while n < N is fixed.
Proof. The probability of error is at least 1/2 times the probability of error when the first message (λ) is transmitted. From (5) and the assumption that N −1 i=0 λ i ≥ N −1 i=0 µ i , the threshold in the decision rule is nonnegative. Thus, where Y [α] denotes a Poisson random variable with mean α. By deleting the (n + 1)-th to N -th letters of two codewords the error probability will increase. Therefore P e (C) ≤ P e (C ) where C has the following structure.
Let λ = [P/n, P/n, . . . , P/n] be a sequence of length n with total power P , and set µ = µ .
Let C a code with (λ , µ ). Since λ ≺ λ , from Lemma 9, with the Robin Hood operations on codeword λ we can reach λ . Therefore Corollary 13 shows that P e (C ) ≤ P e (C ). The result then follows from Lemma 15 which implies P e (C ) ≤ e −n( P n +d) e P n + d log P n + d /d P n n/log(( P n +d)/d) = O e −P log (P ) n/log(P ) .
APPENDIX B

NECESSARY CONDITIONS ON AN OPTIMAL CODE
Let (x 1 , x 2 ) be optimal codewords. Then the error probability of the code should not decrease if we perturb x 1 as follows: where ≥ 0 and s is any arbitrary sequence of real numbers such that s i ≥ 0 whenever x 1i = 0, and x 1 + s satisfies the power constraints (if any). Equivalently, where ζ s * π.
We use this idea to show the following necessary condition on the optimal code: Lemma 17. Take an optimal code and let N +K−2 j=0 a j y j 1 2 b be the optimal decision rule for this code. Then there exists real numbers D i for i ∈ {0, 1, . . . , N + K − 2} such that the following holds: Furthermore, if the power of the codeword x 1 is strictly less than the total-power budget P , we have ν = 0.
Proof. Let us use the perturbation argument. From the optimality of codewords and using the same decision rule for the perturbed codewords, the error probability should not decrease under the perturbation. That is, d d P e ≥ 0 at = 0. Since we fix the decoding rule, the probability of making an error when bit B = 2 is transmitted is unchanged. Thus, we have We have Hence, is a linear combination of ζ i where D i = y: a j y j <b N +K−2 j=0 e −(λ j +d) (λ j + d) y j y j !
We begin by proving the second part of the lemma first.
Case 1: If x 1j = 0 for all j: in this case s j ≥ 0 for all j. Therefore, nonnegativity of the derivative of P e (0) in (57) implies that K−1 i=0 D j+i π i ≥ 0 for all j. This implies the second part of the lemma in this case.

Case 2:
There is a unique j where x 1j > 0: let s j = 0 for all j = j. Setting s j ≤ 0, we obtain that K−1 i=0 D j+i π i ≤ 0. Let ν = K−1 i=0 D j+i π i . Consider an indexj where x 1j = 0. Then, choosing sj ≥ 0 and s j = −sj (and s i = 0 for i / ∈ {j,j}) we do not change the power of the codeword, and obtain K−1 i=0 Dj +i π i ≥ ν as a necessary condition. Next, if x 1j (which is also the power of the codeword x 1 in this case) is strictly less than P , we can also choose s j > 0.
This shows that the coefficient K−1 i=0 D j+i π i = 0. Also, similar to Case 1, we can conclude that K−1 i=0 D j +i π i ≥ 0 for all j = j. Case 3: There exists two distinct indices j and j where x 1j > 0 and x 1j > 0. Using the choice of s j = −s j and s i = 0 for i / ∈ {j, j }, we get that the coefficients of s j and s j must be equal, i.e., K−1 i=0 D j+i π i = K−1 i=0 D j +i π i . Thus, K−1 i=0 D j+i π i = ν if x 1j > 0 for some constant ν. Let us choose s j = s j and s i = 0 for i / ∈ {j, j }. If the power of the codeword x 1 is strictly less than the total-power budget P , we can choose s j = s j to be an arbitrary number; otherwise, we should set s j = s j ≤ 0. The first derivative condition then implies that ν ≤ 0 in general and ν = 0 if the power of the codeword x 1 is strictly less than P . Finally, consider an indexj where x 1j = 0. Then, as before choosing sj ≥ 0 and s j = −sj (and s i = 0 for i / ∈ {j,j}) we do not change the power of the codeword, and obtain K−1 i=0 Dj +i π i ≥ ν as a necessary condition. It remains to verify the first part of the lemma. Observe that Thus, we have We show that for any n we have P[Y i ≥ n| N +K−2 Proof. The proof follows a technique that is used in the proof of the FKG inequality, e.g., see [29,Sec. 2.2]. Suppose that X 1 and X 2 are two independent random variables having the same distribution as X, then we have: (f (X 1 ) − f (X 2 )) (g (X 1 ) − g (X 2 )) ≥ 0.
Since f, g have finite second moments, the expectation of the left hand side of the above inequality exists (using the Cauchy-Schwarz inequality), therefore we have: After expanding the above inequality, we have: Because X 1 and X 2 have the same distribution as X, (61) results in: Corollary 19. The same inequality is true for two decreasing functions f, g (have finite second moments) by applying Lemma 18 to −f, −g. Also, if one of them (for example f ) is increasing and the other one (g) is decreasing by applying Lemma 18 to f and −g we have: