1
$\begingroup$

If there are 100 tickets in an urn, and you draw two at a time, look at them, and replace them both, how does that change the problem? It would obviously take half as many trials, but how does the fact that one ticket will never be a duplicate of the other affect the result?

$\endgroup$

1 Answer 1

2
$\begingroup$

It helps. The simplest way to analyze is to just say that, for any positive integer $n$, the probability of finishing on or before $n$ rounds of this pairwise selection is greater than or equal to the probability of finishing on or before $2n$ rounds of single selection.

An exact analysis is more complicated but you could define a Markov chain with state $c(t) \in \{0, 1, ..., 100\}$ being the number of coupons you have seen after round $t$ (with $c(0)=0$ and $c(1)=2$). Then for $c \in \{2, ..., 98\}$: \begin{align} P_{c,c+2} &= \frac{{100-c \choose2}}{{100 \choose 2}} \geq \left(\frac{100-c}{100}\right)\left(\frac{100-(c+1)}{100}\right)\\ P_{c, c+1} &= \frac{{100 -c \choose 1}{c \choose 1}}{{100 \choose 2}}\\ P_{c,c} &= \frac{{c \choose 2}}{{100 \choose 2}} \leq \left(\frac{c}{100}\right)^2 \end{align} and you could formally use the inequalities in a stochastic coupling argument to prove the claim in the first paragraph.

$\endgroup$
2
  • $\begingroup$ Alright, I've only heard of Markov chains and stochaic anythings, any resources you'd suggest for learning more about them and possibly this type of problem? I'm in over my head. $\endgroup$
    – JShoe
    Nov 7, 2017 at 7:37
  • $\begingroup$ You can search the web for "Markov chains." Above I am using $P_{ij} = P[c(t+1)=j|c(t)=i]$, which is standard notation for Markov chains. Here are some class notes on expected travel times in Markov chains. ee.usc.edu/stochastic-nets/docs/markov-chains-travel-times.pdf $\endgroup$
    – Michael
    Nov 7, 2017 at 7:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .