What do people mean when they say that they choose a code at random for a probabilistic proof in coding theory ? What is random in the code ?
This is for example used in Shannon’s proof for capacity of BSC or in the proof of the rate of list decoding.
Are the codewords supposed to be uniformly distributed in $\{0,1\}^n$ that is $P(c = \text{some n bit vector from } \{0,1\}^n) = 1/2^n$ where c is a codeword or does it mean that $P(c_i = 1) = P(c_i = 0) = 1/2$ where $c_i$ is the i-th bit of the codeword c ?
The random coding technique is an application of the probabilistic method. Suppose you are working with some class of objects, and want to assert that at least one with a certain property exists. One nonconstructive way to do this is to define a distribution over these objects and prove that the probability of drawing one that satisfies the property is larger than $0$.
In a typical channel capacity proof, we want to show that for large $n$, there exists a $(n,2^{nR})$-code, i.e., a codebook $\mathcal{C}$ consisting of $2^{nR}$ codewords (where each codeword is a bitstring of length $n$), and a decoder $\varphi,$ that we can reliably communicate with (i.e., such that $\varphi$ is resilient to noise over $\mathcal{C}$). For a given codebook, we can define an optimal decoder quite easily (e.g., decode to the "closest" codeword, or decode to a jointly typical codeword), so the main question becomes whether we can find a codebook large enough. So the class of objects is codebooks of $2^{nR}$ codewords, and the property is that it is possible to reliably transmit using it.
Now, the usual random coding argument for the BSC says "pick one codebook at random" in the following way: for each codeword, draw $n$ bits uniformly from $\{0,1\}^n$. Observe that this defines a distribution over codebooks (and thus over codes, if we assume decoding to the nearest codeword, or, as is more common, joint typicality decoding). The bulk of the proof then shows that if $R< C$, the probability that we can reliably transmit any message using a random codebook drawn from the aforementioned distribution is nearly $1$ (which is certainly $> 0$). Thus, for large $n$, a good codebook (and hence a reliable code) exists for any $R < C$, which is often stated as "reliable communication is possible at any rate smaller than capacity."
As an aside, note that this argument shows more than what is needed by the probabilistic method, in that the chance that we can reliably transmit using a random code is nearly $1$, i.e., nearly every codebook from the specified distribution can be used for communication. However, in practice, we would not design codes by randomly drawing codewords. There are two issues, both to do with computational complexity: firstly, such a randomly picked codebook would have a highly optimal complex decoder, which is computationally infeasible to execute. Secondly, while for large enough $n$, good codebooks are very common indeed, it is computationally hard to verify in general that a given code is good. So, in practice, we would like codes that are large (i.e., 'capacity achieving') and computationally feasible decode and verify. Speaking somewhat crudely, finding such codes is the subject of coding theory, and the random codebook trick is ultimately only a proof technique used in information theory (although, it does inspires the design of some practical codes, at least in more sophisticated forms). Of course the two fields are deeply intertwined, but formally they care about different things. This is also why you might have encountered courses or books on Coding and Information Theory (in various permutations of the words).