PREFACE

Lecture 15: Statistics

• Random Variables and Expectation
  • Definition
  • Definition
  • Example
  • Example
  • Question
  • Expectation
    • Definition
    • Examples: dice
    • Examples: dice
• Linearity of Expectation
  • Theorem (linearity of expected value)
    • Example 1
    • Example 2
      • Answer 1. (the ‘hard way’)
      • Answer 2. (the ‘easy way’)
  • Observations
    • Exercises 1
    • Exercises 2
• Expected Time to Success
  • Expected time to success
    • Theorem
    • Exercise 1
    • Exercise 2
    • Success vs Expected value
      • Example
  • Gambler’s ruin
• Standard Deviation and Variance
  • Definition
  • example
  • exercise

Random Variables and Expectation

Definition

An (integer-valued) random variable X is a function from Ω to Z. In other words, it associates a number value with every outcome.

Random variables are often denoted by X,Y,Z,…

We extend arithmetic to random variables in the natural way.

Definition

Given random variable $X : Ω → Z$, random variable $Y : Ω → Z$ and integer k, we can combine X,Y and k to obtain the following functions on all $ω ∈ Ω$:

Addition of variables:

$$X +Y : ω→X(ω)+Y(ω)$$

Multiplication of variables:

$$X ·Y : ω→X(ω)·Y(ω)$$

Scalar addition:

$$X −k : ω→X(ω)−k$$

Scalar multiplication:

$$kX : ω→k·X(ω)$$

Example

Random variable X: value of rolling one die

Ω={1,2,3,4,5,6}

X(i) = i

Example

Random variable $X_s$: sum of rolling two dice

Ω={(1,1),(1,2),…,(6,6)}

$$X_s((1,1)) = 2, X_s((1,2)) = 3 = X_s((2,1)) ...$$

Question

Is $X_s = X +X$?

No! X_s 是两个独立随机变量的和，每次扔色子的结果是独立的。因此应该看下面这个等式。从写法上，X+X是自身相加，是相关的，因为两个X是同一个骰子自身的结果。

$$X_s(ω_1,ω_2) = X(ω_1)+Y(ω_2)$$

where $X : ω_1 → ω_1$ and $Y :ω_2 → ω_2$ are independent and identically distributed (i.i.d)

Expectation

Definition

The expected value (often called “expectation” or “average”) of a random variable X is

$$E(X)=\sum_{k \in \mathbb{Z}} P(X =k)·k$$

Take Notice

Expectation is a truly universal concept; it is the basis of all decision making, of estimating gains and losses, in all actions under risk. Historically, a rudimentary concept of expected value arose long before the notion of probability.

Examples: dice

The expected value when rolling one die is:

$$E(X) = \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 2 + \dots + \frac{1}{6} \cdot 6 = 3.5$$

The expected sum when rolling two dice is

$$E(X_s) = \frac{2}{36} \cdot 1 + \frac{2}{36} \cdot 3 + \dots + \frac{6}{36} \cdot 7 + \dots + \frac{1}{36} \cdot 12 = 7$$

Examples: dice

Question. Buy one lottery ticket for $1. The only prize is $1M. Each ticket has probability $6 · 10^{−7}$ of winning. What is the expected value of the lottery ticket?

Answer

There are two types of ticket, winning tickets and losing tickets, so we let Ω = {win,lose}, and $X_L : Ω → \mathbb{Z}$ such that $X_L(win) = $999,999$ and $X_L(lose)= −$1$ Then

$$E(X_L) = 6·10^{−7}·\$999,999+(1−6·10^{−7})·−\$1= −\$0.4$$

Linearity of Expectation

Theorem (linearity of expected value)

For any random variables X,Y and integer k:

$$E(X +Y)=E(X)+E(Y)$$ $$E(k · X) = k ·E(X)$$

Example 1

The expected sum when rolling two dice can be computed as

$$E(X_s) = E(X)+E(Y) = 3.5+3.5 = 7$$

Example 2

Question. Calculate $E(S_n)$, where

$$S_n \overset{def}{=} no. of \quad heads \quad \text{ in n coin tosses }$$

Answer 1. (the ‘hard way’)

