Date: Mon, 18 Mar 96 13:49:47 CST
From: rusin (Dave Rusin)
To: lasmith@athena.mit.edu
Subject: Re: A fun question on words formed from an alphabet without replacement
Newsgroups: sci.math

In article <4ic5lq$9ok@senator-bedfellow.MIT.EDU> you write:
>
>Given are n letters a1,a2,...,an. 
>There is a chance p_i of choosing letter i.
>What is the chance that a k letter word formed from 
>the letters *without replacement* (no letter used twice) 
>misses letter an?

So if  a_1  is selected first, with what probability will the various
letters be selected next? I assume you mean for the probability that
a_2 is selected next, for example, to be  p_2/(p_2+...+p_n), i.e., 
the remaining letters will be selected with probabilities proportional
to their original probabilities, but of course scaled up to sum to 1.

I don't know if there is a _compact_ expression for the resulting
answer, but it's easy to describe. For example, when  k=2, the 
event you want to find the probability of is the union of these:
	(a_i  is selected first and then  a_n  is not selected second)
(for i=1, 2, ..., n-1). These  n-1  events are mutually exclusive,
so we get a probability of
	Sum  p_i*(1-p_n/(1-p_i))
	=Sum p_i - p_n Sum p_i/(1-p_i)
	=1-p_n   - p_n Sum [-1 + 1/(1-p_i) ]
	= 1 + (n-1)p_n - p_n Sum[ 1/(1-p_i) ]
but that's as simple as I can make it. There is, for example, no way to
express this in terms of  p_n  only.

So you have to accept cumbersome answers. Once you've granted that, it's
possible to write down correct (and cumbersome) expressions for  k>2, too.
Here's the same as above but for  k=3:
	Sum p_i*(p_j/(1-p_i))*(1-p_n/(1-p_i-p_j))
the sum taken over all pairs  i<>j  of integers in [1, ..., n-1] .
I won't even bother trying to manipulate it to something simpler.

I will concede that the resulting formulas will have to be rational
functions in  p_1, ..., p_(n-1), and  p_n, which are symmetric
with respect to the first  n-1  parameters; thus in principle you can
express the answers as rational functions of  p_n  and a generating
set of symmetric functions of the  p_i; for example, you should be
able to express the answer in terms of  p_n  and the "moments"
	m_1=p_1+...+p_(n-1)   (= 1 - p_n), 
	m_2=p_1^2+...+p_(n-1)^2, 
	...
	m_(n-1) = p_1^(n-1)+...+p_(n-1)^(n-1)
or instead in terms of  p_n  and the "elementary symmetric functions"
	s_1=m_1,
	s_2= Sum( p_i p_j : i < j ),
	...
	s_(n-1) = Prod(p_i)
But it's not clear that these are any better unless in your application
some set of symmetric functions of the  p_i  is already in use.

dave