Category Archives: Indicator functions

Dinner Party Seating

Posted on October 29, 2022 by | Comments Off on 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?

Comments Off on Dinner Party Seating

Posted in Expectations, Indicator functions

A Dice Rolling Game

Posted on October 29, 2022 by | Comments Off on 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?

Comments Off on A Dice Rolling Game

Posted in Expectations, Indicator functions

Another Birthday Problem

Posted on October 29, 2022 by | Comments Off on 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?

Comments Off on Another Birthday Problem

Posted in Expectations, Indicator functions

Handing back tests

Posted on February 27, 2015 by | Comments Off on 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)\)

Comments Off on Handing back tests

Posted in Expectations, Indicator functions

Tagged ,

Indicator Functions and Expectations – II

Posted on February 3, 2013 by | Leave a comment

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}\]

Leave a comment

Posted in Indicator functions

Tagged , , ,

The Coupon-Collector

Posted on October 2, 2012 by | Comments Off on 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 !

Comments Off on The Coupon-Collector

Posted in Indicator functions

Tagged

Indicator Functions

Posted on September 25, 2012 by | Leave a comment

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]

 

Leave a comment

Posted in Indicator functions

Stuffing Envelopes

Posted on August 28, 2012 by | Comments Off on 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!}\]

Comments Off on Stuffing Envelopes

Posted in inclusion-exclusion formula, Indicator functions, Matching

Tagged , , ,

Indicatior functions and expectations

Posted on August 15, 2012 by | Leave a comment

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 \) ?

Leave a comment

Posted in Expectations, Indicator functions