Using the definition of the expectation, we have

$$E(S_n) = \sum^n_{k=0} P(S_n = k)·k = \sum^n_{k=0} \frac{1}{2^n} \binom{n}{k} \cdot k$$

Since there are $\binom{n}{k}$ sequences of n coin tosses with k heads, and each sequence has the probability $\frac{1}{2^n}$, this gives

$$E(S_n) = \frac{1}{2^n} \sum^n_{k=1} \frac{n}{k} \binom{n-1}{k-1} k = \frac{n}{2^n} \sum^{n-1}_{k=0} \binom{n-1}{k} = \frac{n}{2^n} \codt 2^{n-1} = \frac{n}{2}$$

where we used the ‘binomial identity’ $\sum^{n}_{k=0}=2^n$ to simplify.

Answer 2. (the ‘easy way’)

When n =1, we have that $S_1$ : {tails,heads} → {0,1} denotes the number of heads obtained in one coin toss.

For general n > 1, we can think of $Sn$ as being equivalent to repeating a single $S_1$ coin toss, n distinct (and independent) times. Let $S{1_i}$ denote coin toss number i in this sequence. Then

$$E(S_n) = E(S_{1_1} + S_{1_2} +...+S_{1_n} ) = \sum^{n}_{i=1} E(S_{1_i}) = n·E(S_1) = n \cdot \frac{1}{2}$$

Observations

Fact

If $X_1,X_2,…,X_n$ are independent, identically distributed (i.i.d) random variables, then $E(X_1+X_2+…+X_n) = E(nX_1) = nE(X_1)$.

Take Notice

$X_1 +X_2+…+X_n$ and $nX_1$ are very different random variables.

Exercises 1

Question.You face a quiz consisting of six true/false questions, and your plan is to guess the answer to each question (randomly, with probability 0.5 of being right). There are nonegative marks, and answering four or more questions correctly suffices to pass.

1. What is the probability of passing?

2. What is the expected score?

Exercises 2

Question. An urn has $m+n=10$ marbles, m≥0 red and n≥0 blue. 7 marbles selected at random without replacement. What is the expected numberof red marbles drawn?

Expected Time to Success

Question. Find the average waiting time for the first head, with no upper bound on the ‘duration’ (one allows for all possible sequences of tosses, regardless of how many times tails occur initially).

Answer. Let Ω be the sample space of all possible sequences of H and T.

Let $X_w : Ω →\mathbb{N}$ such that $X_w(ω)$ is the first location in ω containing an H (i.e. the waiting time for ω).For example $X_w(TTHTH···)=3$

Then the average waiting time is

$$A =E(Xw) = \sum^{\infty}_{k=1} k ·P(X_w =k) = \sum^{\infty}_{k=1} k \cdot \frac{1}{2^k} = \frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3} + \dots$$

Expected time to success

Theorem

If the probability of success is p then:

• The expected number of (indep.) trials before 1 success is $\frac{1}{p}$
• The expected number of (indep.) trials before k successes is $\frac{k}{p}$

Exercise 1

Question. Adieisrolled until the first 4 appears. What is the expected waiting time?

Answer

$$P(roll 4) = \frac{1}{6}$$

hence E(no. of rolls until first 4) = 6.

Exercise 2

Question. To find an object $X$ in an unsorted list L of n elements, one needs to search linearly through L. Let the probability of X ∈Lbe p. Then there is 1−p likelihood of X being absent altogether. Find the expected number of comparison operations.

Answer. If the element X is in the list, then the number of comparisons averages to $\frac{1}{n}(1+ \dots + n)$. If X is absent, we need n comparisons.

The first case has probability p, the second 1 − p. Combining these we find

$$E_n = p(\frac{1+ \dots + n}{n}) +(1−p)n \\ =p(\frac{n+1}{2})+(1−p)n \\ =(1-\frac{p}{2})n+\frac{p}{2}$$

As one would expect, increasing p leads to a lower $E_n$.

Success vs Expected value

Question

Does high probability of success lead to a high expected value?

Generally, no.

Example

Buying more tickets in the lottery increases your chances of winning, but the expected value of winnings decreases.

