Home » Basic probability » Indicator functions

Category Archives: Indicator functions

Dinner Party Seating

A host invites \(n\) guests to a party (guest #1, guest #2, … , guest #n). Each guest brings with them their best friend. At the party there is a large circular table with \2n\) seats. All of the \(n\) invited guests and their best friends sit in a random seat.

  1. What is the probability that guest #1 is seated next to their best friend?
  2. What is the expected number of the \(n\) invited guests who are seated next to their best friend?

A Dice Rolling Game

15 players each roll a fair 6-sided die once. If two or more players roll the same number, those players are eliminated. What is the expected number of players who get eliminated?

Another Birthday Problem

A host invites guests to a party. How many guests should be invited in order for the expected number of guests who share a birthday with at least one other guest to be at least 4?

Handing back tests

A professor randomly hands back test in a class of \(n\) people paying no attention to the names on the paper. Let \(N\) denote the number of people who got the right test. Let \(D\) denote the pairs of people who got each others tests. Let \(T\) denote the number of groups of three who none got the right test but yet among the three of them that have each others tests. Find:

  1. \(\mathbf{E} (N)\)
  2. \(\mathbf{E} (D)\)
  3. \(\mathbf{E} (T)\)

Indicator Functions and Expectations – II

Let \(A\) and \(B\) be two events and let \(\mathbf{1}_A\) and \(\mathbf{1}_B\) be the associated indicator functions. Answer the following questions in terms of \(\mathbf{P}(A)\), \(\mathbf{P}(B)\), \(\mathbf{P}(B \cup A)\) and \(\mathbf{P}(B \cap A)\).

  1. Describe the distribution of \( \mathbf{1}_A\).
  2. What is \(\mathbf{E} \mathbf{1}_A\) ?
  3. Describe the distribution of \(\mathbf{1}_A \mathbf{1}_B\).
  4. What is \(\mathbf{E}(\mathbf{1}_A \mathbf{1}_B)\) ?

The indicator function of an event \(A\) is the random variable which has range \(\{0,1\}\) such that

\[ \mathbf{1}_A(x) = \begin{cases} 1 &; \text{if $x \in A$}\\ 0 &; \text{if $x \not \in A$} \end{cases}\]

The Coupon-Collector

Suppose that there are \(N\) different types of coupons. Each box contains one coupon. The type of the coupon is chosen uniformly among \(\{1,2,\cdots,N\}\).

  1. If we open \(k\) boxes what is the expected number of different  coupons thus we will find ? What is the limit  of this quantity as \(k \rightarrow \infty\) ?
  2. Let \(T_k\), for \(k=1,\cdots,N\), be the number of boxes needed to obtain the \(k\)th unique type of coupon. Clearly \(T_1=1\) . For future reference define \(\tau_1=1\) and \(\tau_k=T_k- T_{k-1}\) for \(k=2,3,\cdots\).
    1. What is the distribution of \(\tau_k\) ?
    2. What is the expected value of \(T_N\) ? What is it approximately for \(N\) large ?
    3. What is the variance of \(\mathbf{Var}(T_N) \)?
    4. Show that \(\mathbf{SD}(T_N)  < cn \) from some constant \(c>0\).
    5. Use Chebychev’s inequality to show that the probability that for large \(N\), \(T_N\) differs from \(N\log(N)\)  by at most only a small multiple of \(N\) with high probabilty.
  3. (***) What is the distribution of \( (T_N- N\log(N) \,)/N\) as \(N\rightarrow \infty\) ? Hint: It is not normal !

Indicator Functions

Let \(A\) and \(B\) be independent events. Let \(\mathbf{1}_A\) and \(\mathbf{1}_B\)  be the associated indicator random variables.

  1. Describe the random variable \(\mathbf{1}_A+ \mathbf{1}_B \) in terms of  \(\mathbf{P}(A)\) and \(\mathbf{P}(B)\) ?
  2. Calculate \(\mathbf{E}(\mathbf{1}_A+ \mathbf{1}_B )\).
  3. Describe the random variable \((\mathbf{1}_A+ \mathbf{1}_B )^2\) in terms of  \(\mathbf{P}(A)\) and \(\mathbf{P}(B)\) ?
  4. Calculate \(\mathbf{E}\big( (\mathbf{1}_A+ \mathbf{1}_B )^2 \big)\).

[Partially inspired by Pitman p182, #10]

 

Stuffing Envelopes

You write a stack of thank you cards for people who gave you presents for your birthday. You address all of the envelopes but before you can stuff them you are called away.  A friend tying to help you see the stack of cards and stuffs them in the envelops. Unfortunately they did not realize that each card was personalized and just stick them in the envelops randomly. Assuming there were \(n\) cards and \(n\) envelops, let \(X_{n}\) be the number of cards in the correct envelope.

  1. Find \(\mathbf{E} (X_n)\).
  2. Show that the variance of \(X_n\)  is the same as  \(\mathbf{E} (X_n)\).
  3. Is there any common distribution which has the above statistics ?
  4. (**) Show that
    \[ \lim_{n\rightarrow \infty} \mathbf{P}(X_n =m) = \frac{1}{e\, m!}\]

Indicatior functions and expectations

Let \(A\) and \(B\) be independent events and let \(\mathbf{1}_A\) and \(\mathbf{1}_B\) be the associated indicator functions. Answer the following questions in terms of \(\mathbf{P}(A)\) and \(\mathbf{P}(B)\).

  1. Describe the distribution of \( \mathbf{1}_A\).
  2. What is \(\mathbf{E} \mathbf{1}_A\) ?
  3. Describe the distribution of \((\mathbf{1}_A +\mathbf{1}_B)^2\).
  4. What is \(\mathbf{E}(\mathbf{1}_A +\mathbf{1}_B)^2 \) ?

Topics