{'fraction_non_alphanumeric': 0.038611532851061295, 'fraction_numerical': 0.010181298562114853, 'mean_word_length': 4.258609893550407, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Non-parametric Message Important Measure: Storage Code Design and Transmission Planning for Big Data

Storage and transmission in big data are discussed in this paper, where message importance is taken into account. Similar to Shannon Entropy and Renyi Entropy, we define non-parametric message important measure (NMIM) as a measure for the message importance in the scenario of big data, which can characterize the uncertainty of random events. It is proved that the proposed NMIM can sufficiently describe two key characters of big data: rare events finding and large diversities of events. Based on NMIM, we first propose an effective compressed encoding mode for data storage, and then discuss the channel transmission over some typical channel models. Numerical simulation results show that using our proposed strategy occupies less storage space without losing too much message importance, and there are growth region and saturation region for the maximum transmission, which contributes to designing of better practical communication system.


I. INTRODUCTION
Recent studies show that the problem of data storage and message transmission is becoming much more important and intractable in the era of big data for the contradiction between the limited traditional hardware storage equipment and the sharply increasing data deluge [1]. On the one hand, it is usually neither practical nor worth to store all the message as before when facing the huge amount of data, such as the massive number of connected devices in the Internet of Things [2]. On the other hand, the exponentially increasing data traffic will present huge challenges to transmission design in the future [3]. One of the effective solutions for storing and transmitting the massive amount of data is to directly compress the data sample first and then recover them from compressed samples with minimized information loss [4]. In fact, there is a high level of redundancy in datasets, so redundancy reduction and data compression have little effect on the potential values of the data [1]. The lossy data compression has been discussed in many scenarios, e.g., [5]- [8]. In addition, the lossy transmission of a bivariate Gaussian sources over a Gaussian broadcast channel was studied in [9]. It is noted that the same amount of information loss of different events is treated equivalent in these references. However, it may have various costs in different events. While the errors in useless message may have little impact, the errors in important message can bring disastrous consequences.
Actually, in many cases, sparse events are exceedingly crucial for the fact that people generally concentrate more on the important part of message rather than the whole message itself. For instance, only a few illicit IDs need to be checked in order to prevent financial frauds in synthetic ID detection [10]. Also, only a few individuals need to be closely checked in anti-terrorist system [11]. From ancient times, human beings preferred to record when and where nature disaster events happened (i.e. earthquakes, mountain torrents, hurricanes) rather than to record much more common things of daily life. In this case, the rare events usually contain the most information.
Therefore, the most important information will be substantially retained if the minority subset of these rare events is recorded, which coincides with the cognitive mechanism of human beings.
Generally speaking, people would like to take the events with high probability for granted and would not like to waste storage or transmission resource for them. In fact, the information itself may not have difference from the viewpoint of transmission and storage, but it will be given different importance when received by individuals and/or organizations. Thus, in this paper, we design the strategy of storage and transmission, in which the data is dynamically compressed based on the importance of events, in the case where the rare events contain the most information, which is the minority subset stated above.
Previous studies on the minority subset mainly focused on minority subset detecting under rate-distortion theory [12], [13], graph-based rare category detection [14], hypothesis testing [15], or detecting with the aid of time-evolving of graphs [16]. Information theory has been considered as one of the most important theories in the fields of data storage and communications [17], [18]. Information theory gives the optimal coding and a tight bound of lossless data compression under the typical set [17]. However, these results can not be applied to lossy data compression because it is derived in lossless coding. The other existing information measures, such as Renyi divergence, f-divergence or Fisher information, are usually used in communication theory, data analysis, hypothesis testing or estimation of statistical parameter [19], [20]. However, all these existing information measures characterize all the information as a whole, focusing on typical sets, the events with higher probabilities, rather than the minority subset of events. Therefore, a specific information measure is needed to characterize the minority subsets.
Message Important Measure (MIM) is a fairly useful tool to describe the message importance, which is commonly used in minority subset detection as an information measure [21]. The definition is given by [21] L (p, ̟) = L ̟ (p) = log where p = (p 1 , p 2 , ..., p n ) is a given probability distribution and parameter ̟ is the importance coefficient. By focusing on those small-probability events, MIM is very effective in minority subset detection [21]. The parameter selection of MIM in big data is discussed in [22]. In fact, these two literatures both examined parametric MIM. The flexible parameter in MIM helps to emphasize a certain probability element in a distribution, which is very useful in anomaly detection. However, this parametric MIM may not be applicable in some scenarios for the fact that the optimization of the parameter needs some prior knowledge and also takes excessive computing resources, which makes the MIM in [21] not universal. To overcome this problem, we expand MIM to non-parametric MIM (NMIM), which is more general. Some basic properties and applications was preliminarily discussed in [23]. The more general properties, including NMIM loss distortion and more applications, including the compressed storage code design and transmission planning will be discussed in this paper.
Similar to Shannon entropy, NMIM is only related to the probability distribution. Therefore, it can be easily utilized without the complex process of parameter determination. For convenience of calculations, NMIM is defined as a logarithm of the mean value of the events' importance.
Actually, there are many interesting properties for this new information measure. One important result is that the gap between NMIM of total events and that of minimum probability event will be less than a constant if either sparsity or diversity is satisfied.
Actually, layered transmission schemes and layered coding have been widely discussed in the communication systems designing, e.g. [15], [24]- [26]. In these references, different layers perform disparate things by using different information. This paper proposes two-layer coding mechanism, where the first layer performs the amount of information by Shannon entropy, and the second layer uses NMIM as importance marking.
We then discuss, by means of NMIM, the problem of compressed storage and provide strategy that enormously reduces the precious storage space. This is possible because of allocating resources rationally by providing more code length for important events and little code length for nonsignificant events.
In order to design better transmission strategy, we analyze the change of NMIM during transmission. Then, an achievable NMIM-loss-distortion region is also derived, which is ternary, comprised of the NMIM loss, the distortion and the events' probability distribution. Based on this NMIM-loss-distortion region, one solution of the maximum transmission is proposed which turns to maximizing the entropy in the receiving terminal with limited importance loss.
The main contribution of this paper can be summarized as follows. We give the definition and properties of NMIM, which is an effective measure of importance information. Based on NMIM, a compressed storage strategy in big data is proposed. Furthermore, we analyze the change of NMIM during the transmission and propose the NMIM-loss-distortion region. With the developed results, we solve the problem of the maximum transmission.
The rest of this paper is organized as follows. Section II introduces the definition of NMIM.
Section III gives a detailed discussion of its properties. The speciality of minimum probability is also investigated. In Section IV, the compressed coding problem is formulated as an optimization problem and the explicit solution is presented. The performance of transmission is discussed by means of NMIM to illustrate the practicality of NMIM in Section V. We also study the maximum transmission problem with limited channel capacity and importance loss in this section. Section VI presents the simulation results to certificate our developed theories in this paper and discusses the numerical results. Finally, we present the conclusion in Section VII.

II. NON-PARAMETRIC MESSAGE IMPORTANT MEASURE
In this section, a new non-parametric information measure will be introduced, which is called NMIM. Different from previous studies, in which Shannon entropy uses logarithm operator and Renyi divergence uses polynomial operator [19], NMIM adopts the exponential form because exponential operator can help it magnify the minority subsets.
Definition 1. For a given probability distribution p = (p 1 , p 2 , ..., p n ) of finite alphabet (each element 0 < p i ≤ 1), the non-parametric message importance message is defined as This equation can also be written as In fact, e 1−p i p i is defined as the importance measure of the event with probability of p i . In some case where we need to discuss the importance of one specific event, the following definition is given for convenience.
Definition 2. The importance of the event whose probability is p i is given by As a result, NMIM can also be written as The total importance is the sum of importance of all events, and the logarithm operator in (5) is only to reduce the magnitude of the numerical results.
Let L(p i ) be the logarithm value of the importance of a specific event with probability p i , and it can be written as

III. THE PROPERTIES OF NMIM
In this section, the properties of NMIM is discussed in details. Natural logarithm is adopted in this part.

A. Non-negativity
It is obvious that 0 < p i ≤ 1, so e 1−p i p i ≥ 1 for the fact that 1−p i p i ≥ 0 and we have which means NMIM is non-negativity.

C. Lower bound
For any probability distribution p = (p 1 , p 2 , ..., p n ) without zero elements, it is noted that where the inequality is according to Jensen's inequality [17]. The equality holds if and only if all the p i are equal, i. e. p i = 1/n, which means the uniform distribution achieves the lower bound.

D. Monotonicity
For two probability p 1 and p 2 , if p 1 < p 2 , then we will have L(p 1 ) > L(p 2 ).
Proof. Define f (x) = xe 1−x x and the derivation is given by x . When 0 < x < 1, it is easy to check that f ′ (x) < 0, so that f (x) is a monotonic decreasing function. Since the outer logarithmic function does not change the function monotonicity, we have L(

E. Geometric Center and Barycenter
For any probability distribution p = (p 1 , p 2 , ..., p n ) without zero elements, it is noted that Proof.

F. Event Decomposition and Merging
Let p i (1) + p i (2) = p i , which are the probabilities of the first and second sub-events of the i-th event, we have This shows that NMIM will be increased when one event is divided into two sub-events. On the other hand, if two events are merged into one event, NMIM will be decreased. This is to say, more observation knowledge leads to the increasing of event predication accuracy or decreasing of event unexpected degree. Proof.

H. Taylor Series Expansion
Obviously, the nth order derivative of L(p i ) is: Taylor series expansion of L(p i ) is given by In particular, if p i ≪ 1 < n, then it can be written as I. Minimum probability Proof. Refer to the Appendix A.
Remark 1. Lemma 1 implies that no matter how close or far the two probabilities p 1 and p 2 are, there always exists a N, when n > N, Proof. Refer to the Appendix B.
Remark 2. Lemma 2 means that there exists a p 0 , and if ii) The events size n is large enough, such as n ≫ 1; Proof. It is noted that Furthermore, we can also obtain the lower bound of L (p) according to the monotonicity of logarithmic function, Based on the discussions above, we get Remark 3. Proposition 1 deduces that the gap between L (p) and L(p min ) is less than a constant.
In some applications, p min ≪ 1, so L(p min ) ≫ log 2. In this case, one can use L (p) ≈ L(p min ) instead.

Remark 4. In Proposition 1, it clearly shows the two key characters of big data. Condition i)
reflects the rare event finding. Condition ii) reflects the large diversities of events. This illustrates the validity of definition of NMIM directly in the era of big data.
Remark 5. Proposition 1 explains the sense of NMIM, that the rare events own the majority of information in the viewpoint of message importance, such as seismic record. In this case, we only need to save some small probability events without losing too much information. As a result, it is expected to record large amounts of information with less storage space. Actually, the condition of Proposition 1 is easy to meet in the scenario of big data.
In the era of big data, a large amount of data needs to be stored and transferred. Unfortunately, the storage space of the devices and actual channel capacity are always limited. Therefore, it is quite hard to store or transfer all the messages. Based on the idea of dimensionality reduction, we expect to process a small portion of the data which can retain most importance information.
In fact, NMIM is exactly the importance measure to do this, because this importance measure magnifies this minority data. The remaining parts of this paper cover specific strategies for solving the storage and transmission problem in big data by means of NMIM.

