確率過程としての乱択計算論

随机计算作为随机过程

基本信息

批准号：
21H03396
负责人：
来嶋秀治
金额：
$ 10.15万
依托单位：
Shiga University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21H03396/
关键词：
アルゴリズム理論離散構造マルコフ連鎖

项目摘要

アルゴリズム設計において，乱択化（randomization）は理論的にも実用上も不可欠な基本技法である．本課題は，「ランダムネスは計算にどのように寄与するか？」という問いに対し，とくに計算効率に焦点を当てた理論発展を目的とする．決定性計算を決定性過程と捉え，同様に乱択計算を確率過程と捉えて，決定性過程と確率過程の対比をもってランダムネスの計算効率への寄与を測る点が本課題の特色である．この目的に沿って，決定性過程と確率過程を対比する技術の開発，この技術に関連する応用または基礎研究に取り組み，また，計算効率にとどまらない乱択計算論の新展開も目指す．ゲーム論における繰り返しゲームの確率過程解析を動機として，非推移的サイコロの研究に取り組んだ．非推移的サイコロは，サイコロの目が一般化されたサイコロの組で，サイコロの組を上手に設計すると，Efron's diceで知られる例のように，強弱関係が非推移的になることが知られる．本研究ではまず，一般化じゃんけんにおけるゲーム論的に無駄な手の議論を参考に，非推移的サイコロにおけるゲーム論的に無駄なサイコロ（戦略）について議論した．そして，繰り返しゲームの解析の準備として，ある種の公平性の下，非推移的サイコロが非自明な均衡をもつための条件について明らかにした．得られた成果をAAAI 2021で発表した．このほか，決定論的カオスの計算量に関する研究や動的グラフ上のランダムウォークの研究なども推進し，萌芽的成果を得た．

随机化是一种基本技术，在算法设计中既是理论上又实用的。该主题旨在发展理论，特别是关注计算效率，以回答“随机性如何有助于计算？”该主题是我们将确定性计算视为确定性过程，并类似地将随机计算视为随机过程，并通过比较确定性过程和随机过程来衡量随机性对计算效率的贡献。与此目的相一致，我们旨在开发与确定性和随机过程对比的技术，开发与该技术相关的应用或基础研究，并旨在开发不限于计算效率的随机计算理论中的新发展。通过对游戏理论重复游戏的随机过程的分析，我们研究了非传播骰子的研究。非传递骰子是一组带有广义骰子的骰子，众所周知，如果您设计一组骰子，强度关系就会变得不可传输，如在Efron骰子中所知的示例。在这项研究中，我们首先讨论了非传递骰子中的游戏理论浪费骰子（策略），并考虑到了对广义岩纸剪辑器中游戏理论浪费的手的讨论。为了准备重复游戏的分析，我们阐明了在某些公平性下具有非平凡平衡的非易位骰子的条件。获得的结果是在AAAI 2021中提出的。此外，我们还促进了确定性混乱的计算复杂性的研究，并研究了动态图上随机步行的研究，从而实现了新兴的结果。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Is There a Strongest Die in a Set of Dice with the Same Mean Pips?

具有相同平均点数的一组骰子中是否存在最强的骰子？

DOI：
10.1609/aaai.v36i5.20447
发表时间：
2022
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
0
作者：
Lu Shang;Kijima Shuji
通讯作者：
Kijima Shuji

私の数理工学・補遺

我的数学工程附录

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Enomoto H.;Nishimura T.;Aizawa N.;Takashima T.;Ikeda N.;Yuri Y.;Fujiwara;A.;Yoshihara K.;Yoshioka R.;Kawata S.;Ota S.;Nakano R.;Shiomi H.;Iijima H;来嶋秀治
通讯作者：
来嶋秀治

黄金比付近でのテント展開の平均空間計算量

接近黄金比例的帐篷部署平均空间复杂度