Матан. Вероятность. Аналитическая геометрия

Знаешь как решить свою задачу в одномерном случае?

Полным перебором :-) Можешь еще метод градиентного спуска применить.

Не очень понятно. У тебя есть набор троек: x, y и P(x, y). Тебе нужно по заданному P выбрать все (x,y) которые ему соответствуют и из них выбрать случайную?

Ну отсортируй по P и делай. Или я неправильно понял?

Не очень понятно. У тебя есть набор троек: x, y и P(x, y). Тебе нужно по заданному P выбрать все (x,y) которые ему соответствуют и из них выбрать случайную? Ну отсортируй по P и делай. Или я неправильно понял?

Примерно так, но:
1)Троек нет, есть x,y и аналитически заданная функция, которую лишний раз считать не хотелось бы, ибо время
2)Если даже и представить всё тройками, то сортировать по z... уж шибко массив большой будет чтоб его сортировать, хотелось бы какое-то читерское решение

Знаешь как решить свою задачу в одномерном случае?

Нет, не знаю. Есть идеи?

хотелось бы какое-то читерское решение

Без конкретики наверное ничего не придумать. Монте-Карло не подходит?

Вообще 10**6 элементов не выглядит как-то слишком уж пугающе, может проще будет для всех P посчитать

Без конкретики наверное ничего не придумать.

Да уж куда конкретнее... есть декартова плоскость xy, есть 3D поверхность над ней f(x,y)

Вообще 10**6 элементов не выглядит как-то слишком уж пугающе, может проще будет для всех P посчитать

Дело в том, что в будущем может быть и 1000000x1000000, а функция эта должна считаться за минимально короткое время, чтоб как сложение двух чисел с плавоющей точкой занимало (утрирую), так как она будет вызываться в очень длинном цикле постоянно. Так что подобные реализации абсолютно неприемлимы.

Без оптимизации так: считаем сумму всех элементов. S = sum_x_y xy[j] выбираем число от 0 до S - 1. t := random [0, S) Дальше псевдокод:

for i <- 0 .. 1000
  for j <- 0 .. 1000
    t := t - xy[i][j];
    if t < 0
      return (i, j)

Чтобы оптимизировать, надо хранить суммы по строкам. Дальше - сначала находим строку, потом в ней находим столбец.

Возможно целочисленное переполнение в случае большого S, вероятно надо использовать большие числа.

Делай дерево.

Корню соответствует отрезок [0;1) и весь массив xy. Левое поддерево отвечает за одну половину массива D_l и [0;sum(P,x,y) (x,y принадлежит D_l)), правое поддерево за D_r и отрезок [sum(P,x,y) (x,y принадлежит D_l); sum(P,x,y) (x,y принадлежит D_l) + sum(p,x,y) (x,y принадлежит D_l) = 1) и т.д. пока не дойдёшь до отдельных ячеек. По выданному ГСЧ числу спускайся по дереву.

тогда уж лучше делать дерево с 4мя ветками.

хотя всё равно как.

Если скорость не важна то выбираешь ячейку. Потом внутри нее x, y, z, где z от нуля до глобального максимума всей функции. Если z > p(x, y), вертай (x, y), в противном случае goto начало.

Посчитать функцию распределения (интеграл от плостности), взять обратную, пропустить через неё равномерно распределенную выборку. Самый известный способ, для произвольного непрерывного распределения.

Делай дерево.

Спасибо, думаю идею я уловил, надо будет её обдумать. Пожалуй, из численных методов это будет оптимально.
Но, возможно коллективный разум знает как подобные задачи решаются в аналитическом виде, раз уж мы имеем аналитически заданную функцию? Хотя бы ссылочку, где про такое почитать

Не затруднит ссылку на внятный мануал?

Аналитически через обратные ф-и если они существуют. вики

http://en.wikipedia.org/wiki/Inverse_transform_sampling

А когда они могут не существовать? не могу придумать пример.

Там что-то написано, на счёт того, что функция должна быть исключительно возрастающей, если я правильно понял. И намёк на то, что обратные функции ищите сами где хотите =)

Плотность неотрицательна, интеграл от нее не может убывать. Обратную надо численно брать. Или заранее насчитать сэмплов и аппроксимировать.

