Seminar 1

Seminar Exercises

Exercise 1, Difficulty 1

Two identical coins each have a ‘0’ on one side and a ‘1’ on the other. Both coins are tossed, and the sum of the numbers showing is calculated. This process is then repeated. What is the probability that the same sum is obtained on both tosses, under the following conditions:

  1. the coins are distinguishable.
  2. the coins are indistinguishable (bosonic).

Let S_1, S_2 be the sum of the first and second tossing. We need to find \mathbb{P}(S_1=S_2) = \sum_{k=0}^2 \mathbb{P}(S_1=k)^2.

  1. For distinguishable coins, the sample space is \{(0,0), (0,1), (1,0), (1,1)\}, with each outcome having probability 1/4. The probabilities for the sums are \mathbb{P}(S=0)=1/4, \mathbb{P}(S=1)=1/2, \mathbb{P}(S=2)=1/4. \mathbb{P}(\text{same sum}) = (1/4)^2 + (1/2)^2 + (1/4)^2 = 6/16 = 3/8.

  2. For indistinguishable (bosonic) coins, the sample space is the set of outcomes \{\{0,0\}, \{0,1\}, \{1,1\}\}. Assuming these are equally likely, each has probability 1/3. The probabilities for the sums are \mathbb{P}(S=0)=1/3, \mathbb{P}(S=1)=1/3, \mathbb{P}(S=2)=1/3. \mathbb{P}(\text{same sum}) = (1/3)^2 + (1/3)^2 + (1/3)^2 = 3/9 = 1/3.

Exercise 2, Difficulty 1

You are taking an exam along with other students. The number of students is equal to the number of exam tickets, which is n. It is known that among the tickets, there are 1\le k\le n easy ones. Students enter the room one by one, draw a ticket, and keep it. When is the best time for you to enter to maximize the probability of drawing an easy ticket? To figure out this burning question, calculate the probability of drawing an easy ticket if you enter

  1. first;
  2. j-th, 1\le j \le n.

By symmetry (permutation invariance of the probability of each sequence of easy/hard problems), the probability is independent of the position.

  1. For the first student, the probability is clearly k/n.
  2. Any of the n tickets is equally likely to be in the j-th position. Since k of them are easy, the probability is k/n. The time of entry does not matter.

Exercise 3, Difficulty 3

Consider a random placement of n indistinguishable (bosonic) particles into M distinguishable cells. Calculate the probability Q_k (n; M) that a fixed cell contains k particles.

Find the limit of Q_k (n; M) as n, M \to \infty such that n/M \to \lambda, where \lambda>0 is fixed.

Note: This distribution is called “Bose-Einstein statistics”; it describes the distribution of bosons over energy levels and provides a physical justification for a model where indistinguishable items are placed in distinguishable containers.

The total number of configurations is \binom{n+M-1}{n}. If we fix one cell to have k particles, we must distribute the remaining n-k particles into the other M-1 cells. The number of ways is \binom{(n-k)+(M-1)-1}{n-k} = \binom{n-k+M-2}{n-k}. Q_k(n; M) = \frac{\binom{n-k+M-2}{n-k}}{\binom{n+M-1}{n}}

In the limit, this probability converges to a geometric distribution with parameter p = \frac{\lambda}{\lambda+1}. \lim_{n,M\to\infty} Q_k(n;M) = (1-p)p^k = \frac{1}{\lambda+1}\left(\frac{\lambda}{\lambda+1}\right)^k

Exercise 4, Difficulty 2

There is a code of length n consisting of digits from 0 to 9. Find the probability that the digits are arranged in non-decreasing order.

The total number of codes is 10^n. A non-decreasing sequence is determined by the multiset of its digits. The number of such multisets of size n from 10 digits is \binom{n+10-1}{n} = \binom{n+9}{n}. \mathbb{P}(\text{non-decreasing}) = \frac{\binom{n+9}{n}}{10^n}

Exercise 5, Difficulty 1

From a deck (52 cards), 4 cards are drawn.

  1. What is the probability that all 4 cards are spades?
  2. What is the probability that 3 cards are spades and one is a heart?

Exercise 6, Difficulty 3

There are three numbered boxes (1,2,3). 10 indistinguishable (bosonic) white balls and 4 numbered red balls (1,2,3,4) are randomly distributed among them. Find the probability that each box contains at least one white ball and at least one red ball with a number greater than the box number.