IV. COMPRESSED STORAGE BY NMIM
In this section, we discuss the compressed storage problem with NMIM for big data. Consider the following case, where a security camera takes a lot of photographs from time to time. At present, it is easy for us to analyze the images to get the information which we need. For example, a security camera at the door of one supermarket can record whether someone comes in. It will help us to find the thief if burglary happens. However, storing so much data day by day is too hard, and thus it is necessary to compress this image data.
Consider the model shown in Fig.1, in which there are some events and the event with lower probability owns more importance. In order to compress the data for storage, part of the information will be lost in the process of compression, but the degree of loss can be controlled. In this paper, we consider the rule that minimizes the loss of useful information in compressed encoding. Suppose that there is no error in transmitting and the precision of information reconstruction is only related to the coding length in this model. Obviously, the reconstruction error is monotonically decreasing with respect to code length since more detail can be recoded with longer code length. However, how to measure the loss of information becomes the important question. In fact, the error of important information brings great loss while the common events' loss is insignificant. For example, if the image which contains the suspicious individuals is not clear, we will not able to catch the suspects. However, it will have little influence if the image which shows the usual situation is not clear. In order to describe such kind of things, NMIM is used as the weighting factor. This rule is utilized to minimization of NMIM importance loss. To do so, this optimization problem can be formulated as where l i is the encoding length and D f (l i ) is the reconstruction error function. The source event number is n. To solve this optimization problem, the resource condition need to be taken into account. For convenience, we consider the total code length of all the events K = i l i in this paper. We also suppose that the initial code length of every events is assigned as L. As a result, the average code length before coding is L.