Я подобную одномерную задачу решал: надо было равномерное распределение 0..1 преобразовать в распределение согласно аппаратной функции прибора. Где-то на просторах интернета даже исходники для октавы (чи матлаба) валялись. Если надо — поищу.

Но все элементарно: по обратной функции. Если аналитически обратную функцию найти невозможно, делаем численно (все равно ведь численные методы).

А когда они могут не существовать? не могу придумать пример.

Формально, например, когда есть плоскость у ф-ии распределения, т.е. существуют отрезки с плотностью равной нулю.

А зачем такое понадобилось?

Вот возьмем одномерный случай с нормальным распределением. Юзер вводит число p(x) = 0.658, и получает: x = 1 или x = -1. Что теперь с этим результатом делать? И сколько ему нужно ответов - один, первый попавшийся, или случайно выбранный? Два? Бесконечное число для двумерного случая?

Похоже, выбранный случайно. Эта случайность тоже имеет свой закон. По какому выбираем?

Тогда обратная будет разрывна, но существовать то будет, неоднозначности не получается.

Есть подозрение, что ты не такую задачу решал. Чтобы получить из равномерного распределения любое другое (хоть нормальное, хоть лапласа, хоть твоего прибора), нужна интегральная функция.

А здесь про плотность распределения пишуть.

Тогда обратная будет разрывна, но существовать то будет, неоднозначности не получается.

нет, её вообще не будет, как раз из-за неоднозначности. Но тем не менее можно будет сделать нужную разрывную ф-ю для задачи.

Дык, у меня тоже плотность была — интегрировал.

Все уже украдено до нас (с):

http://statistik.wu-wien.ac.at/unuran/

а эта задача сводится к одномерному случаю. банально разворачиваем матрицу вероятностей в строку.

для одномерного случая алгоритм с временем выборки О(1) и предподготовкой О(N) описан, например, у Романовского И.В, «Дискретный анализ». емнип

Так впечатлился, что до сих пор помню

для одномерного случая алгоритм с временем выборки О(1)

Ох, пошёл гуглить.

в смысле ты не веришь, или ты меня посылаешь? )

Если известна функция распределения плотности вероятности P(x,y), то как (в общих чертах) реализовать функцию, возвращающую юзеру случайным образом пару x,y в соответствии с заданной функцией распределения плотности вероятности? Что почитать на эту тему?

ну надо надо найти обратную P'(z), которая даёт (x,y).

Можно использовать комплексное число w, как контейнер для (x,z).

Что-бы получить случайное z (в ОДЗ 0..1) нужно его умножить на равномерно распределённое случайное число 0..1.

а эта задача сводится к одномерному случаю. банально разворачиваем матрицу вероятностей в строку.

а какая разница, сколько размерностей? Просто вместо одномерного вектора используем многомерный. Это одно число, только из-за принятой записи (x,y) кажется, что их два. Но это не так — это точка. Даже если она в гиперпространстве со 100 измерениями.

в смысле ты не веришь, или ты меня посылаешь? )

Ну, в смысле пошёл искать книгу, точнее, уже читаю.

а какая разница, сколько размерностей? Просто вместо одномерного вектора используем многомерный. Это одно число, только из-за принятой записи (x,y) кажется, что их два. Но это не так — это точка. Даже если она в гиперпространстве со 100 измерениями.

(x,y) это не точка, а кубик квадратик, т.е. такие рассуждения относительно верны если пространство дискретное. Но если, например, нужно выбрать (float, float) с заданной ф-ей распределения P(x,y), то так уже рассуждать нельзя.

(x,y) это не точка, а кубик квадратик, т.е. такие рассуждения относительно верны если пространство дискретное. Но если, например, нужно выбрать (float, float) с заданной ф-ей распределения P(x,y), то так уже рассуждать нельзя.

(x,y) это точка. Или пятнышко (математики говорят «окрестность точки (x,y)). Нет никакой разности, как пространство (не)квантовано. Мало того, как раз в квантованном это „кубик“(точнее тоже точка, но не где угодно, а в узле решётки)

float тут не при чём. Их число тоже. Набор float'ов определяет ОДНО место в пространстве. Математики давно доказали эквивалентность мощностей множеств точек прямой и плоскости. И там и там их ровно алеф-1. Т.е. все точки на плоскости можно отобразить в прямую, и наоборот.

