How Does Random Noise Typically Look?

Question

How does random noise in the digital world typically look?

Suppose you have a memory of n bits, and suppose that a "random noise" hits the memory in such a way that the probability of each bit being affected is at most t.

What will be the typical behavior of such a random digital noise? Part of the question is to define "random noise" in the best way possible, and then answer it for this definition.

The same question can be asked for a memory based on a larger r-letters alphabet.

In particular (as Greg mentioned) I am interested to know: Will the "random noise" behave typically in a way which is close to be independent on the different bits? or will it be highly correlated? or pehaps the answer depends on the size of the alphabet and the value of t?

The source of this question is an easy fact about quantum memory which asserts that if you consider a random noise operation acting on a quantum memory with n qubits, and if the probability that every qubit is damaged is a tiny real number t, then typically the noise has the following form: with large probability nothing happens and with tiny probability a large fraction of qubits are harmed. (So in this case, random noise is highly correlated.)

I made one try for the digital (binary) question but I am not sure at all that it is the "correct" definition for what "random noise" is. I considered a random permutation of all the 2^n binary strings of length n subject to the condition that at most t bits are flipped. I will be happy if somebody can think about the case of larger alphabet and also offers the conceptually "correct" framework for this question.

Perhaps the best way to ask this question (following Jason's and Greg's remarks) is this: What is the appropriate way to define a "random" probability distribution on {0,1}^n and on {0,1,...,r}^n.

Given such a definition we the would like to understand the typical behavior of such a random probability distribution with the additional property that the probability for the ith coordinate to be non zero is at most t for every i.

Updated formulation: One way to solve the question was proposed by Greg: The space of stochastic maps on a finite probability space is a convex polytope. So you can choose one using standard Euclidean measure. (In our case, the finite probability space is the uniform probability space on {0,1}^n, and more generally, the uniform probability space on {0,1,...,r}^n.)

The question is (stated for the binary case) this: Let t>0 be a small real number. How does a random stochastic map, conditioned on the property that a proportion of t bits are corrupted looks like. Is it also the case, as Greg expects, that (like in the quantum case,) with large probability nothing happens and with small probability many bits are corrupted.

I will be happy to see how to do the calculation precisely or heuristically, or perhaps to find it in the literature.
Update: The notion of Arikan's polar coding (See e.g. this paper) is somewhat related to this question.

Answer 1

I think people might be misinterpreting the question.

The easy fact that I think Gil has in mind is that if you randomly choose a quantum noise operation with certain properties, then for most choices of that noise operation, although the total error rate will be very low, the errors will be highly correlated. The orthodox interpretation is that this is an artificial way to choose a quantum noise model.

One analogous classical question is as follows: If you randomly choose a stochastic map on the probability space of bit strings, with similar properties, what will it look like?

Gil proposes a randomly chosen permutation subject to the condition that at most t bits are flipped. I am not sure that that is really a good analogy to the quantum noise model that he proposes.

The Poisson process that flips bits is a specific model of random noise on bit strings. It is not a randomly chosen model of noise.

---

Gil has added the more specific question of why a random stochastic map conditioned on few errors will have the "ambush noise" property that he describes for a random unitary operator. There is a more complicated version, in which each bit separately has a bound on error, and a simpler version, where you just demand that at most $tn$ of the $n$ bits are changed. I will look at the simpler version. As a first step, the different inputs to the stochastic map do not communicate in this question. Each bit string, for instance the string of 0s, is sent to another bit string according to a distribution which is uniform on the simplex of all $2^n$ bit strings. So I will concentrate on just what happens to the 0 string.

One remark is that the fate of just the 0 string is actually statistically identical, whether you choose a random stochastic map classically or a random unitary operator quantumly. The first column of a random unitary operator is a random vector in $\mathbb{C}P^{N-1}$ (with $N = 2^n$ for us). The induced map from $\mathbb{C}P^{N-1}$ to the $(N-1)$-simplex of distributions is a toric moment map, and a famous fact (due to Archimedes for $\mathbb{C}P^1$) is that toric moment maps are measure-preserving. The difference between a random stochastic and a random unitary only first appears with pairwise correlations, and when $N$ is large only very-high-order correlations are significant. If Gil has an argument for random unitaries, this remark suggests that it also applies for random stochastics.

