Assume all random numbers come from the uniform distribution on the unit interval.
probability/up.down.sequence New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Assume all random numbers come from the uniform distribution on the unit
interval.
1. Pick a sequence of random numbers, continuing as long as each number
is greater than the previous one.
- What is the expected value of the last number chosen (that is, the
last number in the increasing sequence)?
(a) What is the expected number of numbers chosen?
(b) What is the expected value of the sum of the sequence?
2. Same questions, but pick the sequence of random numbers, continuing
as long as each number is _less_ than the previous one.
3. Generalize. Start with an infinite string over the alphabet {<,>}.
Pick a sequence of random numbers, continuing as long as the
sequence satisfies the corresponding relations given in the string.
Question 1 corresponds to the string "<<<<..." and question 2
corresponds to the string ">>>>...". What about "<><><><>..."?
"><><><><..."? What string(s) give upper bounds on the expected
number of numbers chosen and the expected sum?
-- Michael J. Slifker <M_Slifker@fccc.edu>
Show solution
The probability for a sequence of n+1 random numbers between 0 and 1 to
have the relationships defined by the sequence S = { S1, S2, ..., Sn },
where Si is "<" or ">", is given by:
1 b1 b2 bn
p(S) = I I I ... I dx0 dx1 dx2 ... dxn
x0=0 x1=a1 x2=a2 xn=an
where ai = 0 and bi = x<i-1> if Si = ">"; ai = x<i-1> and bi = 1 if
Si = "<".
1 1 x<i-1>
The integral I can be replaced with I - I whenever Si = "<".
xi=x<i-1> xi=0 xi=0
Substituting into the first formula and gathering terms yields:
N
2 T(j) 1 t1j t2j tnj
p(S) = SUM (-1) I I I ... I dx0 dx1 dx2 ... dxn
j=1 x0=0 x1=0 x2=0 xn=0
where N is the number of "<" in S and T(j) is the number of 1's in j's
binary expansion. tij for a given j is 1 for the values of i for which
Si = "<", Si is the mth "<" in S, and the mth digit from the right in
j's binary expansion is 0. tij is x<i-1> in all other cases.
This integral can be evaluated analytically to yield:
N
2 T(j)
p(S) = SUM (-1) Fj(s1,s2,...,sN,s<N+1>)
j=1
s1 is equal to i1, sj is equal to ij-i<j-1> for j = 2, 3, ..., N, and
s<N+1> is equal to n + 1 - iN, where ik is the i for which Si is the kth
"<" in S.
Fj(s1,s2,...,sN,s<N+1>) is defined as 1/(t1! t2! ... tm!), where
t1 = s1 + s2 + ... + sk1
t2 = s<k1+1> + s<k1+2> + ... + sk2
...
tm = s<k<m-1>+1> + s<k<m-1>+2> + ... + skm
and k1 is the position of the first 0 in j's binary expansion, k2 is the
position of the second 0, and so on.
For example, for ">><<>" s1 = 3, s2 = 1 and s3 = 2, and then we have
j T(j) t1 t2 t3 F(j)
0 (00) 0 3 1 2 1/12
1 (01) 1 3 3 1/36
2 (10) 1 4 2 1/48
3 (11) 2 6 1/720
p(">><<>") [Editor: was p(">><>>")] = 1/12 - 1/36 - 1/48 + 1/720 = 13/360
Let now S be of infinite length, and let us define Rn(S) as the
sub-series { S1 S2 ... S<n-1> S*n }, where S*k is "<" if Sk is ">" and
vice versa. The probability of ending up with n numbers exactly is then
P(Rn(S)), and the expected value of n is
INF
E(S) = SUM n p(Rn(S))
n=1
For example, in the case of ">>>>>...", for Rn s1 = n and s2 = 1, and
thus p(Rn) = 1/n!-1/(n+1)! = n/(n+1)!, and
INF 2 INF INF INF
E(S) = SUM n /(n+1)! = SUM (n(n+1)-(n+1)+1)/(n+1)! = SUM 1/(n-1)! - SUM 1/n! +
n=1 n=1 n=1 n=1
INF INF INF INF INF
SUM 1/(n+1)! = SUM 1/n! - SUM 1/n! + SUM 1/n! = SUM 1/n! - 1 = e - 1
n=1 n=0 n=1 n=2 n=0
The expected value for the kth random number in a sequence of length n
is given by
1 b1 b2 bn
Ek(Rn(S)) = I I I ... I x<k-1> dxn ... dx2 dx1 dx0 / p(Rn(S))
x0=0 x1=a1 x2=a2 xn=an
This integral can be evaluated analytically to yield:
N
2 T(j)
Ek(Rn(S)) = SUM (-1) Fjk(s1,s2,...,sN,s<N+1>) / p(Rn(S))
j=1
Fjk(s1,s2,...,sN,s<N+1>) is defined as G(k)/(t1! t2! ... tm!), where
G(k) is defined as (t1+1-k)/(t1+1) for k = 1, 2, ..., t1,
(t1+t2+1-k)/(t2+1) for k = t1+1, t1+2, ..., t1+t2, (t1+t2+T3+1-k)/(t2+1)
for k = t1+t2+1, t1+t2+2, ..., t1+t2+t3, and so on.
The expected value of for the last random number in a sequence is thus
N
INF INF 2 T(j)
El(S) = SUM p(Rn(S)) En(Rn(S)) = SUM SUM (-1) Fjn(s1,s2,...,sN,s<N+1>)
n=1 n=1 j=1
and the expected value of the sum of random numbers is
INF n
Es(S) = SUM p(Rn(S)) SUM Ek(Rn(S)) =
n=1 k=1
N
INF n 2 T(j)
SUM SUM SUM (-1) Fjk(s1,s2,...,sN,s<N+1>)
n=1 k=1 j=1
For example, in the case of ">>>>>..." we have
Ek(Rn(S)) = ((n+1-k)/(n+1)!-(n+2-k)/(n+2)!)/(n/(n+1)!) =
(n+1-k)/n-(n+2-k)/(n(n+2)) = 1-k(n+1)/(n(n+2))
and therefore En(Rn(S)) = 1/(n+2)
INF INF INF
El(S) = SUM n/(n+2)! = SUM 1/(n+1)! - 2 SUM 1/(n+2)! =
n=1 n=1 n=1
INF INF
SUM 1/n! - 2 SUM 1/n! = e-2-2(e-5/2) = 3 - e
n=2 n=3
INF n INF 2
Es(S) = SUM SUM (n(n+2)-k(n+1))/(n+2)! = 1/2 SUM n(n +2n-1)/(n+2)! =
n=1 k=1 n=1
INF 3 2
1/2 SUM (n -4n +3n+2)/n! =
n=3
INF INF INF
1/2 ( SUM 1/(n-3)! - SUM 1/(n-2)! + 2 SUM 1/n! ) =
n=3 n=3 n=3
INF INF INF
1/2 ( SUM 1/n! - SUM 1/n! + 1 + 2 SUM 1/n! - 5 ) = e - 2
n=0 n=0 n=0
in order to reduce the amount of summation we note that if S* is
defined as the sequence where Sk* is "<" if Sk is ">" and vice versa,
then p(S*) = p(S) (obtained by replacing xk with 1-xk in the integral),
and therefore E(S*) = E(S) as well. Similarly Ek(Rn(S)) = 1 -
Ek(Rn(S*)), and therefore El(S*) = 1 - El(S) and Es(S*) = E(S) - Es(S).
For example, in the case of "<<<<<..." we have (using the ">>>>>..."
results) E(S) = e - 1, El(S) = e - 2, and Es(S) = 1.
For the general case a computer program can be used to evaluate E(S),
El(S) and Es(S) [Editor: was E(S)] from the above formulae. Using such a
program here are the results for a variety of possible sequences
(obtained by repeating pattern infinitely):
Pattern Length Last term Sum of terms
< 1.71828 0.71828 1.00000
> 1.71828 0.28172 0.71828
<> 2.40822 0.58682 1.26400
>< 2.40822 0.41318 1.14422
<<> 1.93538 0.68841 1.09865
>>< 1.93538 0.31159 0.83674
<>> 2.15669 0.52204 1.08698
><< 2.15669 0.47796 1.06971
<>< 2.23655 0.62758 1.20963
><> 2.23655 0.37242 1.02692
The maximum value for the length appears to be for the sequences
obtained by repeating "<>" or "><", and the maximum value for the sum of
terms appears to be for the sequence obtained by repeating "<>".
-- Ilan Mayer <ilan@isgtec.com>