Случайная девиация — тоже в некотором смысле „точка“, ибо задаётся всего одним параметром — радиусом сферы/окружности. Это скалярная величина, как любое расстояние. Оно всегда положительно. И у него нет никакого направления.

те же яйца, вид сбоку^Wиз-под грибов

Сведи задачу к одномерной.

Тебе нужна вероятность P(y) и P(x/y).

Тогда тебе нужно будет сгенерировать элемент одномерного распределения P(y) и в зависимости от сгенерированного y, генерировать x из соответствующего одномерного распределения P(x/y)

(x,y) это точка. Или пятнышко (математики говорят «окрестность точки (x,y)).

(x,y) в контексте топика это именно квадрат конкретного размера 1x1, т.к. имеет место быть разбиение (R,R) над P(x,y). Математики говорят про окрестности совсем в других контекстах.

Т.е. все точки на плоскости можно отобразить в прямую, и наоборот.

отлично, расскажи как это сделать практически для (float, float)

Не эквивалентность, а равномощьность. Т.е. существование биекции между множествами. Но учти, здесь биекции мало, здесь нужен изоморфизм вероятностных пространств.

(x,y) в контексте топика это именно квадрат конкретного размера 1x1, т.к. имеет место быть разбиение (R,R) над P(x,y). Математики говорят про окрестности совсем в других контекстах.

хорошо, пусть будет интервал. В двумерном виде — это да, квадратик. Но суть-то та же самая. И оно отлично разворачивается в одномерный случай, особенно в компе — в сишечке дык вообще многомерных массивов строго говоря и нет, там любой многомерный массив это тупо последовательность эл-тов.

отлично, расскажи как это сделать практически для (float, float)

struct complex {
  float x;
  float y;
};

Так например в электротехнике представляются в расчётах разные величины: есть активный ток, и есть реактивный ток. Это ОДИН ток, и мы его делим только для удобства в расчётах. Вот конденсатор имеет только мнимое сопротивление (действительное бесконечно), что не мешает нам включить и юзать в сеть на 220 вольт лампочку на 127 вольт. Ага, через конденсатор, рассчитанный по закону Ома.

Какое отношение комплексные числа имеют к равномощьности R и R²?

Не эквивалентность, а равномощьность. Т.е. существование биекции между множествами. Но учти, здесь биекции мало, здесь нужен изоморфизм вероятностных пространств.

конечно развернуть поверхность на прямую невозможно, но нам это и не нужно — нам необходимо и достаточно считать обе половинки (x,y) ОДНИМ числом. Т.е. это зависимые переменные, которые могут быть выражены обе через некое t, и только через него. То, что мы не знаем как именно выражается, и какой смысл t — роли не играет. Вот один float (у меня) это тоже на самом деле 32 разных бита, каждый из которых играет свою роль. Это нам как-то мешает юзать float как единое число?

Какое отношение комплексные числа имеют к равномощьности R и R²?

в данном случае — самое прямое. Откуда вы вообще взяли это «разворачивать»? Что мешает вам считать (x,y) одним неделимым числом?

Юзер вводит число p(x) = 0.658, и получает: x = 1 или x = -1. Что теперь с этим результатом делать?

как «что»? Юзать. Ну и что, что решений два? А кто тебе сказал, что юзеру нужно только одно?

Опять пример из электротехники: если ток постоянный, то выбора нет: надо юзать сопротивление, если хочешь понизить напряжение на чём-то. Но если ток переменный, то решений аж три:

1. также юзать сопротивление.

2. сделать конденсатор.

3. мотать катушку индуктивности.

IRL применяют все три. Почему программа должна решать за юзера, какое лучше, если в рамках модели все три эквивалентны?

как «что»? Юзать. Ну и что, что решений два? А кто тебе сказал, что юзеру нужно только одно?

ещё пример: GPS. Пересечение двух сфер — окружность. А трёх — две точки. Это как-то мешает юзать GPS на практике?

Так например в электротехнике представляются в расчётах разные величины: есть активный ток, и есть реактивный ток.

Деление тока на активный и реактивный мне не понятно. Как минимум, не понятно, почему это активный элемент(резистор) реагирует на реактивный ток. И наоборот, почему реактивный элемент реагирует на активный ток? Мне понятнее, что комплексый ток включает в себя еще и фазу помимо амплитуды.

