Mathematics desk
< March 14	<< Feb \| March \| Apr >>	March 16 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 15

Probability question

Suppose there are N persons and each of them picks a random number from 1 ... M, where M ≥ N. A person picks a "unique" number if nobody else picks the same number. Is there a simple expression for the expected number of persons who pick a unique number? If not, is there a simple approximation for that expected value, assuming that M is larger than N by a margin, e.g. M ≥ 2N? By "simple", I'm really trying to avoid iterated summations/products. I'm trying to understand how the function behaves as M and N vary. Thanks. --173.49.10.183 (talk) 12:36, 15 March 2012 (UTC)[reply]

Fixing M, let f(N) denote the expected number of different numbers chosen by N people. When the Nth person chooses their number, the probability they pick a number that no one has chosen so far is 1 - k/M where k is the number of different numbers chosen so far. The expectation of k is f(N-1), and since 1 - k/M is linear in k, its expectation is 1 - f(N-1)/M. So then f(N) = f(N-1) + 1 - f(N-1)/M. Solving the recurrence relation with initial condition f(0) = 0, we find f(N) = M - M(1 - 1/M)^N. The probability that the Nth person picked a unique number is 1 - f(N-1)/M, but it doesn't actually matter what order the people choose their numbers, so everyone should have the same chance. The expected number of people with unique numbers should be N(1 - f(N-1)/M) = N(1 - 1/M)^N-1. Rckrone (talk) 13:43, 15 March 2012 (UTC)[reply]

And here's another way of getting to the same point. Binomial distribution deals with this. Just think of one number, what is the chance that only only person chooses it? Any of the N could be the person and they choose it with probability 1/M, the N−1 other people don't choose it with probability each of 1−1/M. So the probability of just one person choosing a particular number is

N × (1/M) × (1 - 1/M)^N−1

And that gives you proportion that will be chosen on average by exactly one person. Multiply by the M numbers to get the number of people in the previous answer. When the numbers are large the proportion can be approximated by (N/M)e^−N/M. Dmcq (talk) 13:51, 15 March 2012 (UTC)[reply]

Look in the "approximations" section of birthday problem. 67.117.144.57 (talk) 08:09, 17 March 2012 (UTC)[reply]

Convert Hamiltonian path problem into subset sum problem and vice-versa

Since the Hamiltonian path problem (in a specific graph, is there a Hamiltonian path) is NP-complete, and the subset sum problem (given a set of integers, is there a non-empty subset whose sum is zero) is also NP-complete, by the definition of NP-complete, it should be possible to create a set of integers based on a graph, or construct a graph based on a set of integers, so that both have the same answer, no? How would you do that exactly? 84.197.178.75 (talk) 20:32, 15 March 2012 (UTC)[reply]

Found a reduction from Hamiltonian path problem to subset sum. With V vertices and E edges you use 2*V*E numbers (each representing an edge, the direction and it's place in the path) and use binary coding so that V numbers representing a closed path result in V*E bit positions set to 1 and add another V bits to represent the V possible start vertices of the edge to verify that every vertex is in the path (the paper I found uses V*E positions and encodes both vertices of every edge, that last bit seems redundant imo), maybe some extra zeros are needed to rule out sums of 3*E, 5*E etc numbers giving the right answer, not sure...

Guess it works, but I get the feeling that reducing this problem back to a Hamiltonian path problem will give me more than the V vertices I started with. Anyone a link on how to do that? 84.197.178.75 (talk) 02:04, 16 March 2012 (UTC)[reply]

You don't have to look for a direct reduction. Normally in these proofs you don't care at all about the degrees of the polynomials involved, so you can show equivalence by (say) reducing both problems to 3SAT. 67.117.144.57 (talk) 08:07, 17 March 2012 (UTC)[reply]

Good point, guess I'm really looking for a transformation that preserves the number of posibilities, not for a reduction. Not sure if that exists or is implied by NP-complete. 84.197.178.75 (talk) 15:09, 17 March 2012 (UTC)[reply]

Try to be precise with your question. If you're asking for a bijection between instances of the Hamiltonian path problem and the subset sum problem, where the bijection can be applied in polynomial time and preserves the yes/no answer, then this might be impossible. The existence of this is not implied by NP-completeness. If instead you're asking for transformations (not necessarily bijections) between the Hamiltonian path problem and the subset sum problem such that the number of Hamiltonian paths is equal to the number of subset sum solutions, then in general these are called parsimonious transformations. There is currently no Wikipedia article about the topic, but you can try Google (the singular form with quotes works best) and ignore search results that are unrelated to complexity theory. 98.248.42.252 (talk) 02:24, 18 March 2012 (UTC)[reply]

Thank you! Exploring all I've missed by choosing engineering instead of maths or physics twenty years ago. 84.197.178.75 (talk) 00:15, 20 March 2012 (UTC)[reply]