Category Archives: Probability

Generating a random variable by coin tossing


1. Coin tossing Suppose we are given a sequence of independent fair bits (meaning take and with probabily ) we want to produce with them a discrete random variable that takes the values with probabilities . The objective, of course, … Continue reading

Posted in Algorithms, Number Theory, Probability | Leave a comment

Grading a class


Imagine we had a class with students and each week they hand in a sheet of homework. Now, you choose a set of of them at random and correct only those . At the end, the grade assigned to a … Continue reading

Posted in Asymptotics, Combinatorics, Computation, Probability | Leave a comment

Generating a random permutation


It is well-known that any permutation of can be written as a product of transpositions, that is, of permutations of the form with , where we recall that is the permutation satisfying and for . In this post however, we … Continue reading

Posted in Combinatorics, Computation, Probability | 1 Comment

Symmetric random walks


Definition 1 A symmetric random walk is a homogeneous Markov chain on the set of states such that with probability , and for all . In plain terms, this means that we start off at , and at each second … Continue reading

Posted in Computation, Probability | Tagged | Leave a comment

More on the Monkey typing problem


To compute the expected number of letters the monkey must type before our word turns up, we used   . It is clear that when the series on the left hand side converges, that is the result of the series, … Continue reading

Posted in Graph Theory, Linear Algebra, Probability | Leave a comment

Monkey typing!


I find this an amusing idea, you have a monkey typing on a keyboard and what we want to know is roughly how long we will have to wait for a certain word – a name for instance- to be … Continue reading

Posted in Probability | Leave a comment