Expected number of button clicks

Question

Suppose we have $N$ buttons and each button can be clicked with probability $p_i$. The game stops when the player clicks the button with $i = 1$. Once a button is clicked, the player can not click the same button again. What is the expected number of clicks?

I am not able to answer this question for $ N > 2 $

For $N = 1$, $E[x] = 1$

For $N = 2$, suppose $p_1 = 5 / 6$ and $p_2 = 1 / 6$ , then $ E[x] = 1*p_1 + 2 * p_2 = 1.167$

Can anyone please help me to solve for any $N$?

Answer 1

Let the number of buttons be $N$.

And probabilities of buttons are $p_1, p_2, p_3 ... p_n.$

The expected value $E[X] = N - \frac{p_1}{p_1 + p_2} - \frac{p_1}{p_1 + p_3} - \frac{p_1}{p_1 + p_4} .... \frac{p_1}{p_1 + p_n}$

Will update the full derivation in sometime.

UPDATE:

Consider $N = 3$

$E[X] = 1*p_1 + 2*(p_2*\frac{p_1}{p_1 + p_3} + p_3*\frac{p_1}{p_1 + p_2}) + 3*(p_2*\frac{p_3}{p_3 + p_1}*1 + p_3*\frac{p_2}{p_2 + p_1}*1)$

$E[X] = p_1 + 2*p_2*\frac{p_1}{p_1 + p_3} + 2*p_3*\frac{p_1}{p_1 + p_2} + 3*p_2*\frac{p_3}{p_1 + p_3} + 3*p_3*\frac{p_2}{p_1 + p_2}$

Rearranging terms with same denominator...

$E[X] = p_1 + ( 2*\frac{p_2*p_1}{p_1 + p_3} + 3*\frac{p_2*p_3}{p_1 + p_3}) + (2*\frac{p_3*p_1}{p_1 + p_2} + 3*\frac{p_3*p_2}{p_1 + p_2})$

$E[X] = p_1 + ( 3*p_2 - \frac{p_1*p_2}{p_1 + p_3}) + (3*p_3 - \frac{p_1 * p_3}{p_1 + p_2})$

$E[X] = 3 (p_1 + p_2 + p_3) - (2*p_1 + \frac{p_1*p_2}{p_1 + p_3} + \frac{p_1 * p_3}{p_1 + p_2})$

Since, Sum of all probabilities is 1

$E[X] = 3 - p_1*(2* + \frac{p_2}{p_1 + p_3} + \frac{p_3}{p_1 + p_2})$

$E[X] = 3 - p_1*(\frac{2*(p_1 + p_2)*(p_1 + p_3) + p_2*(p_1 + p_2) + p_3*(p_1 + p_3)}{(p_1 + p_2)*(p_1 + p_3)})$

$E[X] = 3 - p_1*(\frac{(p_1 + p_2)*(p_1 + p_3) + (p_1 + p_2)*(p_1 + p_3) + p_2*(p_1 + p_2) + p_3*(p_1 + p_3)}{(p_1 + p_2)*(p_1 + p_3)})$

$E[X] = 3 - p_1*(\frac{(p_1 + p_2)*(p_1 + p_2 + p_3) + (p_1 + p_3)*(p_1 + p_2 + p_3)}{(p_1 + p_2)*(p_1 + p_3)})$

$E[X] = 3 - p_1*(\frac{(p_1 + p_2) + (p_1 + p_3)}{(p_1 + p_2)*(p_1 + p_3)})$

$E[X] = 3 - p_1*(\frac{1}{p_1 + p_3} + \frac{1}{p_1 + p_2})$

$E[X] = 3 - (\frac{p_1}{p_1 + p_2} + \frac{p_1}{p_1 + p_3})$

$E[X] = 1 + \frac{p_2}{p_1 + p_2} + \frac{p_3}{p_1 + p_3}$

If you do the same thing for N = 4 and onwards.. you get the same thing.. but it is messy...

Answer 2

