a pleasant problem for math freaks

AK70 · Post by **AK70** » 05 Feb 2002 19:41

<blockquote>quote:<hr>Originally posted by tengiz:
я позволил себе следующую вольность: разница высот соседних волн - случайная величина с симметричным распределением. Откуда и равенство вероятности пойти вверх или вниз.<hr></blockquote>

this sounds generic enough.

let F(x) is the probability that wave is less than X. actually, it's
int(P(x),x=0..1), where P(X) is a probability of wave with height X. X is between 0 and 1.

here int() - is integration

so, probability of having a wave whose preceding wave was less (in tengiz's notation it's 1) is:
int(F(x)*P(x), x=0..1) = 1/2

the meaning is that F(x) is a probability that preceding wave was lower than given current wave of height X. now we integrate it with factor P(x), density.

So, tengiz's assumption of 1/2 for 1 and 0 - seems to me correct.
----------------------

what's not Ok, is the calculation of distance distributions. I couldn't get 2/2^n, I got 4(n-1)/2^n - is the P(n)/P(2), where P(n) - is the probability of distance n between maximums.

Melkor · Post by **Melkor** » 05 Feb 2002 20:01

<blockquote>quote:<hr>Originally posted by AK70:
let F(x) is the probability that wave is less than X. actually, it's
int(P(x),x=0..1), where P(X) is a probability of wave with height X. X is between 0 and 1.

here int() - is integration

so, probability of having a wave whose preceding wave was less (in tengiz's notation it's 1) is:
int(F(x)*P(x), x=0..1) = 1/2

the meaning is that F(x) is a probability that preceding wave was lower than given current wave of height X. now we integrate it with factor P(x), density.

So, tengiz's assumption of 1/2 for 1 and 0 - seems to me correct.<hr></blockquote>

Верно, если нам ничего не известно о волнах до предыдущей, то вероятность того, что текущая волна ниже предыдущей, будет 1/2. Но мы ведь рассматриваем длинную цепочку волн целиком. Если мы рассматриваем волну i+2, и нам известно, что волна i+1 была ниже волны i, то распределение волны i+1 уже не будет линейным в интервале 0..1...

AK70 · Post by **AK70** » 05 Feb 2002 20:17

<blockquote>quote:<hr>Originally posted by Melkor:


Верно, если нам ничего не известно о волнах до предыдущей, то вероятность того, что текущая волна ниже предыдущей, будет 1/2. Но мы ведь рассматриваем длинную цепочку волн целиком. Если мы рассматриваем волну i+2, и нам известно, что волна i+1 была ниже волны i, то распределение волны i+1 уже не будет линейным в интервале 0..1...<hr></blockquote>

actually, when I tried to solve the problem few years ago, I thought exactly the same way you explain. when I tried to calcuate the number of different combinations, it reminded me Feinmann diagrams [img:b5d38612af]images/smiles/icon_smile.gif[/img:b5d38612af] I couldn't solve the problem.

when I saw tengiz's solution, I thought that's it! [img:b5d38612af]images/smiles/icon_smile.gif[/img:b5d38612af] because it gives exactly 3, and "looks right". but his proof is not satisfactory for me. actually, I couldn't get 2/2^n following his reasoning [img:b5d38612af]images/smiles/icon_sad.gif[/img:b5d38612af]

Melkor · Post by **Melkor** » 05 Feb 2002 20:29

<blockquote>quote:<hr>Originally posted by AK70:


actually, when I tried to solve the problem few years ago, I thought exactly the same way you explain. when I tried to calcuate the number of different combinations, it reminded me Feinmann diagrams [img:eca45085c1]images/smiles/icon_smile.gif[/img:eca45085c1] I couldn't solve the problem.

when I saw tengiz's solution, I thought that's it! [img:eca45085c1]images/smiles/icon_smile.gif[/img:eca45085c1] because it gives exactly 3, and "looks right". but his proof is not satisfactory for me. actually, I couldn't get 2/2^n following his reasoning [img:eca45085c1]images/smiles/icon_sad.gif[/img:eca45085c1] <hr></blockquote>

tengiz же, вроде, написал, что его решение - для линейного распределения [i:eca45085c1]разности высот[/i:eca45085c1] соседних волн, а не просто высот волн.

Melkor · Post by **Melkor** » 05 Feb 2002 20:35

