Как называется это дискретное распределение (рекурсивное разностное уравнение), которое я получил?

11

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

На каждом шаге игра генерирует равномерное случайное число . Если , то событие инициируется. После того, как событие произошло один раз, игра сбрасывает и снова проходит последовательность. Меня интересует только одно вхождение события для этой проблемы, потому что это представляет дистрибутив, который использует игра. (Кроме того, на любые вопросы, касающиеся множественных вхождений, можно ответить с помощью одной модели вхождения.)n0X<1X<p(n)n=0

Основная «аномалия» здесь заключается в том, что параметр вероятности в этом распределении увеличивается со временем, или, другими словами, порог увеличивается со временем. В примере это изменяется линейно, но я предполагаю, что могли бы применяться другие правила. После шагов или действий пользователя,n

p(n)=kn

для некоторой константы . В определенной точке мы получаем p (n _ {\ max}) \ geq 1 . Событие просто гарантированно произойдет на этом этапе.0<k<1nmaxp(nmax)1

Я смог определить, что

F ( n ) = p ( n ) + F ( n - 1 ) [ 1 - p ( n ) ] f ( n ) F ( n ) n p ( n )

f(n)=p(n)[1F(n1)]
и для PMF и CDF . Вкратце, вероятность того, что событие будет на м шаге, равна вероятности , меньше вероятности того, что событие уже произошло на каком-либо предыдущем шаге.
F(n)=p(n)+F(n1)[1p(n)]
f(n)F(n)np(n)

Вот сюжет от нашего друга Монте-Карло, для удовольствия, с . Медиана работает до 21 и в среднем до 22. k0.003введите описание изображения здесь

Это в целом эквивалентно разностному уравнению первого порядка из цифровой обработки сигналов, которое является моей историей, и поэтому я нашел это довольно новым. Я также заинтригован тем, что может варьироваться в зависимости от любой произвольной формулы.p(n)

Мои вопросы:

  1. Как называется этот дистрибутив, если он есть?
  2. Есть ли способ вывести выражение для без ссылки на ?F ( n )f(n)F(n)
  3. Есть ли другие примеры дискретных рекурсивных распределений, подобных этому?

Редактирует уточненный процесс о генерации случайных чисел.

jbarlow
источник
1
По какой причине вы выбрали квадратные скобки вместо ()?
Cam.Davidson.Pilon
1
@ Cam.Davidson.Pilon: мой фон DSP проник в. Мы склонны использовать квадратные скобки для дискретных функций времени. Я предполагаю, что это должно быть неприятно, поэтому я изменю это.
JBarlow
1
Предполагаемый вами процесс не представляется здесь четко определенным. Вы говорите: «На каждом шаге игра выбрасывает случайное число Если , то событие инициируется». Но вы не даете никаких указаний на то, как рисуетсяЯ думаю, что было бы полезно, если бы этот процесс можно было описать немного точнее. X X < p ( n ) XnXX<p(n)X
кардинал
2
@jbarlow: Извините, если мое предыдущее замечание было неясным. Если для некоторого , то ваш процесс не может иметь больше, чем шагов, так как одно случайное число от нуля до единицы определенно будет меньше чем для любого . Величина как функция от очень тесно связана с так называемой функцией опасности в подполе статистики, известном как анализ выживаемости . 0 < k < 1 k - 1p ( n ) n > 1 / k p ( n ) np(n)=kn0<k<1k1p(n)n>1/kp(n)n
кардинал
1
При малых использование дифференциального аналога этого разностного уравнения показывает, что ( не !) Близко к гауссову. (Из этого мы немедленно выводим, например, что среднее значение должно быть около ). Обратите также внимание, что существуют некоторые (сильные) ограничения на , в противном случае, как только превысит (что в конечном итоге и будет), нет гарантии, что останется меньше или равным . F f kF fk p ( n ) 1 F 11/k=33318kp(n)1F1
whuber

Ответы:

9

В некотором смысле, что вы сделали, это охарактеризовали все неотрицательные целочисленные распределения.

Давайте на минуту отложим описание случайного процесса и сосредоточимся на рекурсиях в вопросе.

