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](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=05560464)) is somewhat related to this question.



How Does Random Noise Typically Look?
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.


