1
$\begingroup$

Let $p_0\in(0,1)$ and let $s>0$. Consider the sequence with terms $p_k$ generated randomly as follows: $$ p_{k+1}=\left\{ \begin{array}{ccl} p_k & \mbox{if} & r_k\leq p_k\\ p_k-s & \mbox{if} & r_k > p_k \end{array} \right., $$ where $r_k\in[0,1]$ is uniformly randomly chosen at each step. We stop whenever $p_k\leq 0$.

What is the expected length of the generated sequence (taking $p_0$ as the first term and the last strictly positive $p_k$ as the last term)?

I can make some simulations and some computations by hand, but I don't really know about any more sophisticated tool to approach such questions. I'm doing this for fun, so any help that might make me learn new stuff will be very welcome.

$\endgroup$
1
$\begingroup$

You can use linearity of expectation. Let $q_0 = p_0, q_1 = p_0-s, q_2 = q_1-s$,... $q_l = q_{l-1}-s$ where we stop so that $q_l-s < 0$. Note this is a pre-determined, deterministic sequence. The expected number of times we see $q_j$ arise in the sequence $(p_0,p_1,\dots,p_k)$ is $\frac{1}{1-q_j}$, so the expected value of $k$ is $\sum_{j=0}^{l-1} \frac{1}{1-q_j}$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer: I made some computations and it looks like the -1 should not be there (meaning that the expected length is $\sum_{j=0}^{l-1}\frac{1}{1-q_j}$ instead). Do you agree? $\endgroup$ – A. Bellmunt Nov 14 '18 at 11:02
  • $\begingroup$ I debated putting the $-1$ there. If $q_j = \frac{1}{2}$, then the expected number of times we see $q_j$ should be 1 rather than 2, no? $\endgroup$ – mathworker21 Nov 14 '18 at 11:21
  • $\begingroup$ Ohhh, nevermind. We see $q_j$ at least once just automatically. Then the expected number of times we see it again is $\frac{1}{1-q_j}-1$, so the total is $\frac{1}{1-q_j}$. I'll edit my answer. $\endgroup$ – mathworker21 Nov 14 '18 at 11:21
  • $\begingroup$ Great. I already accepted your answer. I like to write $p_0-js$ instead of $q_j$ and $\lfloor p_0/s\rfloor$ instead of $l-1$ (although one should be careful here because we have to take $\lfloor p_0/s\rfloor-1$ when $s|p$) to better reflect the dependancy on $p_0$ and $s$. $\endgroup$ – A. Bellmunt Nov 14 '18 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.