A. Reciprocal Error Model
In this section, the reciprocal error model is adopted, in which we minimize the expected values of NMIM with limited average encoding length. Problem in (24) can be represented by Proposition 2. For a given source event number n and the sum of every coding length K (K ≤ L), the solution to the problem in (25) is given by ⌈x⌉ is the smallest integer larger than or equal to x.
Proof. Refer to the Appendix C.
When p min ≪ 1 or n ≫ 1, the compression ratio can be calculated by n ≫ 1, which can be derived easily in the same way as Remark 3. Generally speaking, the gap between K and L is usually small and p min ≪ 1. In this case, p min K L ≪ 1, which means the data is compressed greatly.

B. Exponent Error Model
In the following, we assume the relation between encoding error and codeword lengths is exponential function. That is to say, exponent error model is used as the reconstruction error function and NMIM is taken as wight to measure the encoding loss. Problem in (24) can be represented by Proposition 3. For given source event number n and the required encoding length K (K ≤ L), the error probability for codeword lengths l i is γ −l i where γ is size of code alphabet. The solution to the problem P 2 is given by Proof. Refer to the Appendix D.
WhenÑ = n, the corresponding compression ratio is ln M (p i )/n ≤ 0 according to (10). In general, we select K being less than or equal to L and n ≫ 1, so K/(nL) ≪ 1, which means this coding scheme does achieve significant compression of data.
In fact, ln(x) is a more smoothing operator than √ x. Therefore, the encoding length is more even in exponent error model than that in reciprocal model.
These two propositions focus on the case where K ≤ L, which guarantees l i ≤ L. In fact, when K > L, the above methods can still be applied with small changes to them. If l i > L, let l i ← L and K ← K − L, and then execute the above compressed algorithm literally, iterate it until all code length are smaller than L. For convenience, the program of our new compressed storage strategy is summarized in Algorithm 1.

