Suppose a positive integer N is generated by a fair lottery.
Then, a random integer K is chosen between 1 and N (inclusive).
What information does this give you about N?
Obviously you now know that N ≥ K. Anything else?
Consider some specific pair of numbers n ≥ k, and suppose we’ve found out that K = k. What’s the probability that N = n? Of course P(N=n|K=k) = 0/0. But what if we do this as a limiting procedure. Suppose first that N is randomly chosen between 1 and M where M ≥ n, and let PM be the probabilities for this case. Then
- PM(N=n|K=k) = (1/M)(1/n)/[(1/M)Σj=kMj−1] = (1/n)/Σj=kMj−1.
Take the limit as M goes to infinity. Since Σn=k∞j−1 = ∞, the limit is zero, so we don’t have a meaningful distribution for N.
On the other hand, what if we independently choose two random integers K1 and K2 between 1 and N? Suppose n ≥ ki for i = 1, 2. Let k* = max (k1,k2). Then:
- PM(N=n|K1=k1,K2=k2) = (1/M)(1/n2)/[(1/M)Σj=k*Mj−2] = (1/n2)/Σj=k*Mj−2.
Take the limit as M → ∞ and call that P(N=n|K1=k1,K2=k2). The limit behaves like ck*/n2, for a constant c > 0, and generates a well-defined probability for N = n.
With zero samples, we don’t have a well-defined probability for N. With one sample, we still don’t. But with two samples (or more), now we do. This is a rummy thing: how is it that sampling turns probabilistic nonsense into sense?
This is making me more friendly to using non-normalized probabilities. After all, the fair lottery for N is easily modeled by the constant probability p0(n) = 1. With one sample N = k, we have p1(n) = 1/n for n ≥ k and p1(n) = 0 for n < k. With two samples k1, k2, we have p2(n) = 1/n2 for n ≥ max (k1,k2) and p2(n) otherwise. All this makes perfect sense. And there is a lovely mathematical feature of non-normalized probabilities: conditionalization is conjunction. The conditional probability of an event A on event B is just the probability of A ∩ B.
Non-normalized probabilities aren’t going to solve all problems with infinite fair lotteries. For instance, I toss a fair coin and generate a number N with the following rule. On heads, I choose N with my fair lottery on the positive integers. On tails, I choose N such that the probability of N = n is 2−n (e.g., I toss an independent fair coin and let N be the number of the first toss that gives heads). What’s my non-normalized probability p(x,n), where x is heads or tails and n is a positive integer? We surely want ∑np(H,n) = ∑np(T,n): the total probability of the heads options equals the total probability of the tails options. But clearly p(T,n) has to exponentially decrease so ∑np(T,n) is finite and non-zero. On the other hand, p(H,n) is constant, so ∑np(H,n) is zero or infinity. So they can’t be equal.
But I wonder if one could say something like this: Non-normalized probabilities make sense in certain cases, and in those cases it’s reasonable to use them?
Rummy? One of my favourite Wodehouse-isms :-)
ReplyDeleteI’m not sure this works. You are taking the limit *with n fixed* as M goes to infinity. But as M increases, the likely values of n also increase. Ignoring this can lead to paradoxes.
Here is a paradoxical variation on the 1-sample case. As in the post, N is chosen from a fair infinite lottery on 1, 2, 3, … . K is chosen as follows: A fair coin is flipped. On Heads, K equals N. On Tails, K equals N/2, rounded up to the nearest integer. (You can think of this as a very special unfair lottery on 1 to N.)
Suppose we have found out that K=k. There are only three possibilities: (Heads, N=k), (Tails, N=2k), (Tails, N=2k-1). Apply the method in the post. For any M greater than 2k, these are all possible and have equal probability. So it seems that in the limit of increasing M, each should each be given probability 1/3. So whatever the outcome k, Tails will be given probability 2/3.
Hmm… This could be defensible for some finite set of k values *specified in advance*. But it’s not reasonable for *k, whatever it turns out be*.