gamblers problem cs320

What is the probability that two specific elements zi and zj are compared in Quicksort?

2 / (j - i + 1)

What is the average number of comparisons in Quicksort related to the harmonic series?

O(log n)

What is the expected number of clauses to re-evaluate in MAX-3SAT when flipping one variable?

A constant number, O(1)

How many times does each variable appear in MAX-3SAT (4N clauses, 3 variables per clause)?

Each appears in 12 clauses

What is the average case work to evaluate all variables in MAX-3SAT?

O(1) per variable, O(n) total worst case

What is a random walk?

A value sequence that moves up/down/stays the same over time steps

What makes a random walk "unbiased"?

Equal probability of going up or down

What is Gambler’s Ruin?

A gambler makes 1-dollar bets until reaching a target profit or going broke

What is T in Gambler’s Ruin?

T = starting capital + target winnings

In roulette, what is the probability of winning on a color bet?

18 / 38 ≈ 0.47

What are the absorbing states in the Gambler’s Ruin problem?

$0 (broke) and target capital (e.g., $600)

Is the Gambler’s Ruin process a martingale?

Yes, because outcomes are independent of past events

What is the approximate chance of winning $100 starting from $500 in roulette?

Less than 1 in 37,000

What happens in the doubling betting strategy?

You win 100 with 71.91% chance but lose 300 with 28.09% chance

What is the birthday paradox?

Probability that at least 2 people share a birthday in a group

How many people are needed for >50% chance of a shared birthday?

23 people

What’s the probability of at least one shared birthday with 50 people?

96.53%

How is the number of pairs of people calculated?

n(n-1)/2

In the randomized ONEMAX problem, how long to find one 'A' in a string of n bits?

O(n)

What’s the average time to convert all A’s to G’s in ONEMAX?

O(n log n)

How is progress in ONEMAX often modeled?

Using harmonic series

What is the sum of the harmonic series Hn?

O(log n)