More directly, a distribution on bit strings induces a distribution on Hamming weights of bit strings. This is a linear map from a huge simplex $\Delta_{N-1}$ to the smaller simplex $\Delta_n$ whose corners are labelled by the Hamming weights $0,1,\ldots,n$. We are interested in the push-forward of uniform measure. Let $p_0,\ldots,p_n$ be barycentric coordinates on $\Delta_n$; $p_k$ is also just the probability that the random bit string has weight $k$. Then push-forward of uniform measure on $\Delta_{N-1}$ is proportional to $f(p) \propto \prod_k p_k^{\binom{n}{k}}$. So, in this induced measure on $\Delta_n$, there is an enormous statistical attraction to the corners with middle values of $k$.

Now let's impose the restriction that the total error is at most $tn$, in other words that $$\sum_k kp_k \le tn.$$ This cuts the simplex $\Delta_n$ by a hyperplane. At this point I'll switch to a rough calculation. If $t \ll \frac12$, and if you maximize the log of the probability density $\log f(p)$, the maximum puts most of the probability in the weights $k \approx n/2$. That's because the corresponding term in $\log f(p)$ is $\binom{n}{k}(\log p_k)$. The logarithmic dependence on $p_k$ is outweighed by the sizes of the coefficients. There is a also a geometric factor if your are close to a sharp corner of the cut simplex; however after a logarithm this geometric factor is of order $n$, which is again much smaller than the binomial coefficients.

Answer 2

I am still thinking about the original problem, but let me discuss the side problem of random strings.

In the infinite case the proper way to designate "random" is fairly similar to the "random tree" problem brought up recently: given a string length n, every possible string of that length occurs with the same frequency. This is how "normal" is defined for transcendental numbers to capture the notion that they occur randomly.

