0

Expected value is the probability of the value times the value summed over all the values. In my question, there are 2 numbers that I'll say are X and Y.

The expected value of the sum is: p(X)*X + p(Y)*Y.

But I don't know what to use for p(X).

I understand that there is no uniform probability distribution over the set of natural numbers and I understand why: the sum of the individual probabilities will sum to infinity if the probability is >0 and will sum to 0 otherwise, neither of which is acceptable because that sum must be 1.

So, what value do I use for p(X) in the formula that computes the expected value?

delusionist
  • 61
  • 3
    That sum has no expected value since (as you understand) there is no uniform distribution on the natural numbers. What is the expected value of a single choice of a natural number? If you specify some actual distribution (necessarily not uniform) you can make the calculation. – Ethan Bolker Jan 21 '23 at 21:49
  • Rather than choosing a probability distribution, you can try to make some statement about the answer that would apply over any distribution, in terms of properties of the distribution of X and Y. – Alex K Jan 21 '23 at 21:55
  • 2
    Forget about sums – what's the expected value of one number chosen from the set of natural numbers? Do you see what a ridiculous question that is? how you can't make any progress on it, until you have a probability distribution on the naturals? How there are infinitely many different possible probability distributions on the naturals, no one any better than any other? You need more information, from somewhere. The best source is whoever gave you this question in the first place. – Gerry Myerson Jan 21 '23 at 22:20

1 Answers1

1

As you already said, uniform distributions are impossible to be created over the set of natural numbers, so we can't use uniform distributions. So another question arises: can we create any distribution over the set of natural numbers?

The answer is yes, in truth, we can create infinitely many, each with its own expected value (and therefore expected sum of $2$ values) and its own way to calculate the expected value.

Before creating a distribution we need to know what a distribution "looks like", and here I'm going to use the following definition:

The sequence $(p_n)$ is a probability distribution over the set of natural numbers if and only if $p_n \in \mathbb{Q}$ (this part will make sense later) and $p_n > 0$ for all $n$ and $\sum\limits_{n=1}^{\infty} p_n = 1$.

That is, if all probabilities $p_n$ are rational and greater than $0$ and the sum of all probabilities $p_n$ are $1$, then $(p_n)$ is a probability distribution over the natural numbers.

Now we need a way to use this probability distribution. The following algorithm comes from random walks:

  1. Define $q_n$ as $\dfrac{p_n}{\sum\limits_{i = 1}^{n - 1} p_n}$
  2. Let $n = 1$
  3. Generate a random integer $r$ (using a uniform distribution) from $1$ to $b$ (where $b$ is the denominator of $q_n$).
  4. If $r > a$ (where $a$ is the numerator of $q_n$) then let $n = n + 1$ and go to step 3
  5. The random number generated from the probability distribution $(p_n)$ is $n$

(I only let the probabilities rational in the definition in order to simplify this algorithm)

Note that $q_n$ is used because we need to "normalize" the values in $p_n$, for example, if the first value is $\frac{1}{3}$ and the next value is $\frac{1}{4}$, then running this algorithm with $q_n$ being defined as $p_n$ would result in the second value being chosen only $\frac{2}{3} \cdot \frac{1}{4} = \frac{1}{6}$ of the times instead of the desired $\frac{1}{4}$ of the times.

Now here goes an example of such probability distribution and its expected value:

$p_n = \dfrac{1}{2^n}$

The sequence $(p_n)$ is a probability distribution (in our definition) because $\dfrac{1}{2^n}$ is certainly greater than $0$ (as $n \ge 1$) and $p_n$ is a rational and $\sum\limits_{n=1}^{\infty} \dfrac{1}{2^n} = 1$.

Its expected value is $\sum\limits_{n=1}^{\infty} \dfrac{1}{2^n} \cdot n = 2$ and therefore the expected sum of $2$ natural numbers generated from this probability distribution is $2 \cdot 2 = 4$.

Tiago Cavalcante
  • 390
  • 1
  • 10
  • I'm trying to conceptualize this. It seems that you're sort of mapping the natural numbers 1:1 to the set {1/2,1/4,1/8...} like this: 1 maps to 1/2, 2 maps to 1/4, 3 maps to 1/8, and so on, and then running expected value calculations on the new set that is a uniform distribution. Is that the way to think about this? – delusionist Jan 23 '23 at 00:04
  • @delusionist I have updated my answer, the algorithm I said had a problem.

    The way to think about this is not a map, because this map would need to have infinite elements (which as you said in your question, is impossible). So instead we create a new sequence $(p_n)$, where $p_n$ represents the probability of $n$ being chosen with the algorithm. I think it is better to first conceptualize the idea of this sequence to then start understanding the algorithm. The idea behind the algorithm is to "check" if the random number is $1$, if it is $1$ we are done, otherwise "check" if it is $2$ ...

     – Tiago Cavalcante Jan 23 '23 at 01:19
  • So, if n=3, the probability of n (3) being chosen is 1/8 (one over p to the n power)? – delusionist Jan 23 '23 at 14:56
  • @delusionist in the example I gave, yes. The change of $4$ being chosen is $\frac{1}{16}$, the chance of $5$ being chosen is $\frac{1}{32}$, … Note that these chances change when $(p_n)$ changes – Tiago Cavalcante Jan 23 '23 at 17:39
  • Could 1/p^n be thought of as a random variable that maps from the set of natural numbers to the set of {1/2,1/4,1/8,...}? – delusionist Jan 25 '23 at 11:46
  • @delusionist no, that is just a probability – Tiago Cavalcante Jan 25 '23 at 18:30
  • So, the probability of choosing 1 is 0.5, 2 is 0.25, and so on. But when I'm doing probability problems and choosing from the set of natural numbers, I want the probability to be the same for each number, just like it might be in a finite set. I'm starting to think that I need to give up that idea because it's impossible. I understand that it's impossible (I think), so does that mean that no experiment can include randomly picking from the set of natural numbers unless I define the probability of picking each number in some way like the way you described above. – delusionist Jan 26 '23 at 19:12
  • If someone else set up a problem that said to randomly choose a number from the set of natural numbers, would I tell them that their experiment is impossible? If not, what would I say to convey that no math describes that situation? – delusionist Jan 26 '23 at 19:18
  • @delusionist right, it is impossible (and easy to prove that it is impossible) to pick a element from a infinite set with a uniform distribution (if you asked another question about it I could answer it). If someone asked me if it is possible to pick a number from the naturals with the same probability for all naturals I’d say it is impossible. – Tiago Cavalcante Jan 27 '23 at 03:07
  • I understand the above, and have a question about the word "randomly." Regarding exact language, and in particular the word "randomly", is it correct to say that a number cannot be "randomly" picked from the set of natural numbers? – delusionist Jan 29 '23 at 23:24
  • @delusionist it is correct in the colloquial meaning of the word. In the correct meaning of the word, it is wrong. According to WikiPedia (https://en.m.wikipedia.org/wiki/Randomness) randomness is a lack of predictability, and we have it in any random number generator from any probability distribution – Tiago Cavalcante Jan 29 '23 at 23:38