L8 01 Geometric Random Variables

geometric random variable

__ describes the number of trials performed until the first successful trial in a series of independent trials, each with a success probability (p).

What is the expected value of a geometric random variable?

The expected value is (1/P), where (p) is the probability of success.

How does the expected number of trials relate to the probability of success?

If the probability of success is (p), the expected number of trials until success is at most (1/P).

What is a practical example of a geometric random variable?

Rolling a dice until a 3 appears, where the expected number of rolls is 6 since (p = 1/6).

What are indicator random variables?

Indicator random variables are used to indicate whether a specific event occurs, and their expected value is the probability of that event.

How can you calculate the expected value of a geometric random variable using indicator variables?

Decompose the geometric random variable into a sum of indicator random variables that indicate whether the algorithm is still running at each iteration.

What is the significance of the Monte Carlo randomized algorithm in this context?

Monte Carlo algorithm can fail, but if they succeed with probability (p), the expected number of trials until success is at most (1/p).

How can geometric series be summed up?

By using a technique called shifting, where you multiply the series by its common ratio and subtract to simplify the sum.

What is the probability of success when sampling uniformly from a circle using a square?

The probability of success is (pi /4), which is the ration of the area of the circle to the area of the enclosing square.

What happens to the efficiency of sampling from high-dimensional spheres?

The ratio of the volume of an n-dimensional sphere to its enclosing n-dimensional cube tends to zero as dimensionality increases, making it inefficient to sample from high-dimensional spheres.

How can you sample a random point from the surface of a unit sphere in a (n) dimensions?

By picking each component of a vector independently from a Gaussian distribution and then normalizing the vector.

What is a key principle to remember when dealing with high-dimensional spheres?

Non-intuitive behaviors occur in high-dimensional, such as most of the mass of a high-dimensional sphere residing in a thin shell near the surface.

What is the relationship between independent trials and geometric random variables?

Geometric random variables arise from independent trials where each trial has the same probability of success.

How does the concept of linearity of expectation apply to geometric random variables?

The expected value of a sum of random variables is the sum of their expected values, allowing for the calculation of the expected value of geometric random variables through their indicator components.

What is the formula for the probability of failure in single trial?

The probability of failure in a single trial is (1 - P), where (p) is the probability of success.

How can the expected number of trails until success be derived mathematically?

By summing the probabilities of failure for each trial until the first success occurs, leading to a geometric series.

What is the significance of the are ration (pi / 4) in sampling from a circle?

It represents the probability of a dart landing in the circle when thrown at the enclosing square, which informs the expected number of trials needed for successful sampling.

Why is sampling from high-dimensional spaces challenging?

As dimensionality increases, the volume of the sphere becomes negligible compared to the volume of the enclosing cube, leading to inefficiencies in sampling.

What is a common method for generating random points on the surface of a high-dimensional sphere?

Generating a random vector from a multivariate Gaussian distribution and normalize to obtain a point on the sphere's surface.

What should be considered when designing algorithms that involve high-dimensional objects?

One should be cautious of non-intuitive properties and behaviors that arises in high dimensions, as they can significantly affect algorithm performance.