This is problematic for the finite case because the string 1111111111 can occur with equal probability as the string 1100101010. From a "pure" standpoint there appears to be nothing we can say, but in applied circumstance with a large enough sample set it is possible to get a notion of bias.

    

    (Picture source, also more information on what I'm discussing.)

We would expect (letting p(n) be the number of complete permutation strings in the first n digits of a string) that in base ten n/p(n) would converge to 2755.

The "synthesized" data in the graph above comes from the infamous Rand Corporation work A Million Random Digits, and does appear to have a sort of bias.

However, in the case of even a converging sequence (like the digits of pi) in the low-n cases it's impossible to determine anything from n/p(n). This suggests to me that the noise model problem can only be approached (if at all) from the large-n case.

Answer 3

I think that there is a point of possible confusion with what it means to say there is an error. When I think about a noise process on a quantum system, I think of the following. Given an initial state $\rho$ of the system, the noise process is a completely positive map $\mathcal{E}$ that produces the output state $\sigma = \mathcal{E}(\rho)$. So, unless the channel is the identity channel, then there is always something nontrivial happening (for at least some choice of initial state $\rho$). So has an error occurred? In some sense, yes. Even if the channel has an operator decomposition where a large fraction of the support of the channel is on the identity channel, then there is in general always an error. I think the point of confusion is that for these types of channels, when you measure the state it will collapse into either a state with no error, or a state with (potentially) lots of errors. So, yes, the errors are highly correlated. But the channel is trying to model some kind of conditional independence. Upon measurement, you think of the channel as either having acted trivially, or having done something bad, like apply a randomly sampled Pauli error. Conditioned on something bad happening, then you have independence.

(For anyone unfamiliar with quantum channels, a classical model showing this kind of behavior would be a kind of "catastrophic loss" channel, where you put all $n$ bits into the channel, and with probability $1-\epsilon$ they are faithfully transmitted, and with probability $\epsilon$ you throw away the bit string and replace it with noise, c.f. something sampled uniformly from the hypercube.)

Also, following up on Gil's comment in Greg's answer, one obvious way to define a random stochastic map would be to just pick random probability distributions and make them the rows of a stochastic matrix. Picking a random distribution could be done by choosing your favorite measure on the simplex whose points are labeled by bit strings. You'd still have to decide how to choose the dependencies between rows. Even under the simple and natural case of uniform measure and independently chosen rows, it is not clear to me how this looks.

Answer 4

The type of noise that one could probably handle ('filter' or recover from) is such that for any given time t, any k bits are damaged with probability at most epsilon^k for some small positive epsilon.

Answer 5

Perhaps I'm misunderstanding the question, but it seems to me that this is similar to standard communications questions:

You have a message of $k$ bits, and each bit gets garbled with probability $p$ and this is independent of whether any other bit gets garbled, how do you detect flipped bits? How many bits get garbled? How do you design an error detecting and correcting code? This may be where I'm differing from the intended question, but I think the standard models for this in the theory of communication use a binomial distribution.

If I'm on the right track, then there are many books, and papers related to this. Any search for Shannon entropy, error correcting codes, or similar fields should help.

While it's not particularly well written, this wikipedia entry may point you towards the subject material you are interested in:

http://en.wikipedia.org/wiki/Bit_error_ratio

Answer 6

I think that the statistics of quantum and classical systems differ by a large amount. For one thing the bits of the classical system can be stored arbitrarily far from each other so correlation of errors could cause problems with action at a distance. Quantum states that are entangled can have non-classical correlations. For another bits of a classical system can be duplicated and those in a quantum system can't. For a quantum system error correcting erorors is possible if entanglement is used. These highly entangled bits can repair more than one error to one bit. One code uses 9-entangled qubits. Because of this I think that n qubits will have a different error distribution than n classical bits. I think one difference is entanlegment which may occur in a quantum computer. Classical bits can have independent noise in fact in some cases the noise not being independent may cause problems with action at a distance. For quantum systems there may dependence in the noise especially if there is entanglement. For dealing with a system with 9-entangled qubits the error distribution may have to be derived from the physics involved. Of course if the wrong distribution is used that is a problem but finding the right distribution may involve finding a physical model calculating the effects and testing it. Right now I think quantum computers are doing things like factoring 15 right now so they have a long way to go.

Since I have written the above paragraph I have looked at "How quantum computers can fail". It looks like that the primary concern is if there is a problem with quantum computers in that correlated variable can have problem with noise that is correlated. In the classical case there are some cases where the speed of light seems to inhibit any correlation without quantum entanglement. Theoretically the digits of a binary sequence could be stored on different galaxies. In cloud computing I think information can be stored in different machines far apart. So it appears that in some cases there is a counterexample to correlated noise. That would seem to cause a problem for a generalization of all noise on different scales. That said quantum computers could well fail at some level of complexity. To perform more interesting tasks more complexity is required and these could run into a problem like coordinated noise.

Answer 7

Feeling a vague inclination to keep the topic warm, but failing a clear sense of the word "random" that is wanted here, maybe it would serve to mention a few concepts that I use for thinking about "arbitrary" transitions in bit spaces, for example, a boolean space of abstract type $\mathbb{B}^k$.

First off, given $k$ boolean variables, $x_1, \ldots, x_k$, we have two options for pointing out a point $\mathbf{x}$ in $\mathbb{B}^k$, namely, by giving its $k$-tuple $(x_1, \ldots, x_k)$ in the coordinate space, or by giving a "singular proposition" that singles it out, that is, a logical proposition equivalent to a conjunction of $k$ literals, written either as a boolean product, $e_1 \cdot \ldots \cdot e_k$, or with the symbol "$\land$" for "and", as $e_1 \land \ldots \land e_k$, where $e_j = x_j$ or $e_j = \lnot x_j$ for each $j \in [1, k]$.

Notice that the $k$ coordinate projections are maps of the form $x_j : \mathbb{B}^k \to \mathbb{B}$, which puts them in a special case among the $2^{2^k}$ boolean functions or logical propositions of the form $f : \mathbb{B}^k \to \mathbb{B}$.

Another important special case is the set of linear propositions, indicated here as $\mathbb{B}^k \overset{\ell}{\to} \mathbb{B}$, and you know there must be $2^k$ of those. They are in fact all the boolean sums that can be formed from subsets of the $k$ variables, where "+" is the field operation, in other words, $\operatorname{xor}$.

Further information about special classes of propositions in boolean function spaces may be found here:

• Differential Logic and Dynamic Systems : Special Classes of Propositions

Answer 8

If we think of a boolean function of type $\mathbb{B}^k \to \mathbb{B}$ as a "proposition" about bit strings in $\mathbb{B}^k$, then it amounts to the simplest example of a "distribution" over $\mathbb{B}^k$. Keeping to the field GF(2) for everything in sight, a function of type $(\mathbb{B}^k \to \mathbb{B}) \to \mathbb{B}$ can be thought of as a "higher order proposition", that is, a proposition about propositions about bit strings of length $k$. But it may also be thought of as the simplest example of a distribution over distributions over the space $\mathbb{B}^k$, in other words, a "measure" on distributions over $\mathbb{B}^k$. The link just given exhibits some pictures for the low dimension cases $k = 1, 2$ that may help to support the intuition a bit.