Math Empirical

Question 1

bias-variance tradeoff

illustrate BVT: true data y; model h(X)

Answer 1

E[(y-h)²]

= E[(y-E[y])²] + (E[y] - E[h])² + E[(h-E[h])²]

= Var(y) + (E[y] - E[h])² + Var(h)

= noise + bias + variance

Question 2

simulate triangle

how would you simulate the distribution of points on a triangular region in the plane?

Answer 2

triangle (x0,y0), (x1,y1), (x2,y2)

1. simulate on triangle (0,0), (0,1), (1,0): x, y ~ Unif(0,1), if y > -x + 1, x = -x + 1, y = -y + 1
2. transform and translate: [x1-x0,x2-x0;y1-y0,y2-y0][x;y] + [x0;y0]

Question 3

roll die with cost

Roll a die and get $i; can pay $1 to reroll, can reroll inf times. What’s the strategy and what’s the EV?

Answer 3

Reroll if i = 1 or 2: EV = 2/3(4.5) + 1/3(EV-1) –> EV = 4

Question 4

sum of uniforms

What’s the expected number of U~unif(0,1) such that their sum first exceeds 1?

Answer 4

Let S[n] = sum of n U’s

P(S[n] < 1) = 1/n!

P[N=n] = P(S[n-1] < 1 and S[n] >= 1) = 1/(n-1)! - 1/n! = (n-1)/n!

E[N] = sum_n=0..inf [nP[N=n]] = sum_n=0..inf [1/n!] = e

Question 5

change bases

given 1 balance, how many unique weights are needed to weigh items with w=1…N? what if you could have k copies of each weight?

Answer 5

we can represent any number as sum_i=1..m x*3ⁱ, x in {-1,0,1}

thus the weights are {3⁰, 3¹, … 3^m} where m = min sum_i=1..m 3ⁱ >= N –> m = log_3(2N+1) - 1

for k copies, replace 3 with 2k+1

Question 6

super egg drop

with F floors and K eggs, what’s the min worst case # drops to determine which floor the egg breaks on? Write out init and dp steps

Answer 6

init: dp[f][1] = f; dp[0][k] = 0, dp[1][k] = 1
dp: dp[f][k] = 1 + min(max(dp[i-1][k-1], dp[f-i][k] for 1<=i<=f))

Question 7

bid item

seller values item s~N(0,1) and you value item at y = 1.8s. How should you bid?

Answer 7

Say you bid x and win: E[s] = 0.5x, and E[y] = 1.8E[s] = 0.9x < x, so you should not bid at all.

Question 8

distance on unit sphere

what’s the expected distance (in 3D, not on surface) of any point on a unit sphere’s surface to the sphere’s north pole?

Answer 8

p(point on ring) = 2πdx/4π = 1/2 dx