赢35块钱加上格子上的钱。因此策略2的概率p指向(35-24+1)=12$

Roulette (outcomes 0,1,…,36). Win: $35 × bet$

Strategy 1: Bet $1 on a single number

• Probability of winning: $\frac{1}{37}$
• Expected winnings: $\frac{1}{37}.($35)+\frac{36}{37}.(-$1)\approx −2.7c$

Strategy 2: Place $1 bets on 24 numbers, selected from among 0 to 36.

• Probability of winning: $\frac{24}{37} \approx 65\%$
• Expected winnings:
• • If one of the numbers comes up, win $35 from the bet on that number and lose $23 from the bets on the remaining numbers,

So expected winnings are:

$$p·\$12−q·\$24 = \$12 \frac{24}{37} −\$24 \frac{13}{37} = −\$ \frac{24}{37} ≈ −65c = 24×−2.7c$$

Gambler’s ruin

Many so-called ’winning systems’ that purport to offer a winning strategy do something akin — they provide a scheme for frequent relatively moderate wins, but at the cost of an occasional very big loss.

It turns out (it is a formal theorem) that there can be no system that converts an ‘unfair’ game into a ’fair’ one. In the language of decision theory, ‘unfair’ denotes a game whose individual bets have negative expectation.

It can be easily checked that any individual bets on roulette, on lottery tickets or on just about any commercially offered game have negative expected value.

Standard Deviation and Variance

Definition

For random variable X with expected value (or: mean) $µ = E(X)$, the standard deviation of X is

$$\sigma = \sqrt{E((X −µ)^2)}$$

and the variance of X is

$$\sigma^2$$

Standard deviation and variance measure how spread out the values of a random variable are. The smaller $σ^2$ the more confident we can be that $X(ω)$ is close to $E(X)$, for a randomly selected $ω$.

Take Notice

The variance can be calculated as $E((X − µ)^2) = E(X^2)−µ^2$, where $E(X^2) = \sum^{}_{k \in \mathbb{Z}} P(X = k)·k^2$

此处方差计算公式和我在中国学的方差计算公式，本质上是一样的，这里是简化的另一种形式。

example

Question. Let the random variable $X_d \overset{def}{=} value$ of a rolled die. What is(a)the mean, (b)the variance and (c) the standard deviation?

(a)

$$µ=E(X_d)=3.5$$

(b)

$$E(X_d^2)= \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 4 + \frac{1}{6} \cdot 9 + \frac{1}{6} \cdot 16+ \frac{1}{6} \cdot 25+ \frac{1}{6} \cdot 36 = \frac{91}{6}$$

Hence $\sigma^2=E(X_d^2)- \mu^2 = \frac{35}{12}$

(c)

$$\mu = \sqrt{ \frac{35}{12} } \approx 1.71$$

exercise

Question (Supp). Two independent experiments are performed.

$p_1$ = P(1st experiment succeeds) = 0.7

$p_2$ = P(2nd experiment succeeds) = 0.2. Random variable X counts the number of successful experiments.

• Expected value of X?
• Probability of exactly one success?
• Probability of at most one success?
• Variance of X?

Answer. For experiment i, let $X_i = 1$ if the experiment is successful and $X_i = 0$ otherwise.

(a) $E(X) = E(X1)+E(X2) = 1·p1 +1·p2 = 0.7+0.2 = 0.9$.

这里问的期望值，一次成功就是1，失败就是0.所以Omega是2，成功和失败是对立事件。因为两个实验是独立，且问的是成功的期望值，所以算和即可，不用考虑乘。成功是0.9，失败的期望值是0.3+0.8=1.1。

(b) $P(X = 1) = P(X1 =1,X2 = 0)+P(X1 =0,X2 = 1) =0.7·0.8 +0.3·0.2 = 0.62$.

(c) $P(X = 1)+P(X1 = X2 =0) =0.62+0.3·0.8 = 0.86$.

(d) $σ^2 = E(X^2)−E(X)^2 = (0.62·1+0.14·4)−0.92 = 0.37$.

成功一次的期望值是1，概率是(c)中结果；成功两次的期望值是2，概率是 0.7*0.2。

---

Welcome to point out the mistakes and faults!