Если , то, конечно, . Если мы переписываем эту вторую рекурсию в терминах функции выживания (где имеет распределение ), мы получим что-то очень внушительное и простое в обращении. Ясно, что и поэтому Таким образом, пока наша последовательность принимает значения в и не слишком быстро сходится к нулю, мы получим действительную функцию выживания (т. Е. Монотонно уменьшаемую до нуля при ).F n = p n + ( 1 - p n ) F n - 1 S n = 1 - F n = P ( T > n ) T F S n = 1 - F n = ( 1 - p n ) S nfn=pn(1Fn1)Fn=pn+(1pn)Fn1 Sn=1Fn=P(T>n)TFS n = n k = 0 ( 1 - p k )

Sn=1Fn=(1pn)Sn1,
( p n ) [ 0 , 1 ] n
Sn=k=0n(1pk).
(pn)[0,1]n

Более конкретно,

Предложение : последовательность принимающая значения в определяет распределение по неотрицательным целым числам тогда и только тогда, когда и все такие распределения имеют соответствующую последовательность (хотя она может быть не уникальной).[ 0 , 1 ] - n = 0 log ( 1 - p n ) = (pn)[0,1]

n=0log(1pn)=,

Таким образом, рекурсия, написанная в вопросе, является полностью общей : любое неотрицательное целочисленное распределение имеет соответствующую последовательность принимающую значения .[ 0 , 1 ](pn)[0,1]

Однако обратное неверно; то есть существуют последовательности со значениями в которые не соответствуют ни одному допустимому распределению. (В частности, рассмотрим для всех и для )(pn)[0,1]0<pn<1nNpn=0n>N

Но подождите, это еще не все!

Мы намекали на связь с анализом выживаемости, и стоит изучить это немного глубже. В классическом анализе выживаемости с абсолютно непрерывным распределением и соответствующей плотности , то функция риска определяется как Ff

h(t)=f(t)S(t).

Тогда накопленная опасность равна и простой анализ производных показывает, что Отсюда можно сразу дать характеристику допустимой функции риска: любая измеримая функция такая, что для всех и как .Λ(t)=0th(s)ds

S(t)=exp(Λ(t))=exp(0th(s)ds).
hh(t)0t0th(s)dst

Мы получаем рекурсию, аналогичную приведенной выше, для функции выживания, отметив, что дляt>t0

S(t)=et0th(s)dsS(t0).

Заметим, в частности, что мы могли бы выбрать как кусочно-постоянную, причем каждый кусок имеет ширину 1 и такой, что интеграл сходится к бесконечности. Это дало бы функцию выживания которая соответствует любому желаемому дискретному неотрицательному целому числу, оцениваемому по одному на каждое положительное целое число.h(t)S(t)

Подключение обратно к дискретному корпусу

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

h(t)=hn=log(1pn),
(n1,n](pn)

Обратите внимание, что для малых , который обеспечивает эвристическую связь между функцией риска непрерывного распределения и дискретным распределением с соответствующей функцией выживания на целые числа. - log ( 1 - p n ) p n = f n / S n - 1pnlog(1pn)pn=fn/Sn1

Постскриптум : В качестве заключительного замечания, пример в вопросе не удовлетворяет необходимым условиям без соответствующей модификации при и установке для всех .f n n = k - 1f n = 0 n > k - 1pn=knfnn=k1fn=0n>k1

кардинальный
источник
1
kk=1/2f=(0,1/2,1/2,0,)k=1/mf(m+1)=f(m+2)==0
2
fnFnfn
2
Отличный ответ. Это очень проницательно. Мне было действительно интересно видеть эту проблему связанной с другими областями и понятиями.
JBarlow
1
@jbarlow: Спасибо. Я рад, что вы нашли это полезным! Мне понравилось немного подумать об этом, так как это хороший вопрос.
кардинал
8

p(n)=p<1

F(n)=p+F(n1)(1p);F(0)=p

есть решение

F(n)=P(Nn)=1(1p)n+1

p(n)

Другие случаи:

  1. p(n)=pn;p<1;F(0)=p
    F(n)=1(1p)Γ(n+1p)Γ(1p)Γ(n+1)
  2. S(n)=1F(n)
    S(n)=(1p(n))S(n1)
  3. p(n)np(n)=knp>1
    p(n)=1(1p)n+1p<1
    p(0)=pp(n)
    F(n)=1(1p)n+1n!
    S(n)=1F(n)=(1p)n+1n!
    i=0S(i)=E[N]
    E[N]=(1p)e(1p)
Cam.Davidson.Pilon
источник
2
Кэм, это не функция опасности, а функция выживания . :-)
кардинал
1
ty, * отредактировано для выживания
Cam.Davidson.Pilon