Algorithm 1 Compressed Coding
Input: The probability distribution of source, p = {p i , i = 1, 2, ..., n} The sum of each encoding length, K The initial code length, L

Output:
The compressed code length, l i , i = 1, 2, ..., n (26)  In Algorithm 1, the code length depends on the event's importance M(p i ), in which more code size is assigned to the important events and little code size is assigned to common events.
Thus it is feasible to use a small part of storage while retaining most important information.

V. ANALYSIS OF TRANSMISSION BY NMIM
We discuss the message transmission problem in terms of NMIM in this section. As a message is transmitted from one side to another, people generally prefer to see the important part of message rather than the whole message itself, and NMIM will play a key role in such kinds of applications. In this case, we focus on the maximum transmission problem with limited NMIM loss under the physical environment constants, such as channel capacity, the transmission delay, etc., which helps to improve the design of communication systems.

A. The Change of NMIM
First of all, we study the change of NMIM during the transmission of the message.

Definition 3. The change of NMIM is defined as
where p x and p y are the probability distributions of random variables X and Y .
In fact, the value of ψ(X, Y ) could be positive or negative. If the value of ψ(X, Y ) is positive, it means that there is importance loss during the transmission, such as the lose of crucial data.
On the other hand, the loss of importance will be over-interpreted if it is negative, which results in waste of resources. In general, the importance loss produces more severe impairment than importance over-interpreted. In the following part, we only consider importance loss for convenience.
According to Proposition 1, if n ≫ 1 or p xm ≪ 1 1+ln(n−1) , p ym ≪ 1 1+ln(n−1) , we have where p xm and p ym is the unique minimum probability of p x and p y , respectively, and it is the loose upper and lower bounds for ψ(X, Y ). Actually, in most cases, ψ(X, Y ) is hard to study. As a result, some special cases are taken into account here. We first select Binary Symmetric Channel (BSC) since it captures most of the characteristic of the general problem as a traceable model of channel with errors [17], while Bernoulli(p) source (0 < p ≤ 0.5) is adopted for its simpleness and representativeness.
When a message is transmitted from one side to another, it should not change too much for an effective transmission, otherwise this transport fails. Based on this idea, it is reasonable to assume ε(1 − 2p) ≪ p. In most of sceneries, p is not close to 0.5, so ε ≪ p.