Exercise 7, Difficulty 3

There are three boxes, containing three black and three white balls randomly placed. Find the probability that the first box contains at least two black balls, and the third box contains no more than one white ball, if

  1. the balls are numbered
  2. the balls are distinguished only by color (bosonic).

Exercise 8, Difficulty 2

There is a box with 30 distinguishable balls, of which 10 are red and 20 are black. 12 balls are drawn at random (without regard to order and without replacement). Find the probability that among the drawn balls, there is an equal number of red and black ones. What changes if the order is taken into account?

Exercise 9, Difficulty 3

This is how a (one-dimensional) transmission line of a cellular network works. n antennas are arranged in a line at equal distances. Each antenna repeats the signal received from the neighboring antenna. The signal can travel a distance of two antennas, so the transmission works if there are no two consecutive faulty antennas. Suppose that m < n antennas are faulty, but we do not know their positions. What is the probability that the transmission works?

  • \mathrm{I I X I I I X I} = works
  • \mathrm{I I X X I I I I} = does not work

Exercise 10, Difficulty 3

A person flips a coin repeatedly. They stop as soon as they get a sequence of n heads or a sequence of 1 tail and (n-1) heads in a row.

  1. What is the probability that they will stop?
  2. What is the probability that they will stop at a sequence of n heads?

Exercise 11, Difficulty 4

An electric train consists of n cars. Each of k passengers chooses a car at random. What is the probability that every car will have at least one passenger? What is the probability that exactly r cars will be occupied?

Exercise 12, Difficulty 4

Passengers on a bus take their seats randomly, ignoring the seat numbers on their tickets. The number of passengers is equal to the number of seats. What is the probability that none sits in their assigned seat?

Exercise 13, Difficulty 3

A person bought two boxes of matches at the same time and put them in his pocket. After that, every time he needed to light a match, he randomly took one box or the other. After some time, upon taking out one of the boxes, the person found it to be empty. What is the probability that the other box at that moment contained k matches, if the number of matches in a new box is n?

Exercise 14, Difficulty 3

Using a random selection scheme with replacement from the set of natural numbers \{1,\dots,N\}, N\ge 2, numbers \xi and \eta are chosenc (in other words all the N^2 pairs (i,j) have the same probability). Show that \mathbb{P}\left(\xi^2-\eta^2 \text{ is divisible by 2}\right) < \mathbb{P}\left(\xi^2-\eta^2 \text{ is divisible by 3}\right)

Exercise 15, Difficulty 4

Using a random selection scheme with replacement from the set of natural numbers \{1,\dots,N\}, N\ge 3, numbers \xi and \eta are chosen. Which is greater, \mathbb{P}\left(\xi^3+\eta^3 \text{ is divisible by 3}\right) or \mathbb{P}\left(\xi^3+\eta^3 \text{ is divisible by 7}\right)?

Exercise 16, Difficulty 5

Using a random selection scheme with replacement from the set of natural numbers \{1,\dots,N\}, numbers \xi and \eta are chosen. Find the probability q_N that \xi and \eta are coprime. Find \lim_{N\to\infty}q_N.

Additional Exercises

Exercise 17, Difficulty 2

200 Probability students are divided into three groups of 50, 50, and 100 students each, to attend seminars in classrooms with the corresponding capacity.

  1. In how many ways can these groups of students be formed?

Alexandra and Svetlana are good friends and would like to be in the same room during the seminar. But they cannot stand Alexey, and they hope he will be assigned to a different room.

  1. What is the probability that their wishes are fulfilled?

Exercise 18, Difficulty 5

An urn contains u_1 balls of color 1, u_2 balls of color 2, …, u_R balls of color R. We perform n random draws, and immediately after each draw, the ball is returned to the urn along with m other balls of the same color (m\ge -1 and n\le u_1+\ldots+ u_R if m=-1).

  1. What is the probability that a ball of color r will be drawn on the i-th draw?
  2. What is the probability that among the n selected balls, color 1 appears j_1 times, color 2 appears j_2 times, \ldots, color R appears j_R times?
  3. Let u_1=u_2=\ldots=u_R=m. Calculate the previous probability in the following cases: m=-1 (drawing balls without replacement); m=0 (drawing balls with replacement).