4
$\begingroup$

A set $S = \{1, 2, \cdots, k\}$ is given. Two persons independently choose some numbers from this set. I want to count the probability that the cardinality of intersection of the chosen sets by both persons is exactly one.

Each person has to choose at least one number. A person can choose a number which is already chosen by another person. A number is being chosen independently and uniformly at random from the set.

My approach: Fix one number from $1$ to $k$. Probability of both persons choosing that number is $\frac{1}{k^2}$. Remaining $k-1$ numbers can be chosen by either of both or by none of both. So, probability for that is $\left(1 - \frac{1}{k^2}\right)^{k-1}$. And that fixed number can be selected in ${k \choose 1}$ ways.

So, probability of required event is:

\begin{align} P(E) = {k \choose 1} \frac{1}{k^2} \left(1 - \frac{1}{k^2}\right)^{k-1} \end{align}

My questions:

  1. Is this reasoning correct?

  2. Initially I started with counting all the possible ways of choosing numbers by each person. Can we count the required probability by counting ways technique? Is there any other way of counting the probability?

$\endgroup$
  • 1
    $\begingroup$ Why do you say that the probability of both people picking the fixed number is $\frac{1}{k^2}$? $\endgroup$ – paw88789 Oct 25 '15 at 12:57
  • 2
    $\begingroup$ I think you need to say something about the number of elements each player selects. There are $2^k-1$ non-empty subsets of $\{1,....,k\}$. Do you mean to say that each player can select any one of these with equal probability? $\endgroup$ – lulu Oct 25 '15 at 12:57
  • $\begingroup$ @lulu Yes. That is what I mean. $\endgroup$ – Nimit Oct 25 '15 at 13:07
  • $\begingroup$ Ok, but then the situation is more complex than your method suggests. You have to take into account the fact that it is more likely that a randomly chosen subset has about $\frac k2$ elements than, say, $1$ or $k$. $\endgroup$ – lulu Oct 25 '15 at 13:09
  • $\begingroup$ @paw88789 I got your point. I smell something wrong with my reasoning now. I had assumed that each person is choosing that fixed number very first. But that is not the case. It can be chosen later also. $\endgroup$ – Nimit Oct 25 '15 at 13:16
5
$\begingroup$

Your reasoning is not correct.

Let us at first ignore the condition that at least one number has to be chosen (that will get fixed afterwards). Under that condition, as each choice of each possible subset is equally likely (as you say in the comments), and for any given element there are exactly the same number of subsets containing and not containing that element (think of a subset and its complement!), the probability that a person chooses a given number is exactly $1/2$. Thus it's the same problem as if both people throw a coin for each number, and the question is what's the probability that they throw both head for exactly one of the numbers.

This is a fairly standard problem which I guess you can solve. Let's call the obtained probability $p_0$.

Now we have to fix this up for the condition that the empty set is not a valid choice. Fortunately this is easy, since when any party chose the empty set, we know for sure there was no number that was chosen by both (because at least one of them didn't chose a number to begin with).

Since the probability calculated in the previous step is $$\frac{\text{Number of choices with exactly one shared number}} {\text{Total number of choices when allowing empty sets}}$$ we have to just fix up the denominator, which we can do by multiplying with $$\frac{\text{Total number of choices when allowing empty sets}} {\text{Total number of choices when not allowing empty sets}}.$$ Now the total number of choices when allowing empty sets is $2^{2k}$ since there are $2^k$ subsets, and each person chooses one. When excluding the empty set, each player has one choice less (namely he cannot choose the empty set), and therefore without the empty set, the number of possible choices is $(2^k-1)^2$.

Therefore we have for the requested probability: $$p = \frac{2^{2k}}{(2^k-1)^2}p_0$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ To get an exact answer, the requirement of nonempty set choice by each person complicates the problem. For instance, players can't select/not select items by tossing a coin because that would allow for the empty set being chosen. And then consequently we can't simply say that for any given item that the probability of both selecting it is $\frac14$. I think you need to know more about how numbers are chosen. $\endgroup$ – paw88789 Oct 25 '15 at 13:45
  • 1
    $\begingroup$ @paw88789: Ah right, I overlooked that condition. But the claim that all possible sets are chosen with equal probability should still be sufficient. I'll rework the answer. $\endgroup$ – celtschk Oct 25 '15 at 13:50
  • $\begingroup$ @paw88789: See edited answer. $\endgroup$ – celtschk Oct 25 '15 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.