You have access to rand5(), which returns an integer in {1,2,3,4,5} uniformly at random. A) Implement rand7() that returns {1..7} uniformly using only calls to rand5(). Your solution must be correct (unbiased), terminating, and near-optimal in expected number of rand5() calls. Prove uniformity and compute the exact expected number of rand5() calls your construction uses. B) Generalize: given randM() (uniform over {1..M}), implement randN() (uniform over {1..N}) for arbitrary positive integers M and N. Describe an algorithm that is correct for all M,N, and derive an upper bound on the expected number of randM() calls in terms of M and N. Discuss how you would adapt when N≫M and when M≫N. C) Biased source: given toss(p) which returns 1 with unknown probability p∈(0,1) and 0 otherwise, construct fair_coin() that returns 0/1 with equal probability, prove correctness, and derive the expected number of tosses as a function of p. Then extend your approach to sample uniformly from {1..K} using only toss(p). Analyze termination and expected complexity.

This question evaluates understanding of random number generation, probability theory, and algorithmic reduction techniques for producing unbiased samples from constrained or biased primitives, along with proof of correctness and expected-cost analysis.

How do I approach Statistics & Math interview questions?

Statistics & Math questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master statistics & math interviews.

What difficulty level is this interview question?

This is a hard difficulty Statistics & Math question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Snowflake during technical interviews.

Derive uniform RNGs from limited or biased sources

Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source

You have access to a uniform primitive randM() that returns an integer in {1, 2, ..., M} and (in part C) a biased primitive toss(p) that returns 1 with unknown probability p ∈ (0, 1) and 0 otherwise.

A) rand7() from rand5()

Task: Implement rand7() that returns a value uniformly from {1, ..., 7} using only calls to rand5().
Requirements: unbiased (exact), almost surely terminating, and near-optimal in expected rand5() calls.
Deliverables: (i) a correct construction; (ii) a proof of uniformity; (iii) the exact expected number of rand5() calls.

B) General randN() from randM()

Task: For arbitrary positive integers M and N, construct randN() from randM().
Requirements: correctness for all M, N; almost sure termination.
Deliverables: (i) an algorithm; (ii) an upper bound on the expected number of randM() calls in terms of M and N; (iii) discuss adaptations when N ≫ M and when M ≫ N.

C) Fairness from a Biased Source

Given toss(p) that returns 1 with unknown probability p and 0 otherwise:
1. Construct fair_coin() that returns 0/1 with probability 1/2 each. Prove correctness and derive the expected number of tosses as a function of p.
2. Extend to sample uniformly from {1, ..., K} using only toss(p). Analyze termination and expected complexity.

Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source

A) rand7() from rand5()

Task: Implement rand7() that returns a value uniformly from {1, ..., 7} using only calls to rand5().

Requirements: unbiased (exact), almost surely terminating, and near-optimal in expected rand5() calls.

Deliverables: (i) a correct construction; (ii) a proof of uniformity; (iii) the exact expected number of rand5() calls.

B) General randN() from randM()

Task: For arbitrary positive integers M and N, construct randN() from randM().

Requirements: correctness for all M, N; almost sure termination.

Deliverables: (i) an algorithm; (ii) an upper bound on the expected number of randM() calls in terms of M and N; (iii) discuss adaptations when N ≫ M and when M ≫ N.

C) Fairness from a Biased Source

Given toss(p) that returns 1 with unknown probability p and 0 otherwise:

Construct fair_coin() that returns 0/1 with probability 1/2 each. Prove correctness and derive the expected number of tosses as a function of p.
Extend to sample uniformly from {1, ..., K} using only toss(p). Analyze termination and expected complexity.

Derive uniform RNGs from limited or biased sources

Quick Overview

Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source

Solution

Comments (0)

Derive uniform RNGs from limited or biased sources

Quick Overview

Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source

Solution

Comments (0)