Compare it with throwing a die. What is the expected number of throws needed to get a 6 ?

Although there are 6 possible outcomes for each throw, we reduce it to two, a 6 with Pr = 1/6, and any other with a Pr = 5/6, and E(X) = 1/p = 6

Similarly, here p = 1/N, and E(X) = N

Answer 3

This is only a partial answer, meant to point the OP in a hopefully helpful direction.

If the non-terminating buttons $i=2$ to $N$ can each be clicked more than once, as the original statement of the problem seemed to allow, then the expected number of clicks is simply $1/p_1$, as true blue anil correctly answered.

When buttons cannot be clicked more than once, the answer will be a function of the probabilities assigned to buttons $2$ to $N$. As the OP correctly said, the answer is (trivially) $1$ when $N=1$ and $p_1+2p_2$ when $N=2$.

For examining the next case, I think it's convenient to change a bit of notation, letting $a$, $b$, $c$, etc. denote the probabilities of clicking (and thus eliminating) the non-terminating buttons $2$, $3$, $4$, etc., so that $p_1=1-(a+b+c+\cdots)$. We can express the OP's findings as

$$E_0=1$$ and $$E_1(a)=1+a$$

where the subscript on $E$ counts the number of non-terminating buttons. If I've done all the algebra correctly, the answer in the next case is

$$E_2(a,b)={1-(a^2-ab+b^2)\over(1-a)(1-b)}$$

Note, in particular, that

$$E_2(a,0)={1-a^2\over1-a}=1+a=E_1(a)$$

which makes sense: if the second non-terminating button has no chance of being clicked, then you really only have one non-terminating button. Also,

$$E_2({1\over3},{1\over3})={1-1/9\over4/9}=2$$

which accords with the easily proved general result

$$E_{N-1}({1\over N},{1\over N},\ldots,{1\over N})={N+1\over2}$$

So let me summarize what we have so far:

$$\begin{align} E_0&=1\\ \\ E_1(a)&={1-a^2\over1-a}\\ \\ E_2(a,b)&={1-(a^2+b^2-ab)\over(1-a)(1-b)}\\ \end{align}$$

At first glance, this suggests

$$E_3(a,b,c)={1-(a^2+b^2+c^2-ab-bc-ca)\over(1-a)(1-b)(1-c)}$$

which certainly satisfies $E_3(a,b,0)=E_2(a,b)$. But it doesn't satisfy $E_3({1\over4},{1\over4},{1\over4})={5\over2}$, so it can't be correct. Indeed, I have a feeling the next formula is going to be a somewhat messy one.

Answer 4

Let's try to look at this problem recursively:

If we have only one button, the expected number of clicks is obviously 1 $$E_1=1$$

For any $n$, the expected number of clicks is: $$E_n=p_1+(1-p_1)(n-1)E_{n-1}$$ Since we have $n-1$ choices to choose a button that isn't button #1, and the probability of that happening is $1-p_1$.

This should be enough to answer your question

If you want to have a closed form solution, this can be done by solving the recursive relation.

We'll define a generating function $$f(x)=\sum{E_nx^n}$$

$$f(x)=E_0+\sum_{n=1}{(p_1+(1-p_1)(n-1)E_{n-1})x^n}=E_0+\sum_{n=1}{p_1x^n}+(1-p_1)\sum_{n=1}{(n-1)E_{n-1}x^n}=E_0+\frac{p_1x}{1-x}+(1-p_1)x\sum{(n-1)E_{n-1}x^{n-2}}=1+\frac{p_1x}{1-x}+(1-p_1)x^2f'(x)$$

We got a differential equation: $$f'(x)-\frac{f(x)}{x^2(p_1-1)}=\frac{p_1(x-1)+1}{(1-x)(p_1-1)x^2}$$ This is a linear differential equation, The solution of this type equation is described here:

Then, in order to get the closed form equation, substitute f here:

$$E_n=\frac{f^{(n)}(0)}{n!}$$ I haven't done the calculations myself, but I can assure you that the result is not pretty.