2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3
 
 Re: Вероятность остатков.
Сообщение24.09.2012, 20:33 
Sonic86 в сообщении #623058 писал(а):
Напишите, пожалуйста, попытки решения явно, я Вам подскажу. Задача очень хорошая :-) А кратко я Вам написал уже: сначала выпишите формулу для $N_n-N_{n-1}$ явно, а потом делайте тривиальные оценки.
Или колитесь, откуда задача :-) тогда кусок решения выпишу.

Точного источника задачи не знаю, давал преподаватель.
$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.

 
 
 
 Re: Вероятность остатков.
Сообщение24.09.2012, 22:57 
dreamkiller в сообщении #623114 писал(а):
$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.
Ну только надо писать либо $\approx$ вместо $=$, либо выписывать погрешность $O(...)$.
Ну все :-) Чему равна сумма?
И потом из рекуррентного соотношения ищем $N_n$ с точностью до $O(...)$

 
 
 
 Re: Вероятность остатков.
Сообщение24.09.2012, 23:21 
Sonic86 в сообщении #623182 писал(а):
dreamkiller в сообщении #623114 писал(а):
$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.
Ну только надо писать либо $approx$ вместо $=$, либо выписывать погрешность $O(...)$.
Ну все :-) Чему равна сумма?
И потом из рекуррентного соотношения ищем $N_n$ с точностью до $O(...)$

Все равно не понимаю, как получить $5/4 - \ln2$. У меня почему-то получается . Что $N_n \approx \frac{n(n-1)}{4} - n(n+1)\ln 2$

 
 
 
 Re: Вероятность остатков.
Сообщение25.09.2012, 06:28 
dreamkiller в сообщении #623188 писал(а):
Все равно не понимаю, как получить $5/4 - \ln2$. У меня почему-то получается . Что $N_n \approx \frac{n(n-1)}{4} - n(n+1)\ln 2$
Вы уже все нашли, воспользуйтесь теперь классическим определением вероятности. Здесь $N_n$ - благоприятствующее число случаев.
И, кстати, в строгом доказательстве соотношения типа $\approx$ неприемлемы - лучше переписать с использованием $O(...)$.

 
 
 
 Re: Вероятность остатков.
Сообщение25.09.2012, 10:42 
Всего случаев $n^2$. Но тогда $ \frac{N_n}{n^2} \approx 1/4 - \ln 2$, где я теряю единицу?

 
 
 
 Re: Вероятность остатков.
Сообщение25.09.2012, 11:02 
dreamkiller в сообщении #623267 писал(а):
где я теряю единицу?
А! Понял. Она теряется в ряде для $\ln 2$ (в нем нет первого члена)

 
 
 
 Re: Вероятность остатков.
Сообщение25.09.2012, 11:18 
Sonic86 в сообщении #623274 писал(а):
dreamkiller в сообщении #623267 писал(а):
где я теряю единицу?
А! Понял. Она теряется в ряде для $\ln 2$ (в нем нет первого члена)


Действительно. Тогда все сходится. Всем спасибо за помощь(В особенности Sonic86).

 
 
 
 Re: Вероятность остатков.
Сообщение23.07.2019, 21:20 
dreamkiller в сообщении #623114 писал(а):
Точного источника задачи не знаю, давал преподаватель.
"На его месте должен был быть я" (с) Извиняюсь за некропостинг, но не смог пройти мимо (тоже предлагаю своим студентам эту задачу). Касательно первоисточника и точной формулировки задачи:
von zur Gathen & Gerhard in Modern Computer Algebra писал(а):
The fact that two random integers are coprime with probability $6/\pi^2$ is a theorem of Dirichlet (1849). Dirichlet also proves the fact, surprising at first sight, that for fixed $a$ in a division the remainder $r=a \bmod{b}$, with $0<r<b$, is more likely to be smaller than $b/2$ than larger: If $p_a$ denotes the probability for the former, where $1<b<a$ is chosen uniformly at random, then $p_a$ is asymptotically $2-\ln{4} \approx 61{.}37\%$.


-- Ср июл 24, 2019 01:23:43 --

gris в сообщении #620646 писал(а):
Или зафиксировать первое число, а второе считать не большим его, выбираемым равновероятно. Тогда вероятность будет зависеть от первого числа.
Вот прям как у классика :)

 
 
 [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group