On Probability and Random Variable

[This is an edited version of my answer on Quora to the question - "What is a Random Variable?"]

Why should I care about this? 

There are a LOT of very commonly used algorithms and data structures that make extensive use of Randomness. These are called Randomized Algorithms. A very common example is Quicksort. The most commonly employed version of quicksort is the Randomized Quicksort. Another common data structure that utilizes randomness is the Bloom Filter.

Random Variable is a tool to analyze the running time of a randomized algorithm, or to reason about the insertion, deletion and query times of a randomized data structure.

Introduction

So you want to understand what a Random Variable is!

I will try to explain in simple language without any notation. The only take-away terms you need to remember and keep in mind as you read are underlined below. I promise that if you pay attention and read this post carefully, nobody can stop you from understanding what a Random Variable is, and you might also pick up some Probability 101 along the way!

Keep in mind that all the analysis and all of the following ideas are with respect to some Experiment. Examples of experiments are:

• rolling a dice
• flipping a coin,
• or doing something that results in many possible outcomes. 

Probability 101

In Probability Theory, there is a concept of a Probability Space. Probability Space is a fancy term consisting of three things:

1. A Sample Space, or the set of all possible outcomes of an experiment. For example, if you roll a dice, the set of all possible outcomes - {1,2,3,4,5,6} is the Sample Space.
2. Events. An event is a set of 0 or more outcomes. Nothing special, just a set of outcomes. For example, an event the dice example could be - getting a even number : {2,4,6}. Or, getting a number which is a factor of 4 : {1,2,4}. An event is said to have occurred if an outcome is part of that event. For example, if you get a 4, both the above events are said to have occurred. That is, you got both an even number and a factor of 4. So one outcome can cause multiple events to occur. 
3. A probability function - which associates every outcome with a probability. For example, if you flip a coin, the outcomes are H or T. And the probability of both the outcomes is a 1/2. But if a coin is biased, the probabilities might not be equal. So there's a function called the Probability function maps each outcome to a probability.

So, those three things consist of a Probability Space. Take a moment to internalize this.

Value/Measure and Random Variable

Now let's talk about a notion of a 'Value' associated with each outcome. For every outcome of an experiment, we can associate a measure or a value. For example, if you roll a dice, you may say that the value associated with a outcome is the number you get on the dice. In case of a single dice, this notion of a Value might not make much sense. But let's think of two dice. One possible outcome on rolling two dice can be - {2,4}. What value can you associate with this? It is really up to you and will depend on the setting. For example, you may decide to associate the value 6 (which is the sum of the two numbers) or 8 (product of the two numbers). Multiple outcomes can give the same value.

In another experiment of randomly picking students from a college classroom, the outcomes are the students you pick (for example, you pick a student named Sandra), then the value you may associate with her could be: Her 'height' on a scale of 1-10, or her 'IQ' on a scale of 50-100, or the number of siblings she has. The values or measure is something you decide depending on what the experiment is about.

Notice that the Value is not the same as Probability. Value is something you chose. Keep this in mind as you read further.

From the above discussion, you should agree that we can associate a specific value (or a measure) with each outcome. This association (assigning a value to each outcome) can be thought of a function that maps an outcome to a value. 

foo(Outcome) = Value  

This function - foo - takes in an Outcome, and outputs a Value.

This association or mapping or function (foo in this case) that tells you what the value is for each outcome is known as a Random Variable. The Random Variable (generally denoted with an upper-case X) is a mapping that can take specific values. 

Now pay attention:

You generally see stuff like Pr[X = x] = k in books and papers.

What this means is there was some outcome (you don't know what that outcome is, and it's not important), but the 'Value' associated with that outcome was x. And because the outcome itself has a probability associated with it (remember, each outcome can occur with some probability, and the probability function describes what that probability is), there is a "probability that the Random Variable will take a particular value", which here is 'k'

Another way of reading that equation is, Probability that a function foo or X (which is the Random Variable) will return a value 'x' is 'k'.

So Random Variable is nothing but a mapping, and you generally look at specific values of the mapping and argue about its probability.

An Indicator Random Variable a special Random Variable that can have only two values. The sample space of outcomes (or events) is only Yes or No. If the event occurs, the "value" associated is 1 otherwise 0. 

Why such a confusing name?

An Intuitive reason why a Random Variable is called a Random Variable (and not a function) is because if you're doing an experiment, the pattern of outcomes is unpredictable - that is, you can never say with 100% guarantee about what is going to be the next outcome. Ofcourse if you repeat the experiment an infinite amount of times, the distribution of the outcomes will follow the probability distribution, but the individual outcomes themselves are sort of Random.

This is it, you now know what a Random Variable is!

Expectation

Since there is a value associated with the Random Variable, there is this notion of an "Expected Value". For example, if you're rolling dice (the experiment) and you were to win as many dollars as the number you get on the dice, you may be interested in the "expected" dollars you will earn in the first 3 dice rolls, or first 10 dice rolls etc. That is the intuition, but the term 'Expectation' has a formal definition.. The idea of Expectation has wide application, and is also used in the analysis of algorithms, esp Randomized Algorithms. For example, 'What is the running time of Quicksort 'in Expectation'? 

Next Steps

Try to read this wikipedia article - https://en.wikipedia.org/wiki/Expected_value

---------------------------

Header Image courtesy - http://brainzooming.com/wp-content/uploads/2013/12/Rolling-Dice.jpg