d(point on ring, north pole) = sqrt(x² + (1-(x-1)²) = sqrt(2x)

E[point on sphere, north pole) = integrate_x=0..2 sqrt(2x) 1/2 dx = 4/3

Question 9

stick breaking

break a stick into 3 pieces:

1. what’s the probability that they form a triangle?
2. what’s the expected length of the middle part?

Answer 9

1. Plot: 0<=x,y<=1

• min(x,y) <= 1/2
• max(x,y) >= 1/2
• |x-y| <= 1/2

Area = 1/4

2. integrate_x=0..1 x(x/2) + (1-x)(1-x)/2 dx = 1/3

Question 10

arrival time

A and B each arrive t ~ U(0,1) hr and stay for 1/2 hr, what’s the probability that they meet?

Answer 10

Plot: 0<=x,y<=1, |x-y| <= 1/2 –> Area = 3/4

Question 11

ant on cube

What’s the expected number of steps for ant to go from one corner of cube to opposite corner of cube?

Answer 11

x1 = 1 + x2

x2 = 1 + 1/3 x1 + 2/3 x3

x3 = 1 + 2/3 x2 + 1/3 x4

x4 = 0

–> x1 = 10

Question 12

simulate fair coin

how to used a biased coin to simulate a fair coin?

Answer 12

naive: 2 flips at a time, HT/TH –> 1/0, HH/TT –> continue; E[flips] = 2 * 1/2pq = 1/pq
optimized: at kth flip, if kC(#H) is even, X[k] = H/T –> 1/0; odd –> continue

Question 13

ball sequence

N white and N black balls, randomly ordered. what’s the expected # color switches? what’s the expected # color runs?

Answer 13

let Xi = color switch between (i, i+1)

E[# color switches] = E[Σ_i=1..2N-1 Xi] = (2N-1) (N/2N * N/(2N-1) * 2) = N

E[# color runs] = E[# color switch] + 1 = N + 1

Question 14

coin flips

1. what’s x[N] = E[# adj H in N flips]?
2. what’s x[N] = E[# flips to get N consecutive H]?

Answer 14

1. x[N] = 1/2 x[N-1] + 1/2 (1/2 x[N-1] + 1/2 (x[N-1] + 1)); x[2] = 1/4 –> x[N] = (N-1)/4
2. x[N] = 1/2 (x[N-1] + 1) + 1/2 (x[N-1] + 1 + x[N]); x[N] = 0 –> x[N] = 2^N+1 - 2

Question 15

draw with replacement

draw N numbers from {1…N} with replacement, what’s the expected # distinct numbers?

Answer 15

N(1 - ((N-1)/N)^N)

Question 16

max seq length

a sequence of numbers, all MA(8) > 0 and all MA(5) < 0, what’s the max length of this sequence?

Answer 16

Write numbers in a 8x5 grid, get contradiction where all rows < 0 and all columns > 0. Hence max length is 8 + 5 - 1 = 11

Question 17

dice sum

roll dice continuously, what’s the probability that the sum hits exactly 100?

Answer 17

P(1) = 1/6

P(2) = 1/6 + 1/6 P(1)

P(3) = 1/6 + 1/6 P(2) + 1/6 P(1)

…

P(6) = 1/6 + 1/6 P(5) + … 1/6 P(1)

P(7) = 1/6 P(6) + … + 1/6 P(1)

P(n) = 1/6 Σ_i=1..6 P(i) = Σ_i=0..5 (n-1)Ci 6^n-i

Question 18

guess coin

2 people each flip a coin and guess each other’s result, how to maximize probability that both are correct?

Answer 18

random guess: p = 1/4

guess own coin: p = 1/2

Question 19

draw ball

n-1 red balls, 1 blue ball. 2 people take turns drawing w/o replacement, and win if draw blue. does the 1st person have an advantage?

Answer 19

same as lining up the balls and see if blue is at odd or even index.

if n even, P1 = P2; if n odd, P1 = P2 + 1/n > P2

Question 20

languages

70 people in total, for every pair, i knows a language that j doesn’t and vice versa. at least how many languages in total?

Answer 20

k language / person: solve for min n s.t. nC1 >= 70

k = 1, n = 70

k = 2, n = 13

k = 3, n = 9

k = 4, n = 8

k = 5, n = 9

…

Question 21

survivor

n people (i=0..n-1) in a circle, #0 shoots #1, #2 shoots #3, and so on. who survives in the end?

Answer 21

if n = 2^k, then i=0 survivies

else, once n is reduced to n = 2^k, the next person survives

So idx = 2(n - 2^m), where 2^m is max 2^m s.t. 2^m <= n

Question 22

birthday problem

in a long line, the 1st person to have a shared birthday as someone before him wins. where to stand?

Answer 22

P(N) = prob(no shared birthday in N people) = 365*364*..*(365-n+1) / 365^n = 365Pn / 365^n

argmax P(i) i/365 = 19 –> stand in 20th place

Question 23

sample from disk

how to sample uniformly from a disk with radius R?

Answer 23

x1, x2 ~ Unif(0,1)

theta = 2πx1

r = R sqrt(x2)

–> pdf f(r) = 2r/R²; cdf F(r) = r²/R²; F^-1(x) = R sqrt(x)

Question 24

coin flip

flip n coins, Pi = 1/(2i+1) for i = 1…n. What’s P(#H is odd)?

Answer 24

P[i] = P[i-1] (1 - 1/(2i+1)) + (1 - P[i-1]) 1/(2i+1) = P[i-1] (2i-1)/(2i+1) + 1/(2i+1)

P[0] = 0

P[n] = n / (2n+1)

Question 25

strategy returns each day a strategy either gains 50% (p=0.6) or loses 50% (q=0.4). What's P (pnl \> 0 after n days)? What n maximizes P?

Answer 25

1.5^k 0.5^(n-k) = 1 --\> k = ceil(n ln2/ln3) X ~ Bin(n, p) --\> P(X \> k) = P(X \> ceil(n ln2/ln3)) for p = 0.6, n = 260: k = 165, P = 14% for general n, P is maximized for n = 3

Question 26

expected flips what's the expected flips to get 1) HH? 2) HT?

Answer 26

Markov Chain: 1) x[HH] = 0; x[H] = 1 + 1/2 x[T] + 1/2 x[HH]; x[T] = 1 + 1/2 x[T] + 1/2 x[H] --\> x[T] = 6 2) x[HT] = 0; x[H] = 1 + 1/2 x[H] + 1/2 x[HT]; x[T] = 1 + 1/2 x[T] + 1/2 x[H] --\> x[T] = 4

Question 27

function if f(x) - f(y) \<= (x-y)^2 for all x,y, what do we know about f(.)?

Answer 27

let z = f(x) - f(y); -z = f(y) - f(x) z \<= (x-y)^2; -z \<= (x-y)^2 --\> z = -z = 0 --\> f(.) = constant

Question 28

buy/sell stocks you know daily stock return for the next T days: R you can hold 0 or 1 shares on day 1..T-1 and 0 shares on day T buy/sell incurs c% tcost what's the max wealth you can gain?

Answer 28

let L[t], R[t] = max wealth at day t if you hold 1 / 0 shares at day t L[0] = N[0] = 0 L[t] = max((1+R[t])L[t-1], (1-c%)(1+R[t])N[t-1]) N[t] = max(N[t-1], (1-c%)L[t-1]) ans = max(N[T], (1-c%)L[T])

Question 29

sum children Given a root n \> 1: for each node k \> 1, else split into x and k-x. Find the sum of all these x(k-x)

Answer 29

base step: S(2) = 1\*1 = 2, S(3) = 1\*1 + 1\*2 = 3 induction step: S(n) = n(n-1)/2