ЗЫ но главное, какое это нах имеет отношение к вопросу ТС? =)

в данном случае — самое прямое. Откуда вы вообще взяли это «разворачивать»? Что мешает вам считать (x,y) одним неделимым числом?

Именно что никакого отношения =)

Деление тока на активный и пассивный мне не понятно.

сам-ты «пассивный» (:

ток РЕАКТИВНЫЙ. Это такой термин технический.

Как минимум, не понятно, почему это активный элемент(резистор) реагирует на реактивный ток. И наоборот, почему реактивный элемент реагирует на активный ток? Мне понятнее, что комплексый ток включает в себя еще и фазу помимо амплитуды.

ну во первых у тебя в голове каша: «активный» это такой эл-т, который может менять свои характеристики. Например КМОП транзистор меняет сопротивление канала в зависимости от потенциала затвора. Пассивный элемент просто тупо лежит. Конденсатор — тоже пассивный. Ибо не меняется, пока не поломаешь.

Во вторых, как я уже говорил, это абстракция. Ток ОДИН. Его _удобно_ делить на компоненты для расчётов. Как вот комплексные числа удобно складывать в декартовом виде. А вот умножать/делить удобно в экспоненциальной форме(это как раз тогда, когда у тебя «сдвиг по фазе» :) Амплитуда тут вообще не при чём, ты её путаешь с эффектным напряжением(током). Эффектное значение у математиков называется «модуль». Вот модуль того, что в твоей розетке == 220В. А амплитуда таки 311вольт.

резистор пассивный, и ни на что не реагирует. Он тупо греется, отхватывая часть энергии. А конденсатор тоже ни на что не реагирует, а тупо тормозит, постоянно перезаряжаясь. При этом энергия на нём не рассеивается, он её забирает при заряде, и потом отдаёт на разряде. Потому тоже «задерживает» энергию — часть её просто не доходит до потребителя, и идёт обратно. Это приводит к сдвигу фазы у потребителя относительно поставщика. Этот сдвиг фазы == тоже напряжение и тоже греет провода (потому если много конденсаторов, ещё и индуктивности нужны. Там эффект такой-же, но знак противоположный. Вот в старых ЛДС нужны были индуктивности, и потому приходилось туда ставить ещё и конденсаторы, иначе из-за этого энергетического онанизма провода погорят).

Но _количественно_ конденсатор работает как активное сопротивление, хотя качественно он «не сопротивляется», а тупо тормозит.

но главное, какое это нах имеет значение к вопросу ТС? =)

самое прямое: ТС должен понять, что координата у точки ОДНА. Как один ток. Просто её удобно разложить на (x,y), для вычислений. Для других вычислений удобнее будет взять модуль и «фазу». Не веришь? Дай уравнение окружности в (x,y) радиуса R. Вот только эти все представления, да и вообще мерность пространства совершенно ортогонально рассматриваемому распределению. Оно вообще «вверх» направлено в случае ТСа. Если вернуться к электротехнике, то это ваше P(x,y) суть ЦЕНА в рублях и копейках данного девайса. Зависимость есть, но она совсем не линейная, да и не столько от «сопротивления». Больше от допуска цена зависит. Ну и от других, совершенно ортогональных характеристик (морозостойкости скажем).

Да, естественно обратная функция будет многозначной, если у исходной функции есть одинаковые значения. Ну и что? Например парабола x^2 имеет два значения, когда она равна 1. Обратная ессно двузначна при x==1. Ну например, если на твоей поверхности все точки с z образуют окружность R^2=x^2+y^2, то очевидно обратная функция в z будет многозначной, со значениями R^2=x^2+y^2. Как их «вернуть юзеру», и какой в этом физический смысл — ТСу виднее.

Именно что никакого отношения

вы как-то плоско мыслите. Задача ТСа трёхмерная, и поверхность трёхмерная. Её не нужно никуда сворачивать. Её просто надо повернуть, и рассматривать ось z как ось x. Сама поверхность от этого ну никак не поменяется, гуглить аффиные преобразования. Вот, просвещайся: http://ru.wikipedia.org/wiki/Аффинное_преобразование

Так например в электротехнике представляются в расчётах разные величины...

Чувак, тебя уносит с твоим вольным словоблудием и гуманитарными аналогиями непонятно куда. Просто покажи как развернуть и получить от этого профит.