Let $X$ denote an $m\times n$ matrix and suppose that each value $x_{ij}$ is an integer that is selected uniformly at random from ${1,\dots,n}$, independently of all other values. If we fix $m$ and take the limit as $n\to\infty$, what is the probability that there exists a number that is contained in all $m$ rows of $X$?
3
-
$\begingroup$ Is this a homework problem? This does not seem appropriate for MO. $\endgroup$– Noah SchweberCommented Jun 21, 2013 at 22:37
-
$\begingroup$ Not homework, but I'm happy to post to stackexchange if that's the majority opinion. $\endgroup$– Daryl N HolmesCommented Jun 21, 2013 at 22:41
-
$\begingroup$ A confession: I actually don't know anything about probability, which is why I didn't downvote or vote to close. This looks, though, like it is not research-level, which is what this site is for. (Also, if you post to MSE, you should give some motivation for this problem.) $\endgroup$– Noah SchweberCommented Jun 21, 2013 at 23:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
By approximate independence between the $n$ numbers (and complete independence among the rows for a fixed number), the probability is approximately $$1-(1-(1/e)^m)^n\rightarrow 1.$$
answered Jun 22, 2013 at 6:48
-
$\begingroup$ Thanks, I gather that the "approximate independence" assumption is used to justify the $()^n$ expression. Is there a way to make that argument more rigorous? I've googled "approximate independence", "almost independent", et cetera, but can't seem to find a body of literature that would help in justifying that. $\endgroup$ Commented Jun 22, 2013 at 19:19
-
$\begingroup$ Could try to replace "is approximately" by "is $\ge $" but it might become a long computation. $\endgroup$ Commented Jun 22, 2013 at 21:52