Proposition 4. For a given BSC and Bernoulli(p) source, if the transmission error probability
ε is relatively small (ε ≪ p), the change of NMIM is Proof. Refer to the Appendix E.

Remark 6. This proposition means that the change of NMIM is proportional to the ε and s(p). s(p) is a rational fraction with respect to parameter p.
Moreover, when p ≪ 1, s(p) can be simplified to 1 p 2 . In this case, The importance loss is proportional to the ε and inversely proportional to p 2 .
In fact, this result means that the impact of channel and that of source can be decouple under certain condition. On the one hand, p is the attribute of source and has nothing to do with channel, so s(p) is the representation of source. Obviously, s(p) decreases with the increasing of p, so a little loss of information leads to heavy loss when p is very small (the message itself is important in this case). On the other hand, ε describes the channel performance, such as the channel capacity (the channel capacity of BSC is 1 − H(ε) [17]). If channel capacity is relatively small, which means that ε is big, the importance loss will be large. Actually, in the actual communication process, the source can not be chosen and we can only improve the channel performance. In order to improve communication quality in BSC, what we can do is make ε smaller, which is consistent with the known result in information theory.

B. NMIM Loss Distortion
In this section, we still consider the Bernoulli(p) source, but the general binary channel is analyzed rather than BSC. In fact, this special transmission process can also be seen as source coding. The basic problem in NMIM loss distortion is what the maximum expected NMIM loss is as given a particular distortion. Here the NMIM loss distortion function is defined as follows. In the best case, this difference value is zero if L (p x ) = L (px), which means no NMIM loss in coding process. In fact, NMIM invariably changes more or less due to distortion.

Definition 4. The NMIM loss distortion function
In fact, there is a tradeoff between NMIM loss and distortion. We would like calculate the NMIM loss distortion function for some simple sources to explain its physical meaning. Let R (M IM ) (D) describe NMIM loss of Bernoulli(p) source and the distortion is less than or equal to D.

Proposition 5. (NMIM-loss-distortion region). When Hamming distortion measure D (D ≥ 0) is used, the NMIM loss distortion function for a Bernoulli(p) source is given by
where δ(p) = log(pe  Proof. Refer to the Appendix F. Here we focus on the transmission problem to maximize the received entropy with limited NMIM loss and the channel capacity. This model is summarized as follows. For a transmission process X → Y , the entropy in transmitting terminal H(X) and transmission time t determine the bit rate. In order to distortionless transmission, we have H(X)/t ≤ C where C is channel capacity in the required transmission time, which shows the limit on transmission due to channel itself. Furthermore, human beings expect importance loss as small as possible, so people usually prescribe a limit to importance loss, such as 0 ≤ ψ(X, Y ) ≤ ∆, where ∆ is the maximum allowable change of NMIM. In fact, this condition ensures that the receiver can afford the loss.
Within this region, people would like to maximize entropy in receiving terminal, which means receiver can get as much effective information as possible . The mathematical expression for this model is given by Unfortunately, it is not a convex optimization problem, so the solution to P 3 is hard to get in general. In order to facilitate the analysis, we consider this problem in the extreme case firstly. When ∆ = 0, which means that there is no NMIM change before and after transmission, the message X is transmitted to the receiving terminal perfectly. As a result, max For simplifying the analysis, we consider this maximum transmission problem in Bernoulli(p) source as a typical example.
Proposition 6. For a Bernoulli(p) source, if ∆ ≥ 0 and 0 < Ct ≤ 1 bits, the solution to the constrained maximization P 3 is given by where H(p 0 ) = Ct and δ(p 0 ) is defined in (64).
Proof. Refer to the Appendix G.
Remark 7. Proposition 6 shows that there are growth region and saturation region for the maximum entropy of receiving terminal with respect to ∆. The turning point is at ∆ = δ(p 0 ).
Remark 7 shows that people can not increase ∆ unlimitedly to obtain better performance when other parameter fixed. δ(p 0 ) is the minimum allowable NMIM loss when the receiver wants to maximize the entropy of the information.
Moreover, according to H(p 0 ) = Ct, so p 0 = H −1 (Ct) when we consider 0 ≤ p 0 ≤ 0.5. Refer to [17], H −1 (·) is monotonic increasing function, which means p 0 increases with increasing of Ct. In fact, the monotonicity of δ(·) is similar with L(·) which is monotonic decreasing in (0, 0.5] according to III-D. As a result, δ(p 0 ) decreases with increasing of Ct, which means the receiving amount of information increasing with increasing of the product of C and t when the allowed importance loss is fixed. It also shows that the channel capacity and transmission time affect the performance of maximum transmission together. In fact, Ct is mobile service, which reflects the cumulative transmitted information for a channel within a period of time [27].
Based on the result discussion above, NMIM can be used as a very useful importance measure to help us analyze and design practical communication system.

VI. NUMERICAL RESULTS
In this section, numerical results will be presented to validate the above results in this paper.

A. The properties of minimum probability
First of all, the relationship between NMIM of total events and that of minimum probability event is discussed when the probability distribution is Zipf, Normal and Rayleigh distribu- to find that all the minimum probabilities are unique and far less than 1 1+ln(n−1) , which means that the condition of Proposition 1 is met. Fig. 4 shows the gap between L (p) and L(p min ) is less than a constant (log 2), which proves validity of Proposition 1. Moreover, L (p) − L(p min ) decreases with increasing of n. In fact, this gap will almost disappear in comparison to L(p min ) when n is relatively large. At this time, we can use L (p) ≈ L(p min ), which is shown in Fig. 5.

B. Compressed coding by NMIM
Next, we focus on conducting the simulation by computer to compare and analyze the compressed coding. The initial code length of every events L is 100. The required coding length The size of alphabet for exponent γ is 2. To better show the performance, some other coding schemes are listed here. The code length is distributed equally in Code 1. The code length in Code 2 is assigned to each events according to its possession rate in total probability. More code size is assigned to the one with smaller probabilities in order to reduce the importance loss. More important, the average code length of NMIM code is the smallest in most time among the three considered encoding strategies. The loss of message importance decreases with increasing of K for all the compressed encoding strategies. There exists a threshold K 0 (K 0 = 100 in Fig.   6 and K 0 = 140 in Fig. 7). When K > K 0 , the message importance loss for NMIM code will almost disappear. In general, there is a tradeoff between average code length and accuracy for any compressed coding, but NMIM provides a new compressed way taking events importance into account.
There are also some difference between Fig. 6 and Fig. 7. In Fig. 6, the message importance loss decreases slowly when K < 90 and decreases rapidly when K > 90. However, in Fig.   7, the loss of message importance reduces fast from the beginning and then slows down when K > 140. The average code length in Fig. 7 is bigger than that in Fig. 6   Obviously, the importance will not change in this case. Furthermore, the approximate value and εs(p) are very close to the true value. As a result, εs(p) is a good approximation in this case.
In the range of the error permitted, ε/p 2 is also a feasible approximate value. In this figure, we only consider the case in which 0 < p < 0.5 for the fact that Bernoulli(p) is symmetry about p = 0.5.

VII. CONCLUSION
In this paper, we discussed the problem of storage and transmission in big data with taking message importance into account. As an extension of MIM, we defined NMIM to measure the message importance, in which we mainly focus on the minority subset different from Shannon entropy. By fully analyzing the properties of NMIM, we found that the difference between message importance of low-probability events and that of all the events is less than a constant, if either the low-probability value is extremely small or the events number to be considered is large. These two conditions are correspond to the two major characters of big data, which are the rare event finding and the large diversities of events.
Then we proposed an effective compressed storage strategy based on NMIM, which coincides with the cognitive mechanism of human beings, and greatly reduces the average code length with little importance loss. We further analyzed the change of importance during transmission and defined NMIM loss distortion function to characterize the tradeoff between NMIM loss and distortion. Importantly, we found that there are growth region and saturation region for maximum transmission problem, which helps to improve the design of practical communication systems.
APPENDIX A PROOF OF LEMMA 1 Proof.
Because 0 < p 1 < p 2 , we might as well take x = p 1 p 2 and x ∈ (0, 1). Therefore, (39) can be written as This means, we only need to check xe n(1−x) ≥ n − 1 holds if n is large enough. It is easy to check that xe n(1−x) monotonically increases in interval (0, 1 n ) and monotonically decreases in the interval ( 1 n , 1). As a result, if ∃ x 1 ∈ (0, 1 n ) and Solve the equation x 1 e n(1−x 1 ) = n − 1 in the interval (0, 1 n ), we get (41b) is obtained by removing nx 1 for the fact that lim n→∞ ne ln(n−1)−n = 0, which leads to nx 1 is close to 0 when n is very large.

APPENDIX B
PROOF OF LEMMA 2 Proof. We prove this lemma in a similar way as Appendix A. We also take x = p 1 p 2 and x ∈ (0, 1). According to (40), it is easy to check that xe 1−x p 1 monotonically increases in interval (0, p 1 ) and monotonically decreases in the interval (p 1 , 1). As a result, if ∃ x 1 ∈ (0, p 1 ) and x 2 ∈ (p 1 , 1) s.t.
In a similar way as Appendix A, we have (43) is obtained by removing x 1 /p 1 for the fact that lim , this interval will become as (0, 1).

Remark 9.
For arbitrary positive number x < 1 and constant n, one can always find a p 0 , when

APPENDIX C PROOF OF PROPOSITION 2
Proof. We can write the constrained minimization P 1 using Lagrange multipliers as the minimization of Differentiating with respect to l i , we get where M(p i ) = p i e 1−p i p i according to (4).
Setting the derivative to 0, and we get l i = M(p i )/λ. Substituting this in the constraint , and hence But since l i must be intergers, we will set l i = APPENDIX D

PROOF OF PROPOSITION 3
Proof. We can write the constrained minimization P 2 using Lagrange multipliers as the mini- Differentiating with respect to l i , we get where M(p i ) = p i e 1−p i p i according to (4).
Setting the derivative to 0, and we get l i = ln M (p i )+ln ln γ−ln(−λ) ln γ . In order to ensure l i > 0, so we take Substituting this in the constraint K = The key of this optimization problem is the second item in (58a). Define p ij = p(i, j) for convenience, and we can solve it as a constrained minimization (61) 28 The function f (t) = te 1 t + (1 − t)e 1 1−t is symmetrical about t = 1 2 . It achieves the minimum when t = 1 2 and it monotonically decreases in (0, 1 2 ). By linear programming, when p 01 + p 10 ≤ D, the range of t is Based on the discussion above, the NMIM loss distortion function for a binary source is Proof. According to [17], where p 0 + D (M IM ) (∆) ≤ 0.5 is due to