t**********t
发帖数: 364 | 1 一个0/1序列，长度为N（say N=1000）
0/1出现的概率均为1/2
求出现的最长continuous序列的expected长度（连续的0或连续的1均可，只要最长）。
now repeat it for any 0
have fun | m*******r
发帖数: 98 | 2 The state is (m,n), where m is the current maximal length, and n is the
current length. m from 1 to N, n from 1 to m.
The final distribution is T^(N-1) times [1 0 ... 0]', where T is the
transfer matrix.
Then we can calculate the expectation.
For arbitrary p, the state is augmented by (m,label_m, n, label_n).
【在 t**********t 的大作中提到】
: 一个0/1序列，长度为N（say N=1000）
: 0/1出现的概率均为1/2
: 求出现的最长continuous序列的expected长度（连续的0或连续的1均可，只要最长）。
: now repeat it for any 0: have fun
| p*****k
发帖数: 318 | 3 how long were you given for this problem?
here is my attempt for the case of a FAIR coin.
consider n total tosses, with the maximum length of either consecutive H or consecutive T no greater than k. denote the number of such sequences: x(n,k). then the problem asks for
sum {from k=1,N} k*[x(N,k)-x(N,k-1)]/2^N.
to get x(n,k), note up to a factor of 2, this is the number of ways to partition n into positive integers no greater than k, which appears in brainteasers like crossing river or climbing | m*******r
发帖数: 98 | 4 what is the period of delta?
I tested up to N=1000. The linearity seems quite good.
or consecutive T no greater than k. denote the number of such sequences: x(
n,k). then the problem asks for
partition n into positive integers no greater than k, which appears in
brainteasers like crossing river or climbing stairs. easy to get the
recurrence relation:
~ 9.33), and seems it converges to ~ log2(N)+0.33 when N is large. so for N
=1000, it should be ~ 10.3
characteristic polynomials, but it's po
【在 p*****k 的大作中提到】
: how long were you given for this problem?
: here is my attempt for the case of a FAIR coin.
: consider n total tosses, with the maximum length of either consecutive H or consecutive T no greater than k. denote the number of such sequences: x(n,k). then the problem asks for
: sum {from k=1,N} k*[x(N,k)-x(N,k-1)]/2^N.
: to get x(n,k), note up to a factor of 2, this is the number of ways to partition n into positive integers no greater than k, which appears in brainteasers like crossing river or climbing
| J******d
发帖数: 506 | 5 If the correlations among the digits of your series are 1, then for every p,
the expectation is N.
【在 t**********t 的大作中提到】
: 一个0/1序列，长度为N（say N=1000）
: 0/1出现的概率均为1/2
: 求出现的最长continuous序列的expected长度（连续的0或连续的1均可，只要最长）。
: now repeat it for any 0: have fun
| t**********t
发帖数: 364 | 6 correlation? what correlation? each digit is independent...
p,
【在 J******d 的大作中提到】
: If the correlations among the digits of your series are 1, then for every p,
: the expectation is N.
| t**********t
发帖数: 364 | 7 this is an excellent analysis.
yes, the answer should be on the order of log2N. I spent about 20 mins on
this one and no luck, was able to get some induction for small N, but was
not able do it for general N. after 20 mins of scratching head, was told to
move on to next question, the interviewer mentioned no one was able to solve
this on spot...oh well
or consecutive T no greater than k. denote the number of such sequences: x(
n,k). then the problem asks for
partition n into positive integers
【在 p*****k 的大作中提到】
: how long were you given for this problem?
: here is my attempt for the case of a FAIR coin.
: consider n total tosses, with the maximum length of either consecutive H or consecutive T no greater than k. denote the number of such sequences: x(n,k). then the problem asks for
: sum {from k=1,N} k*[x(N,k)-x(N,k-1)]/2^N.
: to get x(n,k), note up to a factor of 2, this is the number of ways to partition n into positive integers no greater than k, which appears in brainteasers like crossing river or climbing
| c******r
发帖数: 300 | 8 classis probability problem, check the following paper:
The longest run of heads
by M. F. Schilling
【在 t**********t 的大作中提到】
: 一个0/1序列，长度为N（say N=1000）
: 0/1出现的概率均为1/2
: 求出现的最长continuous序列的expected长度（连续的0或连续的1均可，只要最长）。
: now repeat it for any 0: have fun
| p*****k
发帖数: 318 | 9 here is the exact form of delta and relevant reference in Finch's book stolen from google book. delta as a function of log2(N) has a period of 1.
Schilling's paper is indeed good, which won the MAA writing award:
http://mathdl.maa.org/mathDL/22/?pa=content&sa=viewDocument&nodeId=2681 | J******d
发帖数: 506 | 10 Please tell me why each digit is independent. Which part of your
original post grants this?
【在 t**********t 的大作中提到】
: correlation? what correlation? each digit is independent...
:
: p,
|
|