<blockquote>quote:<hr>Originally posted by AK70:
[QB][/QB]<hr></blockquote>

Кстати, полностью согласен с Вами относительно венгерской нотации.

tengiz · Post by **tengiz** » 06 Feb 2002 22:10

Прошу прощения, коллеги - конечно моё "решение" неправильное. Разумеется вероятность цепочек должна быть X/2^X, а никак ни C/2^X. Так что ой. Я попробовал аккуратно посчитать эту вероятность для произвольного распределения высот - да, получается ужас, действительно чем-то напоминающий Фейнмановский интеграл по путям. Чего дальше с ним делать для произвольного распределения - я пока не знаю.

AK70 · Post by **AK70** » 06 Feb 2002 23:04

<blockquote>quote:<hr>Originally posted by tengiz:
Прошу прощения, коллеги - конечно моё "решение" неправильное.<hr></blockquote>

what I'm going to do is to write a program, which will generate sequences with different distributions : linear, gaussian, puassonian, etc.

then I'll estimate the distribution of distance. I suspect that they are all the same. If they are all the same then, I'll try to find an approximation. I suspect it might be easily an exponential, like c/2^n

AK70 · Post by **AK70** » 07 Feb 2002 04:34

вот результат моей симуляции на последовательности длины 100000000:

linear

Distribution of distances:
02: 0000000.3999225 ratio2: 0000001.0000000 ratio: 0000001.0000000
03: 0000000.3335284 ratio2: 0000001.1990657 ratio: 0000000.8339827
04: 0000000.1713101 ratio2: 0000002.3344947 ratio: 0000000.5136296
05: 0000000.0666690 ratio2: 0000005.9986240 ratio: 0000000.3891717
06: 0000000.0211942 ratio2: 0000018.8693872 ratio: 0000000.3179024
07: 0000000.0056938 ratio2: 0000070.2383060 ratio: 0000000.2686481
08: 0000000.0013296 ratio2: 0000300.7781689 ratio: 0000000.2335220
09: 0000000.0002863 ratio2: 0001396.9495966 ratio: 0000000.2153107
10: 0000000.0000554 ratio2: 0007221.6088841 ratio: 0000000.1934402
11: 0000000.0000090 ratio2: 0044289.3355482 ratio: 0000000.1630553
12: 0000000.0000014 ratio2: 0283640.2127660 ratio: 0000000.1561462
13: 0000000.0000001 ratio2: 2666218.0000000 ratio: 0000000.1063830
Avg. distance: 2.9999235019499353

Gaussian

Distribution of distances:
02: 0000000.4000749 ratio2: 0000001.0000000 ratio: 0000001.0000000
03: 0000000.3332447 ratio2: 0000001.2005440 ratio: 0000000.8329557
04: 0000000.1714331 ratio2: 0000002.3337085 ratio: 0000000.5144361
05: 0000000.0666491 ratio2: 0000006.0027075 ratio: 0000000.3887760
06: 0000000.0211767 ratio2: 0000018.8921835 ratio: 0000000.3177350
07: 0000000.0057334 ratio2: 0000069.7800725 ratio: 0000000.2707389
08: 0000000.0013387 ratio2: 0000298.8633185 ratio: 0000000.2334849
09: 0000000.0002843 ratio2: 0001407.3321022 ratio: 0000000.2123616
10: 0000000.0000525 ratio2: 0007624.8593482 ratio: 0000000.1845715
11: 0000000.0000110 ratio2: 0036238.8016304 ratio: 0000000.2104059
12: 0000000.0000013 ratio2: 0296352.8666667 ratio: 0000000.1222826
13: 0000000.0000002 ratio2: 1905125.5714286 ratio: 0000000.1555556
14: 0000000.0000000 ratio2: 13335879.0000000 ratio: 0000000.1428571
Avg. distance: 2.999989200038772

------------------
пояснения:
первая последовательность с линейным распределением высот волн, вторая - с гауссовым.

первый столбец - вероятность расстояния между максимумами, ratio2: отношение вероятности расстояния 2 к данному, ratio - отношение вероятности данного расстояния к предыдущему.

видно что для обоих распределений вероятности одинаковые, что я и подозревал.

надо бы теперь подогнать под какую-то формулу. на экспоненту не похоже