320 Prove that the average value of
(a) n2 as n varies over nat+1 according to probability 2–n is 6 . § Lemma 0:
Σn: nat+1· 2–n
= (Σn: nat· 2–n) – 2–0
= (Σn: nat+1· 2–(n–1)) – 1
= (Σn: nat+1· 2–n×2) – 1
= 2×(Σn: nat+1· 2–n) – 1 Lemma 1:
⊤
= (Σn: nat+1· 2–n) = 2×(Σn: nat+1· 2–n) – 1
= (Σn: nat+1· 2–n) = 1
and therefore, as n varies over nat+1 , 2–n is a distribution. Lemma 2:
Σn: nat+1· n×2–n
= Σn: nat· n×2–n
= Σn: nat+1· (n–1)×2–(n–1)
= 2×(Σn: nat+1· n×2–n) – 2×(Σn: nat+1· 2–n)
= 2×(Σn: nat+1· n×2–n) – 2 Lemma 3:
⊤
= (Σn: nat+1· n×2–n) = 2×(Σn: nat+1· n×2–n) – 2
= (Σn: nat+1· n×2–n) = 2 Lemma 4:
Σn: nat+1· n2×2–n
= Σn: nat· n2×2–n
= Σn: nat+1· (n–1)2×2–(n–1)
= 2×(Σn: nat+1· n2×2–n) – 4×(Σn: nat+1· n×2–n) + 2×(Σn: nat+1· 2–n)
= 2×(Σn: nat+1· n2×2–n) – 4×2 + 2
= 2×(Σn: nat+1· n2×2–n) – 6 Lemma 5:
use Lemma 0
use Lemma 1 use Lemma 2
Lemmas 1 and 3
use Lemma 4 The average value of n2 as n varies over nat+1 according to distribution 2–n is
⊤
= (Σn: nat+1· n2×2–n) = 2×(Σn: nat+1· n2×2–n) – 6
= (Σn: nat+1· n2×2–n) = 6
2–nʹ. n2
= Σnʹʹ: nat+1· 2–nʹʹ×nʹʹ2
=6
(b) n as it varies over nat according to probability (5/6)n × 1/6 is 5 . § Lemma 6:
Σn: nat· (5/6)n
= 1 + Σn: nat+1· (5/6)n
= 1 + Σn: nat· (5/6)n+1
= 1 + 5/6 × Σn: nat· (5/6)n Lemma 7:
⊤
use Lemma 5
= (Σn: nat· (5/6)n)
= (Σn: nat· (5/6)n)
= (Σn: nat· (5/6)n)
and therefore, as n varies over nat , (5/6)n × 1/6 is a distribution.
use Lemma 6
= 1 + 5/6 × (Σn: nat· (5/6)n) = 1 / (1 – 5/6)
= 6
Lemma 8:
Σn: nat· (5/6)n × n
= 0 + Σn: nat+1· (5/6)n × n
= Σn: nat· (5/6)n+1 × (n+1)
= 5/6 × (Σn: nat· (5/6)n × n) + 5/6 × (Σn: nat· (5/6)n)
use Lemma 7
use Lemma 8
= 5/6 × (Σn: nat· (5/6)n × n)
= 5/6 × (Σn: nat· (5/6)n × n) Lemma 9:
⊤
+ 5/6 × 6 + 5
= (Σn: nat· (5/6)n × n)
= (Σn: nat· (5/6)n × n)
= (Σn: nat· (5/6)n × n)
The average value of n as it varies over nat according to distribution (5/6)n × 1/6 is
(5/6)nʹ × 1/6. n
= Σnʹʹ: nat· (5/6)nʹʹ × 1/6 × nʹʹ
= 1/6 × Σnʹʹ: nat· (5/6)nʹʹ × nʹʹ use Lemma 9 = 1/6×30
=5
= 5/6 × (Σn: nat· (5/6)n × n) + 5 = 5 / (1 – 5/6)
= 30