Intereting Posts

Variant of Cauchy Functional Equation
Does there exist a CW complex with prescribed fundamental group and trivial higher homology?
From constrained to unconstrained maximization problem
When does l'Hospital's rule work for series?
$G$ a group s.t. every non-identity element has order 2. If $G$ is finite, prove $|G| = 2^n$ and $G \simeq C_2 \times C_2 \times\cdots\times C_2$
column space of positive semidefinite matrix
How can one prove that $\pi^4 + \pi^5 < e^6$?
Mathematical meaning of certain integrals in physics
Prove an inequality with a $\sin$ function: $\sin(x) > \frac2\pi x$ for $0<x<\frac\pi2$
Can morphisms in the category Set be partial functions?
How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$
A proof that BS(1,2) is not polycyclic
Field and Algebra
Probability that n points on a circle are in one semicircle
Formal definition for indexed family of sets

I am studying Randomized Algorithms chapter in the book “Introduction to Algorithms” by Cormen et al.

In this chapter the book introduces the concept of an indicator random variable and state that the expected value of an indicator random variable as :

- Is there a possibility to choose fairly from three items when every choice can only have 2 options
- How to find a “simple” fraction between two other fractions?
- Why is sorting pancakes NP hard?
- nth convolved Fibonacci numbers of order 6 modulo m
- Algorithm to find the exact roots of solvable high-order polynomials?
- How to find a closed form solution to a recurrence of the following form?

I am having difficulty understanding why this is called an **indicator random variable**, specifically why *indicator* and *random* and how this concept is useful in analyzing algorithm timings . It has been some time since I studied probability in school . However , I am aware of the concept behind probability. So you can base your answer on this premise.

As you can see from the diagram all it is saying is that the expected value of an indicator random variable of an event is equal to the probability of that event . We already have the concept of probability , why should we know about this new concept which happens to be the same value as the probability ?

- Is there any infinite set of primes for which membership can be decided quickly?
- Probability of asymmetric random walk returning to the origin
- Overlapping Probability in Minesweeper
- Choosing two random numbers in $(0,1)$ what is the probability that sum of them is more than $1$?
- Probability of two integers' square sum divisible by $10$
- A disease spreading through a triangular population
- Maximum amount willing to gamble given utility function $U(W)=\ln(W)$ and $W=1000000$ in the game referred to in St. Petersberg's Paradox?
- Show that $\prod (1- P(A_n))=0$ iff $\sum P(A_n) = \infty$
- What's the probability that we don't have $3$ consecutive heads in $n$ tosses?
- Tail sum for expectation

As the name implies, an *indicator* random variable indicates something: the value of $I_A$ is $1$ precisely when the event $A$ occurs, and is $0$ when $A$ does not occur (that is, $A^c$ occurs). Think of $I_A$ as a Boolean variable that indicates the occurrence of the event $A$. This Boolean variable has value $1$ with probability $P(A)$ and so its average value is $P(A)$. In terms of long-term frequencies, $I_A$ will have value $1$ on roughly $N\cdot P(A)$ of $N$ trials

of the experiment, and the long-term average value of $I_A$ on these

$N$ trials will be approximately

$P(A)$.

An indicator function is a function that returns the value of 1 when something is true: $$\mathbf{1}[A] = \left\{\begin{array}{cc} 1, & A\ \mathrm{ is\ true,} \\ 0, & A\ \mathrm{ is\ false.} \end{array}\right.$$

Therefore, the expectation is essentially the same thing as computing the expected value of a Bernoulli random variable: the value 1 times the probability that $A$ is true, plus the value 0 times the probability it is not.

- Are sines of primes dense in $?$
- What is the (mathematical) point of straightedge and compass constructions?
- Should an undergrad accept that some things don't make sense, or study the foundation of mathematics to resolve this?
- Vector Algebra Coordinate Transformation
- Inverse image sheaf and éspace étalé
- What are relative open sets?
- Confusion between operation and relation: Clarification needed
- Spherical harmonics for dummies
- (undergraduate) Algebraic Geometry Textbook Recommendations
- Did Galois show $5^\sqrt{2}$ can't solve a high-order integer polynomial?
- Assume that $f$ is uniformly continuous. Prove that $\lim_{x→∞} f(x) = 0.$
- The set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable?
- True Definition of the Real Numbers
- How many sorts are there in Terry Tao's set theory?
- How to find all rational points on the elliptic curves like $y^2=x^3-2$