In this chapter, we review random encoding models that directly reduce the dimensionality of distributional data without first building a co-occurrence matrix. While matrix distributional semantic models (DSMs) output either explicit or implicit distributional vectors, random encoding models only produce low-dimensional embeddings, and emphasize efficiency, scalability, and incrementality in building distributional representations. We discuss the mathematical foundation for models based on random encoding, the Johnson-Lindenstrauss lemma. We introduce Random Projection, before turning to Random Indexing and BEAGLE, a random encoding model that encodes sequential information in distributional vectors. Then, we introduce a variant of Random Indexing that uses random permutations to represent the position of the context lexemes with respect to the target, similarly to BEAGLE. Finally, we discuss Self-Organizing Maps, a kind of unsupervised neural network that shares important similarities with random encoding models.